KasMP

А чем они плохи? Нам же надо найти просто любую раскраску. Если ты имеешь в виду оптимизацию, то она вряд ли сильно спасёт (раскрасок вообще 4^N, а с учётом не-симметричности будет в 2 раза меньше), да и непонятно, как избавить перебор от них.


Ну да, если мы хотим написать рекурсивный переборный раскрасок, то нет никакого смысла пытаться написать его так, чтобы _синтаксически_ не было рекурсии. Хотя, впрочем, такая оптимизация иногда сильно помогает - избавление от рекурсии на уровне языка, замена её ручным моделированием рекурсии (со стеком). Но опять же, код усложнится и станет менее понятным, а какой прирост скорости мы получим взамен - ещё неизвестно.


[про линейное программирование] 
Ну потому что вместо ясной задачи на графе мы получаем задачу 0-1-ЛП, которую надо как-то решать. Наверно, этому посвящены кучи теории, но чтобы написать что-то, надо всё это перелопатить  Да и вообще, у меня есть сомнения, что по скорости этот метод вообще может быть быстрее других.


Разброс нехилый 
Для 20-30, думаю, и самый простой перебор будет укладываться. А вот для 1024 и хоть немного сложного графа - это заставит его задуматься весьма надолго  Для 1024, наверно, уже вообще нет смысла пытаться применять точные алгоритмы раскраски...

Если раскраска хорошая, то ничем - мы ее нашли и ура  .
А если она плохая?? Мы вернемся на уровень вверх, потом через несколько шагов попадем в "симметричную" плохую, потом снова  ...

Наверно, это зависит от кол-ва переменных в рекурсивной ф-ии.
В любом случае, даже при ф-ии с одной переменной i, увеличивающейся на единицу от 0 до какого-то n, мы при рекурсии одновременно будем хранить несколько экземпляров i: i=0, i=1, i=2, i=3, i=4, i=5, ... . А если делать это через циклы, то в один момент времени у нас будет одна переменная i с каким-то значением j (я только что это осознала  ; знать-то я это и так знала, но вот сейчас почувствовала...).
i=0, i=1, i=2, i=3, i=4, i=5, ... - туповато как-то, по-моему.

Добавлено @ 23:32

Тогда пусть 1<n<=100  . Здесь тоже есть, что посчитать.

Это сообщение отредактировал(а) KasMP - 17.3.2009, 23:38

В принципе мой перебор работает и дает правильные результаты, но в каком-то месте не хватает выхода из рекурсии: после того, как найден правильный вариант, рекурсия еще несколько раз закручивается и раскручивается, еще проверяет все на бог знает сколько раз.


Есть ощущение, что вместо вызовов типанадо использовать более ... направляющие варианты:

Добавлено через 13 минут и 42 секунды
Если возникнет желание помочь, то вам может пригодиться это:

• Используемые типы:
  

  Код

  struct GRAPH {     short    n;     bool    **adj;     short    *color; };

  
  
• Используемые при проверке функции:
  

  Код

  bool Edge (GRAPH *graph, short i, short j) { return (graph->adj[i][j] || graph->adj[j][i]); } bool AnotherColorExists (GRAPH *graph, short i) { return (graph->color[i] != num); } bool SameColor (GRAPH *graph, short i, short j) { return (graph->color[i] == graph->color[j]); }

  
  
• Функции для графа (его матрицы смежности и раскраски) - выделение памяти, чтение из файла, удаление, вывод (на консоль), т.п.:
  

  Код

  void LoadNewGraph (GRAPH *graph, short t, ifstream *p_f) {     graph->n = t;     // выделение памяти для м-ы смежности из bool, запись м-ы     (graph->adj) = new bool *[t];     for (short i=0; i<t; i++) {         graph->adj[i] = new bool[t];         // чтение строки из файла в строку м-ы смежности         for (short j=0; j<t; j++)             *p_f >> graph->adj[i][j];     }     // выделение памяти для массива цветов из short, инициализация     graph->color = new short[t];     for (short i=0; i<t; i++)                 graph->color[i] = 0; } void PrintMatrix (GRAPH *graph) {     short n = graph->n;     cout << "Size = " << n << "\n";         for (short i=0; i<n; i++) {         for (short j=0; j<n; j++)             cout << graph->adj[i][j] << ' ';         cout << "\n";     }     cout << "\n"; } void DeleteGraph (GRAPH *graph) {     short n = graph->n;     for (short i=0; i<n; i++)         delete[] graph->adj[i];     delete [] graph->adj;     delete [] graph->color; } void PrintColor (GRAPH *graph) {     short n = graph->n;     for (short i=0; i<n; i++) {         cout << "vertice " << i+1 << ": ";         switch (graph->color[i]) {             case 0: cout << "0 \n"; break;             case 1: cout << "yellow \n"; break;             case 2: cout << "blue \n"; break;             case 3: cout << "green \n"; break;             case 4: cout << "violet \n"; break;         }     }     cout << "\n"; }

  
  
• Main(), которой все это предназначается:
  

  Код

  #include <fstream> #include <iostream> using namespace std; const char path1[]="C:\\in.txt";        // входной файл const char path2[]="C:\\out.txt";        // выходной файл const short num = 4; int main() {     GRAPH graph;          ifstream fin(path1); ofstream fout(path2);     short n;     fin >> n;         LoadNewGraph(&graph,n,&fin);     PrintMatrix(&graph);               if (Paint(&graph,0))         PrintColor(&graph);     else         cout << "Impossible.";     DeleteGraph (&graph);     fin.close(); fout.close();     return(0); }

  
  
• Примеры исходных файлов.
  

  Цитата

  8 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0

  
  

  Цитата

  4 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 0

Достаточно необычно перебор написан, но конкретно по вопросу - видимо, стоит везде написать так:

А иначе (если вернулось false) всё будет продолжаться перебираться дальше.

В смысле плохо? Что ты имеешь в виду  ?


Я думала об этом... Сейчас додумаю эту мысль до конца  .
Спасибо    .

Добавлено через 8 минут и 44 секунды

Сюда мы попадаем после проверки с "+" результатом.
Если условие выполняется, то это значит, что еще есть незакрашенные вершины, что надо еще сходить в i+1 вершину..; если неверно, то это конец (закрашивать больше нечего, все уже хорошо) и мы можем выйти.

Добавлено через 11 минут и 42 секунды

Сюда мы попадаем, когда узнаем, что цветов для этой вершины больше нет.
Ну мы и хотим узнать, есть ли смысл подниматься в i-1 и пытаться перекрасить ее... Если i-1 - первая вершина, то нет смысла перекрашивать первую вершину в другой цвет и проверять симметричные комбинации - уходим. Если вершина где-то посередине, то можно посмотреть и поискать.

Ну не то чтобы плохо, просто в некоторых местах рекурсия используется неоправданно. Ты подбираешь очередной цвет, проверяешь, не нарушает ли он правильность покраски по отношению к уже покрашенным вершинам, и если нарушает, то зачем-то вызываешь рекурсию от той же вершины. Было бы логичнее просто перебирать цвет вершины i, проверять его на корректность, и если он хороший, то вызывать рекурсию от следующей вершины, а иначе просто сразу переходить к следующей итерации цикла (цикла по цвету).

не забыв при этом обнулить следующие вершины

Добавлено через 6 минут и 14 секунд

Это делается для того, чтобы изменить цвет вершины, нарушившей правильность...
Ведь все начинается с:

Т.е. мы как раз и перебираем цвет вершины i.
Что не так  ?

Добавлено через 8 минут и 42 секунды
Еще меня добивает, что при КАЖДОМ вызове ф-ии делается

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

Это большая неправда.
В очевидном случае
он путается...

Сейчас найдем его  .

Добавлено через 11 минут и 5 секунд
Все-таки правильнее так:


Добавлено через 12 минут и 58 секунд
Осталось нарисовать и раскрасить  .

Нет.

esperanto, это одинокое "нет" не добавляет никакой пользы. Можно подробнее  ?

А еще у нас есть замечательная

Ну, вероятно, имелось в виду, что NP-полнота не обязательно означает только переборное решение. Даже тут где-то приводилось сведЕние этой задачи к другим, например, линейное 0-1-программирование. Для них могут быть свои алгоритмы, работающие не за полиномиальное время (как, например, для линейного программирования - симплекс - за O(2^N) (или даже больше?)), но не имеющие ничего общего с перебором.

Это сообщение отредактировал(а) maxdiver - 23.3.2009, 13:29

Какое многообразие  !
Эх, сколько еще предстоит узнать мне, если я не сверну с пути программиста ...

Добавлено через 4 минуты и 33 секунды

Кошмар какой  ! и не поправил никто  !
Не лучше ли просто

Ребята, а разве

и

не одно и то же ?!

Почему-то в первом случае работает правильно, а во втором - нет...

Одно 

Я так же думаю, но если заменить первое на второе, то ф-я работает неправильно    ...