Алгоритм раскраски графа - Назначить цвет

Question

У меня есть функция в алгоритме раскраски графа, который присваивает цвет ряду курсов. Но он выбирает случайным образом, и я хотел бы улучшить алгоритм и назначить цвет более эффективно, чем выбирать его случайным образом на основе доступных цветов.

В этой функции 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; 
     } 
    } 
} 

Объяснение было бы здорово.

Answer 1

Прежде всего, давайте определим проблему 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 (граф, к) == верно, то также canColor (граф, к + 1) == истинный

Это означает, что у вас есть метафорический массив ответов, 0,0,..0,1,1,...,1, когда есть решение для некоторых k, все значения k после того, как он также будет иметь решение. Этот метафорический массив отсортирован, поэтому вы можете применить к нему binary search (где вместо доступа к массиву вы каждый раз рассчитываете ответ для canColor(graph,k)), чтобы получить оптимальное значение k - количество цветов, которое вы можете использовать.