图着色算法 - 分配颜色
Graph Coloring Algorithm - Assign color
我这里有一个图表着色算法的函数,它为许多课程分配颜色。但是它是随机选择的,我想改进算法并比根据可用颜色随机选择一种更有效地分配颜色。
在这个函数中,N
是时间安排的个数。
void create_schedule(int **graph, list *courses, int numcourses){
int i, j, k, col=0;
for(i=0; i<numcourses; i++){
for(j=0; j<N; j++){
for(k=0; k<i; k++){
if(graph[i][k] > 0 && courses[k].color == j) break;
}
//color j was not yet chosen by adjacent nodes
if(k >= i){
courses[i].color = j;
break;
}
}
//if there is no color available, choose randomly
if(j >= N){
col = rand()%N;
courses[i].color = col;
}
}
}
最好有解释。
首先,让我们定义问题 canColor(graph, k)
- 当且仅当您可以 graph coloring 使用 k 种颜色绘制图形时,它才会回答正确。
canColor
的伪代码:
canColor(graph, k):
if graph is completely colored:
return checkIfColoringValid(graph)
v = first uncolored vertex
for each i from 1 to k (inclusive)
color v with color i
//can add optimization here to trim upfront unsuccesful results
res = canColor(graph,k)
if res == true:
return true
//no answer found
uncolor v (mark it as color[v] = 0)
return false
以上是图着色decision problem
现在,我们需要用它来找到最佳着色。
请注意,如果 canColor(graph,k) == true,则 canColor(graph,k+1) == true
这意味着,你有一个隐喻的答案数组,0,0,..0,1,1,...,1
,一旦有一些 k
的解决方案,k
之后的所有值也将有一个解决方案.这个隐喻数组是排序的,所以你可以在它上面应用 binary search (而不是访问数组,你每次计算 canColor(graph,k)
的答案),以获得 k
的最佳值 -您可以使用的颜色数量。