Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Связный граф, его раскраска...

Автор: KasMP 13.3.2009, 22:37

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

Автор: maxdiver 14.3.2009, 00:41

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

Автор: KasMP 14.3.2009, 06:17

Цитата(maxdiver @  14.3.2009,  00:41 ) Перебираем мы не вершины графа, а перебираем то, как мы их раскрашиваем. Я понимаю, я так для краткости написала. Цитата(maxdiver @  14.3.2009,  00:41 ) Это такое задание - использовать его?  Нет. Задание - пользоваться методами теории графов. Цитата(maxdiver @  14.3.2009,  00:41 ) Что такое алгоритм Липтона, понятия не имею. Вообще он относится к молекулярной биологии: есть раствор в пробирке, в нем цепочки нуклеотидов ДНК; цепочки могут соединяться в разных последовательностях и мы хотим выбрать только те, которые удовлетворяют каким-то условиям; для этого сначала порождаются все возможные последовательности (при этом создается, так сказать, графообразное представление: каждая цепочка - вершина, связь между цепочками - ребро, ну и еще интересные особенности, которые и привлекли мое внимание; каждая последовательность рассматривается как путь в этом графе); ну и дальше с помощью нескольких шагов (не буду утомлять тебя их описанием) отбрасываются ненужные последовательности; смотрят, осталась хоть одна последовательность? Короче, все равно это все не поможет, т.к. порождение всевозможных путей и выбор нужных к моей задачке отношения не имеет - возможные пути уже указаны. Ну и там же было сказано, что задача 3-раскраски (раскраски в три цвета так, чтобы смежые вершины были разноцветными) - NP-полная, что это доказано и пока ничего не найдено... Я так понимаю, тогда 4-раскраска тем более NP-полная. Цитата(maxdiver @  14.3.2009,  00:41 ) Т.е. для каждой вершины перебираем все возможные её цвета, и проверяем, корректная ли раскраска у нас получилась. Вот в этом и была моя ошибка. Я все время пыталась сначала понять, смежны ли вершины и раскрасить их в разные цвета; потом, если каким-то вершинам не хватило раскраски, то сделать, например, раскраску не 1-2-3, а 1-2-1... А это же по сути построение раскраски  . А в переборе с точностью до наоборот обратный подход: сначала раскрасить как попало - хоть все вершины в один цвет  (ну понятно, что в связном графе не надо тратить силы на рассмотрение этого варианта), а потом смотреть, смежно или не смежно. Оказывается, у меня проблемы с определением перебора  ! Спасибо, вобщем    !

Автор: skyboy 14.3.2009, 10:06

Цитата(KasMP @  14.3.2009,  05:17 ) А в переборе с точностью до наоборот обратный подход: сначала раскрасить как попало - хоть все вершины в один цвет ну, почему? если у тебя при раскраске 2-й по счету вершины уже видно, что схема не подойдет(цвет у первой и второй одинаковый и они смежные), то берем другой цвет для второй вершины, а не строим все остальные (N-2)! вариантов сочетаний для явно проигрышного варианта раскраски.

Автор: Sefko 14.3.2009, 19:56

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

Автор: maxdiver 14.3.2009, 21:54

Sefko Цитата А тем, что если мы среди 100005 найдем 5 таких, что они связаны вот так крепко, то и вся задача для 100005 неразрешима. А поиск таких завязок - это не NP-полная задача, а что-то порядка поиска циклов в графе. Поиск клик (и даже проверка наличия клик фиксированного размера) тоже NP-полная задача. В данном случае (для размера 5) что-то не видится алгоритма, быстрее O(N^5). Это огромное время, на большинстве практических тестов перебор отработает быстрее. Более того, как вы сами заметили, отсутствие таких клик не означает, что граф может быть раскрашен, и уж тем более не даёт самой раскраски. Цитата Но ведь дело-то еще проще. Не нужно искать такие плотно связные группы - достаточно выяснить, есть ли вершины, в которых сходится более чем три ребра (ориентированность ребер к самой задаче отношения не имеет - можем считать граф неориентированным). Если есть, то все - приехали. Здесь вообще не понял. Ну будет у нас такая "звёздочка" - граф из 10 вершин, где все вершины 2..10 смежны вершине 1 и только ей. В вершине 1 "сходятся" 9 рёбер, однако этот граф можно раскрасить в 2 цвета. Цитата С другой стороны, если наш граф дерево, и нет вершин, в которых сходится более чем три ребра, то решение существует всегда, и строится тривиально прямым способом, без какого бы то ни было перебора. Осталось разобраться с циклами. ...Если у нас есть циклы, но никакие два цикла не имеют общих ребер, то задача тоже решается тривиально прямым построением. Гениально  Сколько бы частных случаев мы ни разбирали, останется бесконечное число графов (и, скорее всего, асимптотически почти все графы), которые не подходят ни под какой частный случай.

Автор: maxdiver 14.3.2009, 22:10

Sefko Кстати, цитата из авторитетной книги "Вычислительные машины и труднорешаемые задачи" Гэри и Джонсона: Цитата УСЛОВИЕ. Заданы граф G =(V, E) и положительное целое  число K<|V|.  ВОПРОС. Верно ли, что граф G K-раскрашиваем? (Граф на-  называется K-раскрашиваемым, если существует такая функция  f: V->{1,2, ..., К}, что если {u,v} in E, то f(u)!=f(v).)  Источник [280]. К этой задаче сводится задача 3-ВЫП.  Комментарий. При К = 2 задача разрешима за полиномиаль-  полиномиальное время, но при всех фиксированных К >= 3, а также для  К = 3 и плоских графов, степени всех вершин которых не пре-  превосходят 4, задача NP-полна. Она остается также NP-полной  при К = 3, когда G— это граф пересечений отрезков прямых  линий на плоскости [112]. Задача NP-полна также для произ-  произвольного К и графов пересечения окружностей и дуг окруж-  окружностей (даже если графы представлены в виде семейства дуг).  Для графов пересечения дуг окружностей, представленных в  виде семейства дуг, при любом фиксированном К задача разре-  разрешима за полиномиальное время [153]. В общем случае задача  может быть решена за полиномиальное время для графов срав-  сравнимости [117], для триангулированных графов [163], для (3,1)-  графов [532], а также для графов, не имеющих вершин степени  выше 3 [56]. Цитата А здравый смысл без всякой теории графов подсказывает: чем больше цветов, тем проще задача. Т.н. "здравый смысл" много чего подсказывает (например, мне подсказывает, что задача о гамильтоновом цикле не должна бы быть сильно сложнее задачи о эйлеровом цикле), но в математике, и особенно в теории сложности, доверяться ему просто глупо.

Автор: Sefko 15.3.2009, 14:08

Цитата(maxdiver @  14.3.2009,  21:54 ) Здесь вообще не понял. А тут и понимать особо нечего. Просто не стоит писать якобы серьезные сообщения наспех. Это кирпич в мой огород. Но удалять сообщение (методом затирки) не буду. Пусть висит. Другим наука.

Автор: KasMP 17.3.2009, 16:25

Цитата(skyboy @  14.3.2009,  10:06 ) ну, почему? если у тебя при раскраске 2-й по счету вершины уже видно, что схема не подойдет(цвет у первой и второй одинаковый и они смежные), то берем другой цвет для второй вершины, а не строим все остальные (N-2)! вариантов сочетаний для явно проигрышного варианта раскраски.   Конечно. Когда я говорила "как попало", то я больше думала не об этой конкретной задаче, а о переборе в принципе. Понятно, что при переборе нужно исключать заведомо неподходящие варианты и что это очень желательная составная часть перебора. (рада тебя видеть   ты все так же верен своему желанию (пере)делать все Рационально, Правильно, Экономично    ; только для того, чтобы это желание реже усаживало тебя переписывать чужое творение, я буду делать нормальные программы) Цитата(Sefko @  14.3.2009,  19:56 ) ... Удачи! ... Благодарим за желание помочь   ! Цитата(maxdiver @  14.3.2009,  22:10 ) Кстати, цитата из авторитетной книги "Вычислительные машины и труднорешаемые задачи" Гэри и Джонсона: Замечательная цитата    !

Автор: KasMP 17.3.2009, 16:53

Вобщем я начинаю представлять, как все это будет выглядеть  . Граф можно задавать любым удобным способом. Нам будет удобен тот, где можно максимально быстро и просто определить, смежны вершины с номерами 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, ... .

Автор: nworm 17.3.2009, 17:54

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

Автор: KasMP 17.3.2009, 18:06

Цитата(nworm @  17.3.2009,  17:54 ) В 4 цвета можно раскрасить плоские графы А не плоские, я так понимаю, иногда можно, иногда - нет? Цитата(nworm @  17.3.2009,  17:54 ) Н. Кристофедес, "Теория графов. Алгоритмический подход." Спасибо  !Теперь знаю, что читать  ! Цитата(nworm @  17.3.2009,  17:54 ) а затем найти где-нибудь в Интернете приглянувшийся запрограммированный алгоритм. Нет, вот это я буду делать уже сама  ... (тем более, что результат надо еще нарисовать через API-функции  ) Добавлено @ 18:13 Цитата(KasMP @  17.3.2009,  18:06 ) Спасибо smile !Теперь знаю, что читать smile ! Целая глава про раскраски  !

Автор: maxdiver 17.3.2009, 22:03

KasMP Цитата Теперь непосредственно перебор (с почти правильными исключениями  ): Вроде всё правильно. Самая что ни на есть рекурсия. Цитата Целая глава про раскраски  ! Ну я посмотрел, если нужен точный алгоритм раскраски, то там предлагается либо точно такой же перебор, либо линейное программирование (что, я не думаю, лучше подходит тебе  ), либо к задаче о наименьшем покрытии (для которой опять же переборный алгоритм). Кстати, какие всё-таки ограничения на размер графа? Может, meet-in-the-middle с динамическим программированием будет удобно применить.

Автор: KasMP 17.3.2009, 22:28

Цитата(maxdiver @  17.3.2009,  22:03 ) Вроде всё правильно. Особенно правилен перебор "симметричных" вариантов - цвета-то разные, а суть одинаковая: 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" Как от них избавиться?? Цитата(maxdiver @  17.3.2009,  22:03 ) Самая что ни на есть рекурсия. Рекурсия, да  . Есть мнение, что рекурсией можно пользоваться тогда, когда нужна наглядность, маленькое время написания и простота самого процесса написания, а производительность некритична (и что вообще рекурсию используют неумеющие программировать люди); а нормальные программы лучше писать без рекурсии. Поэтому мне не нравится рекурсия. Хотя, с другой стороны, если даже в программе у нас не будет рекурсии в явном виде, то в нашем случае в памяти навряд ли что-то изменится: все равно надо помнить цвета предыдущих вершин в текущей "итерации", все равно будет создаваться что-то типа дерева рекурсии (правильно назвала?) и его глубина останется такой же. Я же правильно думаю  ? Т.е. пытаться не использовать рекурсию в данном случае бессмысленно  ? Цитата(maxdiver @  17.3.2009,  22:03 ) что, я не думаю, лучше подходит тебе smile Почему  ? Цитата(maxdiver @  17.3.2009,  22:03 ) Кстати, какие всё-таки ограничения на размер графа? Ну, понятно, что для проверки больше 20-30 никто не возьмет... Но для порядка пусть их будет 1024    .

Автор: KasMP 17.3.2009, 22:51

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

Автор: maxdiver 17.3.2009, 23:09

KasMP Цитата Особенно правилен перебор "симметричных" вариантов ... Как от них избавиться?? А чем они плохи? Нам же надо найти просто любую раскраску. Если ты имеешь в виду оптимизацию, то она вряд ли сильно спасёт (раскрасок вообще 4^N, а с учётом не-симметричности будет в 2 раза меньше), да и непонятно, как избавить перебор от них. Цитата Есть мнение, что рекурсией можно пользоваться тогда, когда нужна наглядность, маленькое время написания и простота самого процесса написания, а производительность некритична (и что вообще рекурсию используют неумеющие программировать люди); а нормальные программы лучше писать без рекурсии. Поэтому мне не нравится рекурсия. Хотя, с другой стороны, если даже в программе у нас не будет рекурсии в явном виде, то в нашем случае в памяти навряд ли что-то изменится: все равно надо помнить цвета предыдущих вершин в текущей "итерации", все равно будет создаваться что-то типа дерева рекурсии (правильно назвала?) и его глубина останется такой же. Я же правильно думаю  ? Т.е. пытаться не использовать рекурсию в данном случае бессмысленно  ? Ну да, если мы хотим написать рекурсивный переборный раскрасок, то нет никакого смысла пытаться написать его так, чтобы _синтаксически_ не было рекурсии. Хотя, впрочем, такая оптимизация иногда сильно помогает - избавление от рекурсии на уровне языка, замена её ручным моделированием рекурсии (со стеком). Но опять же, код усложнится и станет менее понятным, а какой прирост скорости мы получим взамен - ещё неизвестно. Цитата Почему  ? [про линейное программирование]  Ну потому что вместо ясной задачи на графе мы получаем задачу 0-1-ЛП, которую надо как-то решать. Наверно, этому посвящены кучи теории, но чтобы написать что-то, надо всё это перелопатить  Да и вообще, у меня есть сомнения, что по скорости этот метод вообще может быть быстрее других. Цитата Ну, понятно, что для проверки больше 20-30 никто не возьмет... Но для порядка пусть их будет 1024    . Разброс нехилый  Для 20-30, думаю, и самый простой перебор будет укладываться. А вот для 1024 и хоть немного сложного графа - это заставит его задуматься весьма надолго  Для 1024, наверно, уже вообще нет смысла пытаться применять точные алгоритмы раскраски...

Автор: KasMP 17.3.2009, 23:31

Цитата(maxdiver @  17.3.2009,  23:09 ) А чем они плохи? Нам же надо найти просто любую раскраску. Если раскраска хорошая, то ничем - мы ее нашли и ура  . А если она плохая?? Мы вернемся на уровень вверх, потом через несколько шагов попадем в "симметричную" плохую, потом снова  ... Цитата(maxdiver @  17.3.2009,  23:09 ) Ну да, если мы хотим написать рекурсивный переборный раскрасок, то нет никакого смысла пытаться написать его так, чтобы _синтаксически_ не было рекурсии. Хотя, впрочем, такая оптимизация иногда сильно помогает - избавление от рекурсии на уровне языка, замена её ручным моделированием рекурсии (со стеком). Но опять же, код усложнится и станет менее понятным, а какой прирост скорости мы получим взамен - ещё неизвестно. Наверно, это зависит от кол-ва переменных в рекурсивной ф-ии. В любом случае, даже при ф-ии с одной переменной 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 Цитата(maxdiver @  17.3.2009,  23:09 ) А вот для 1024 и хоть немного сложного графа - это заставит его задуматься весьма надолго Тогда пусть 1<n<=100  . Здесь тоже есть, что посчитать.

Автор: KasMP 21.3.2009, 23:11

В принципе мой перебор работает и дает правильные результаты, но в каком-то месте не хватает выхода из рекурсии: после того, как найден правильный вариант, рекурсия еще несколько раз закручивается и раскручивается, еще проверяет все на бог знает сколько раз. Код bool Paint (GRAPH *graph, short i) {     short n = graph->n;     if (AnotherColorExists(graph,i)) {         ++(graph->color[i]);         for (short k=0; k<i; k++) {             if ( Edge(graph,i,k) && SameColor(graph,i,k) ) {                 Paint (graph,i);             }         }         if ( i+1 < n ) {             graph->color[i+1] = 0;             Paint(graph,i+1);         }         else             return (true);     }     else {         if ( i > 2 ) {             graph->color[i]=0;             Paint(graph,i-1);         }         else             return (false);     } } Есть ощущение, что вместо вызовов типа Код Paint (graph,i); надо использовать более ... направляющие варианты: Код if ( Paint (graph,i); )     return (что-то); else     return (противоположное); Добавлено через 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

Автор: maxdiver 22.3.2009, 00:00

Достаточно необычно перебор написан, но конкретно по вопросу - видимо, стоит везде написать так: Код if ( Paint (graph,i) )    return true; А иначе (если вернулось false) всё будет продолжаться перебираться дальше.

Автор: KasMP 22.3.2009, 00:07

Цитата(maxdiver @  22.3.2009,  00:00 ) Достаточно необычно перебор написан В смысле плохо? Что ты имеешь в виду  ? Цитата(maxdiver @  22.3.2009,  00:00 ) видимо, стоит везде написать так: Я думала об этом... Сейчас додумаю эту мысль до конца  . Спасибо    . Добавлено через 8 минут и 44 секунды Код if ( i+1 < n ) Сюда мы попадаем после проверки с "+" результатом. Если условие выполняется, то это значит, что еще есть незакрашенные вершины, что надо еще сходить в i+1 вершину..; если неверно, то это конец (закрашивать больше нечего, все уже хорошо) и мы можем выйти. Добавлено через 11 минут и 42 секунды Код if ( i > 2 ) Сюда мы попадаем, когда узнаем, что цветов для этой вершины больше нет. Ну мы и хотим узнать, есть ли смысл подниматься в i-1 и пытаться перекрасить ее... Если i-1 - первая вершина, то нет смысла перекрашивать первую вершину в другой цвет и проверять симметричные комбинации - уходим. Если вершина где-то посередине, то можно посмотреть и поискать.

Автор: maxdiver 22.3.2009, 00:19

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

Автор: KasMP 22.3.2009, 00:20

Цитата(KasMP @  22.3.2009,  00:07 ) то можно посмотреть и поискать не забыв при этом обнулить следующие вершины Добавлено через 6 минут и 14 секунд Цитата(maxdiver @  22.3.2009,  00:19 ) и если нарушает, то зачем-то вызываешь рекурсию от той же вершины Это делается для того, чтобы изменить цвет вершины, нарушившей правильность... Ведь все начинается с: Код if (AnotherColorExists(graph,i)) {         ++(graph->color[i]); Т.е. мы как раз и перебираем цвет вершины i. Что не так  ? Добавлено через 8 минут и 42 секунды Еще меня добивает, что при КАЖДОМ вызове ф-ии делается Код short n = graph->n; С одной стороны, логично сделать число вершин графа глобальной переменной, с другой - не хочется нарушать целостность и самодостаточность ф-ии и структуры .

Автор: KasMP 22.3.2009, 00:55

Цитата(KasMP @  21.3.2009,  23:11 ) В принципе мой перебор работает и дает правильные результаты Это большая неправда. В очевидном случае Цитата 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 он путается... Сейчас найдем его  . Добавлено через 11 минут и 5 секунд Все-таки правильнее так: Код if ( Paint (graph,i) )     return (true); else     return (false); Добавлено через 12 минут и 58 секунд Осталось нарисовать и раскрасить  .

Автор: esperanto 23.3.2009, 00:15

Цитата(KasMP @ 13.3.2009,  22:37)   Добавлено @ 22:39 Говорят, эта задача относится к классу NP-полных задач... Т.е. нет лучшего алгоритма решения, чем просто перебор  .  Нет.

Автор: KasMP 23.3.2009, 06:31

Цитата(esperanto @  23.3.2009,  00:15 ) Нет.  esperanto, это одинокое "нет" не добавляет никакой пользы. Можно подробнее  ? А еще у нас есть замечательная Цитата(maxdiver @  14.3.2009,  22:10 ) цитата из авторитетной книги "Вычислительные машины и труднорешаемые задачи" Гэри и Джонсона:

Автор: maxdiver 23.3.2009, 13:26

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

Автор: KasMP 23.3.2009, 14:27

Цитата(maxdiver @  23.3.2009,  13:26 ) Ну, вероятно, имелось в виду, что NP-полнота не обязательно означает только переборное решение. Даже тут где-то приводилось сведЕние этой задачи к другим, например, линейное 0-1-программирование. Для них могут быть свои алгоритмы, работающие не за полиномиальное время (как, например, для линейного программирования - симплекс - за O(2^N) (или даже больше?)), но не имеющие ничего общего с перебором. Какое многообразие  ! Эх, сколько еще предстоит узнать мне, если я не сверну с пути программиста ... Добавлено через 4 минуты и 33 секунды Цитата(KasMP @  22.3.2009,  00:55 ) Все-таки правильнее так: Код if ( Paint (graph,i) )     return (true); else     return (false); Кошмар какой  ! и не поправил никто  ! Не лучше ли просто Код return ( Paint (graph,i) )

Автор: KasMP 28.3.2009, 21:29

Ребята, а разве Код if ( Paint (graph,i) )     return (true); else     return (false); и Код return ( Paint (graph,i) ); не одно и то же ?! Почему-то в первом случае работает правильно, а во втором - нет...

Автор: maxdiver 28.3.2009, 23:05

Одно

Автор: KasMP 28.3.2009, 23:07

Цитата(maxdiver @  28.3.2009,  23:05 ) Одно Я так же думаю, но если заменить первое на второе, то ф-я работает неправильно    ...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)