 |
Гамильтонов цикл и задача коммивояжера
|
|
|
|
Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот цикл также называется гамильтоновым.
Слово «гамильтонов» в этих определениях связано с именем известного ирландского математика У.Гамильтона, которым в 1859 году предложена следующая игра «Кругосветное путешествие». Каждой из двадцати вершин додекаэдра приписано название одного из крупных городов мира. Требуется, переходя от одного города к другому по ребрам додекаэдра, посетить каждый город в точности один раз и вернуться в исходный город.
Эта задача, очевидно, сводится к отысканию в графе додекаэдра (рис. 18) простого цикла, проходящего через каждую вершину этого графа.
Рис. 18. Граф додекаэдра и его гамильтонов цикл
Несмотря на внешнее сходство постановок, задачи распознавания эйлеровости и гамильтоновости графа принципиально различны. Легко узнать, является ли граф эйлеровым и, в случае положительного ответа, алгоритм Флёри позволяет достаточно быстро построить один из эйлеровых циклов. Ответить на вопрос, является ли данный граф гамильтоновым, как правило, очень трудно.
Практическое применение задача о поиске гамильтонова цикла в графе находит, например, в задачах распознавания образов. Там вершины графа соответствуют допустимым символам, а ребра соединяют те символы, которые могут быть соседними. Самый длинный путь в этом графе будет наилучшим кандидатом для правильной интерпритации. Поиск самого длинного пути или цикла тесно связан с задачей о гамильтонове цикле.
Хорошо известная задача коммивояжера состоит в следующем: коммивояжер должен посетить каждый из заданных городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов.
|
|
|
Математическая постановка этой задачи: в полном взвешенном графе требуется найти гамильтонов цикл минимального веса. Под весом цикла понимается сумма весов составляющих его ребер.
Конечно, для решения этой задачи существует простой алгоритм – полный перебор всех возможных вариантов. Однако, такой подход, как правило, неприемлем из-за чрезвычайно большого числа этих вариантов (если число городов равно n, то число всех возможных обходов nn). Поэтому вызывает интерес не просто алгоритм, а эффективный алгоритм.
Многие задачи, такие как задача коммивояжера, с вычислительной точки зрения представляются достаточно трудными. Для их решения до сих пор не найдено полиномиальных алгоритмов. Возможно, что таких алгоритмов не существует, но пока это не доказано.
5.4. Классы сложности P и NP
Будем рассматривать лишь задачи сформулированные в так называемом распознавательном варианте, когда решение задачи заключается в получении ответа «да» или «нет». Таковы, например, задачи распознавания изоморфизма, гамильтоновости, эйлеровости графов. На практике чаще требуется решить оптимизационную задачу, т.е. выбрать из множества допустимых решений одно, вес или стоимость которого минимальна. Например, найти минимальное остовное дерево. Каждой оптимизационной задаче можно сопоставить семейство ее распознавательных вариантов следующим образом: определить, существует ли решение с весом меньше некоторого c. Далее будем рассматривать только распознавательные задачи.
P– это класс распознавательных задач, каждая из которых может быть решена некоторым алгоритмом за полиномиальное время.
Понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи, так как, во-первых, полиномиальные алгоритмы действительно работают довольно быстро. Во-вторых, класс полиномиально разрешимых задач обладает естественными свойствами замкнутости: композиция двух полиномиальных алгоритмов (выход первого алгоритма подается на вход второго) также работает полиномиальное время.
|
|
|
Все рассмотренные выше задачи, независимо от того, установлена их принадлежность классу P или нет, обладают одним общим свойством: существует полиномиальный алгоритм, доказывающий, что имеет место ответ «да» по соответствующему входу задачи. Например, пусть задача состоит в выяснении, является ли граф гамильтоновым, и пусть поступающий на вход граф G гамильтонов, т.е. в графе G имеется гамильтонов цикл C. Тогда доказательство гамильтоновости графа G заключалось бы в проверке включения C Í G, что можно сделать за O (n) операций. Но, если граф не является гамильтоновым, то нельзя утверждать, что существует полиномиальное доказательство этого факта, так как для перебора всех возможных простых циклов потребуется O ((n (G)-1)!) операций.
Назовем проверяющим алгоритмом алгоритм A с двумя аргументами: первый аргумент - входная строка, а второй – сертификат. Алгоритм A с двумя аргументами допускает вход x, если существует сертификат y, для которого A (x, y)=1. Другими словами, алгоритм A проверяет задачу L, если для любого входа x задачи L найдется сертификат y, с помощью которого A сможет проверить, что в задаче L получен положительный ответ, а для входных данных, предполагающих отрицательный ответ, такого сертификата нет. Например, в задаче о гамильтоновом цикле сертификатом была последовательность вершин, образующая гамильтонов цикл.
NP - это класс всех распознавательных задач, для которых существуют проверяющие алгоритмы, работающие полиномиальное время, причем длина сертификата также ограничена некоторым полиномом.
Сокращение NP происходит от термина недетерминированно разрешимых за полиномиальное время, так как первоначально класс NP определялся с помощью недетерминированных вычислений.
Нетрудно видеть, что P 
NP. Действительно, если есть полиномиальный алгоритм, решающий задачу, то легко построить проверяющий алгоритм для той же задачи – проверяющий алгоритм может просто игнорировать свой второй аргумент(сертификат).
|
|
|
Список проблем третьего тысячелетия открывается вопросом P = NP? Большинство исследователей считают, что P ≠ NP. Интуитивно класс P можно представить себе как класс задач, которые можно быстро решить, а класс NP - как класс задач, которые можно быстро проверить. На практике решить самому задачу намного труднее, чем проверить готовое решение, особенно если время работы ограничено. Или можно считать, что в классе NP имеются задачи, которые нельзя решить за полиномиальное время.
Как оказалось из P ≠ NP следует, что ни одна из «трудных» задач не имеет полиномиального алгоритма, а из существования такого алгоритма для одной из них следует P = NP.
Изложение соответствующих результатов опирается на понятие сводимости одной задачи к другой, т.е. из решения одной задачи можно получить решение другой. Говоря неформально, задача Q сводится к задаче Q ', если задачу Q можно решить для любого входа, считая известным решение задачи Q ' для какого-то другого входа. Например, задача решения линейного уравнения сводится к задаче решения квадратного уравнения (линейное уравнение можно превратить в квадратное, добавив фиктивный старший член). Если задача Q сводится к задаче Q ', то любой алгоритм, решающий Q ', можно использовать для решения задачи Q.
Задача Q сводится к задаче Q ', если существует полиномиальный алгоритм F, который будучи примененным ко всякому входу x задачи Q, строит некоторый вход F (x) задачи Q ', и вход x имеет ответ «да» тогда и только тогда, когда ответ «да» имеет вход F (x).
Нетрудно показать, что если задача Q сводится к задаче Q ' и Q ' Î P, то и Q Î P. Действительно, пусть А – алгоритм решения задачи Q ' и полиномы P 1(n) и P 2(n) таковы, что O (P 1(n)) и O (P 2(n))– трудоемкости алгоритмов F и A соответственно. Рассмотрим теперь алгоритм B решения задачи Q, который состоит из двух этапов. На первом этапе вход x задачи Q преобразуется алгоритмом F во вход F (x) задачи Q '. На втором этапе алгоритм A применяется ко входу F (x). Согласно определению F, алгоритм A сообщит ответ «да» тогда и только тогда, когда ответ «да» имеет вход x, то есть алгоритм B действительно решает задачу Q. Выясним теперь его сложность. Если длина входа x равна n, то F (x) будет построен за время O (P 1(n)) и его длина – O (P 1(n)). Алгоритм A, будучи примененным ко входу F (x), затратит время O (P 2(P 1(n))). Таким образом, сложность алгоритма B есть O (P 1(n))+ O (P 2(P 1(n))). Поскольку суперпозиция и сумма полиномов также являются полиномом, то алгоритм B – полиномиальный.
|
|
|
Задачу Q назовем NP - полной, если Q Î NP и любая задача из NP сводится к Q. Очевидно, что если хотя бы одна NP - полная задача входит в P, то P = NP. Таким образом, гипотеза P ≠ NP означает, что NP - полные задачи не могут быть решены за полиномиальное время. Возможно, когда-нибудь будет найден полиномиальный алгоритм решения NP - полной задачи и тем самым доказано, что P = NP. Пока это никому не удалось, и поэтому доказательство NP -полноты некоторой задачи служит убедительным аргументом в пользу того, что она является практически неразрешимой.
В настоящее время известен значительный список NP - полных задач. Это и задача о поиске числа независимости, плотности графа, гамильтоновости, изоморфного подграфа.
5.5. Решение NP - полных задач
Допустим, доказано, что некоторая задача является NP - полной, то есть алгоритма с полиномиальным временем исполнения для ее решения при всех входных данных не существует. Однако, такую задачу всё равно надо решать. Существует три варианта решения:
- алгоритмы, эффективные для средних случаев задачи. Например, поиска с возвратом, где выполняются значительные отсечения;
- эвристические алгоритмы. Примером может служить жадный алгоритм. Для задачи коммивояжера он формулируется так: иди в ближайшую непройденную вершину. Эвристические алгоритмы позволяют быстро найти решение, но без гарантии, что это решение будет наилучшим;
- апроксимирующие алгоритмы, которые дают гарантию, что найденное решение будет отличаться от оптимального решения не более чем на определенную погрешность на любом входе задачи.
Упражнения.
1. Сформулируйте критерий существования эйлерова цикла для ориентированных графов.
2. Реализуйте алгоритм решающий задачу китайского почтальона.
3. Приведите пример, когда «жадный» алгоритм решения задачи коммивояжера дает далеко не оптимальное решение.
4. Разработайте алгоритм, который находит все циклы в графе. Оцените его трудоемкость.
|
|
|
