圖形着色算法 - 分配顏色

我在這裏有一個圖形着色算法中的函數，它將顏色分配給多個課程。但它隨機選擇，我想改進算法，並比基於可用顏色隨機選擇一個更有效地分配顏色。圖形着色算法 - 分配顏色

在這個函數中，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; 
     } 
    } 
}

解釋會很好。

來源

2015-05-06 CrazyGirl

你的問題不清楚。「你的意思是」更有效地指定顏色，而不是根據可用顏色隨意給予顏色「，你在這裏的含義是什麼」有效「？你想讓它跑得更快？你期待什麼樣的加速，你期望你能達到什麼目的？ – amit

我想盡可能少使用顏色 – CrazyGirl

而您知道這個問題是NP-Complete？所以最佳解決方案將會花費指數時間（除非P = NP，這不太可能）？ – amit

首先，我們來定義問題canColor(graph, k) - 只有當您可以使用k種顏色進行圖形繪製時，它纔會回答true。

僞爲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（圖中，k）== true，那麼也canColor（圖中，k + 1）== TRUE

這意味着，必須答案，0,0,..0,1,1,...,1的隱喻陣列，一旦有一個解決方案對於一些k，所有k之後的值也會有解決辦法。這個隱喻數組是排序的，因此您可以在其上應用binary search（而不是訪問數組，每次計算回答爲canColor(graph,k)），以獲得最佳值k - 您可以使用的顏色數。

來源

2015-05-06 08:33:44 amit

如果不是優化顏色，而是優化目標函數的最終值？這個問題並沒有真正相關，但我也想知道。 – CrazyGirl

@CrazyGirl這將取決於你的目標函數，你有什麼目標函數？很明顯，儘可能減少顏色數量的目標函數 - 答案是相同的。 – amit

圖形着色算法 - 分配顏色

回答

相關問題