Есть связный граф и 4 цвета. Надо найти такую раскраску, при которой никакие две смежные вершины не покрашены в один цвет.
Предположительно, граф будет задаваться матрицей смежности.

Добавлено через 2 минуты и 1 секунду
Говорят, эта задача относится к классу NP-полных задач... Т.е. нет лучшего алгоритма решения, чем просто перебор  .

Добавлено через 5 минут и 38 секунд
Если даже рассматривать перебор, то не совсем понятно, как перебирать вершины графа... Граф любой: хотя с циклами, хоть без, хоть ориентированный, хоть нет, хоть.
Сегодня судьба свела меня с алгоритмом Липтона... В нем используется представление ... эээ ... графообразных структур, которое можно попробовать задействовать. Пока хочу идти от этого...

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

Что такое алгоритм Липтона, понятия не имею. Это такое задание - использовать его?

Я понимаю, я так для краткости написала.

Нет.
Задание - пользоваться методами теории графов.

Вообще он относится к молекулярной биологии:
есть раствор в пробирке, в нем цепочки нуклеотидов ДНК;
цепочки могут соединяться в разных последовательностях и мы хотим выбрать только те, которые удовлетворяют каким-то условиям;
для этого сначала порождаются все возможные последовательности (при этом создается, так сказать, графообразное представление: каждая цепочка - вершина, связь между цепочками - ребро, ну и еще интересные особенности, которые и привлекли мое внимание; каждая последовательность рассматривается как путь в этом графе);
ну и дальше с помощью нескольких шагов (не буду утомлять тебя их описанием) отбрасываются ненужные последовательности;
смотрят, осталась хоть одна последовательность?

Короче, все равно это все не поможет, т.к. порождение всевозможных путей и выбор нужных к моей задачке отношения не имеет - возможные пути уже указаны.

Ну и там же было сказано, что задача 3-раскраски (раскраски в три цвета так, чтобы смежые вершины были разноцветными) - NP-полная, что это доказано и пока ничего не найдено... Я так понимаю, тогда 4-раскраска тем более NP-полная.

Вот в этом и была моя ошибка.
Я все время пыталась сначала понять, смежны ли вершины и раскрасить их в разные цвета; потом, если каким-то вершинам не хватило раскраски, то сделать, например, раскраску не 1-2-3, а 1-2-1... А это же по сути построение раскраски  .
А в переборе с точностью до наоборот обратный подход: сначала раскрасить как попало - хоть все вершины в один цвет  (ну понятно, что в связном графе не надо тратить силы на рассмотрение этого варианта), а потом смотреть, смежно или не смежно.
Оказывается, у меня проблемы с определением перебора  !

Спасибо, вобщем    !

ну, почему? если у тебя при раскраске 2-й по счету вершины уже видно, что схема не подойдет(цвет у первой и второй одинаковый и они смежные), то берем другой цвет для второй вершины, а не строим все остальные (N-2)! вариантов сочетаний для явно проигрышного варианта раскраски.

Доказано, что невозможно с помощью циркуля и линейки разделить любой угол на три равные части. Ну и что? Прямой угол делится запросто. Это я к тому, что NP-полная задача не должна уж так сильно запугивать..

Скажем, пять вершин и все, какие возможны, ребра - сильнее не связать. Без всякого перебора очевидно, что задача не разрешима: все вершины смежные - стало быть, все  нужно красить в разные цвета. А цветов у нас всего четыре.

А если у нас не 5 вершин, а 100005? Чем нам может помочь предыдущее наблюдение?
А тем, что если мы среди 100005 найдем 5 таких, что они связаны вот так крепко, то и вся задача для 100005 неразрешима. А поиск таких завязок - это не NP-полная задача, а что-то порядка поиска циклов в графе.

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

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

Осталось разобраться с циклами.

Удачи!
_______________________________________________
P.S. Подсказка.
Если у нас есть циклы, но никакие два цикла не имеют общих ребер, то задача тоже решается тривиально прямым построением. Но только если цветов больше трех.
Это замечание надо понимать и так, что из того, что для трех цветов задача NP-полная, то из этого не следует, что она такая же трудная для четырех цветов.
А здравый смысл без всякой теории графов подсказывает: чем больше цветов, тем проще задача.


Это сообщение отредактировал(а) Sefko - 14.3.2009, 20:14

Sefko

Поиск клик (и даже проверка наличия клик фиксированного размера) тоже NP-полная задача. В данном случае (для размера 5) что-то не видится алгоритма, быстрее O(N^5). Это огромное время, на большинстве практических тестов перебор отработает быстрее. Более того, как вы сами заметили, отсутствие таких клик не означает, что граф может быть раскрашен, и уж тем более не даёт самой раскраски.


Здесь вообще не понял. Ну будет у нас такая "звёздочка" - граф из 10 вершин, где все вершины 2..10 смежны вершине 1 и только ей. В вершине 1 "сходятся" 9 рёбер, однако этот граф можно раскрасить в 2 цвета.


Гениально  Сколько бы частных случаев мы ни разбирали, останется бесконечное число графов (и, скорее всего, асимптотически почти все графы), которые не подходят ни под какой частный случай.

Sefko
Кстати, цитата из авторитетной книги "Вычислительные машины и труднорешаемые задачи" Гэри и Джонсона:



Т.н. "здравый смысл" много чего подсказывает (например, мне подсказывает, что задача о гамильтоновом цикле не должна бы быть сильно сложнее задачи о эйлеровом цикле), но в математике, и особенно в теории сложности, доверяться ему просто глупо.

А тут и понимать особо нечего. Просто не стоит писать якобы серьезные сообщения наспех. Это кирпич в мой огород. Но удалять сообщение (методом затирки) не буду. Пусть висит. Другим наука.

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

Благодарим за желание помочь   !

Замечательная цитата    !

Вобщем я начинаю представлять, как все это будет выглядеть  .

Граф можно задавать любым удобным способом. Нам будет удобен тот, где можно максимально быстро и просто определить, смежны вершины с номерами i и j или нет.
Имхо "быстро и просто" - это м-а смежности: если [i][j] и [j][i] - нули, то вершины не смежны; иначе - смежны.


Теперь непосредственно перебор (с почти правильными исключениями  ):

закрасили вершину i
смотрим на i-ые строку и столбец м-ы смежности (смотрим элементы с номерами [i][j] и [j][i], где 0<=j<i - зачем проверять на смежность еще не закрашенное?)
    увидели не смежность - перешли на уровень глубже (закрасили вершину i+1, ...)
    иначе - проверили вершины i и j на совпадение цвета
        увидели не совпадение - перешли на уровень глубже (закрасили вершину i+1, ...)
        иначе - проверили, есть ли неиспользованные цвета для i
                есть - поднялись обратно и перекрасили вершину i
                нет - поднялись, поднялись и перекрасили i-1

Добавлено через 2 минуты и 51 секунду
Какая-то рекурсия получается... Да еще и не исключены симметричные варианты: 4-3-1-3, 4-2-1-2, 3-2-1-2, 1-4-3-4, ... .

KasMP
В 4 цвета можно раскрасить плоские графы, т.е. те которые можно нарисовать на плоскости без пересечения рёбер.

Алгоритм для раскраски логичнее (да и лучше) взять готовый. Наиболее известная книга по алгоритмам теории графов 
Н. Кристофедес, "Теория графов. Алгоритмический подход."
Там много алгоритмов по раскраскам. Можете сначала почитать параграф в этой книге, а затем найти где-нибудь в Интернете приглянувшийся запрограммированный алгоритм.


Это сообщение отредактировал(а) nworm - 17.3.2009, 17:56

А не плоские, я так понимаю, иногда можно, иногда - нет?

Спасибо  !Теперь знаю, что читать  !

Нет, вот это я буду делать уже сама  ...
(тем более, что результат надо еще нарисовать через API-функции  )

Добавлено @ 18:13

Целая глава про раскраски  !

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

KasMP

Вроде всё правильно. Самая что ни на есть рекурсия.


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

Кстати, какие всё-таки ограничения на размер графа? Может, meet-in-the-middle с динамическим программированием будет удобно применить.

Особенно правилен перебор "симметричных" вариантов - цвета-то разные, а суть одинаковая:
4-3-1-3, 4-2-1-2, 3-2-1-2, 1-4-3-4, ... . 

4-3-1-3 читается как "вершина 1 цвета 4, вершина 2 цвета 3, в3 цвета 1, в4 цвета 3"
4-2-1-2 читается как "в1 цвета 4, в2 цвета 2, в3 цвета 1, в4 цвета 2"

Как от них избавиться??

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

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

Почему  ?

Ну, понятно, что для проверки больше 20-30 никто не возьмет... Но для порядка пусть их будет 1024    .

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

Предполагаю хранить текущую раскраску в одномерном массиве размерности n: a[i] = {0, 1, ... 4}, 0 <= i <= n-1 .
Вроде логично  (да и вообще по-другому сложно придумать  ).

Можно a[i] сделать не каким-то целочисленным, а символьным - зачем занимать ненужные байты? (да и перепрыгивать через 1 байт легче, чем через 2 или 4)
Если a[i] - символ, то получается что-то типа битовой маски, только не из {0, 1}, а из {0, ..., 4}. Интересно  .

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

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 секунды

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

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

и

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

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

Одно 

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