Задача о гамильтоновом пути

Задача нахождения цикла через все вершины графа

Проблема гамильтонового пути — это тема, обсуждаемая в областях теории сложности и теории графов . Она решает, содержит ли ориентированный или неориентированный граф G гамильтонов путь , путь, который посещает каждую вершину в графе ровно один раз. В задаче могут быть указаны начало и конец пути , в этом случае должны быть идентифицированы начальная вершина s и конечная вершина t . ^[1]

Задача о гамильтоновом цикле похожа на задачу о гамильтоновом пути, за исключением того, что она спрашивает, содержит ли заданный граф гамильтонов цикл . Эта задача также может указывать начало цикла. Задача о гамильтоновом цикле является частным случаем задачи о коммивояжере , полученной путем установки расстояния между двумя городами равным единице, если они соседние, и двум в противном случае, и проверки того, что общее пройденное расстояние равно n. Если это так, то маршрут является гамильтоновым циклом.

Задача о гамильтоновом пути и задача о гамильтоновом цикле относятся к классу NP-полных задач, как показано в книге Майкла Гэри и Дэвида С. Джонсона «Компьютеры и неразрешимость: руководство по теории NP-полноты» и в списке Ричарда Карпа из 21 NP-полной задачи . ^{[2] [3]}

Скидки

Сведение от задачи о пути к задаче о цикле

Задачи нахождения гамильтонова пути и гамильтонова цикла можно связать следующим образом:

• В одном направлении задача о гамильтоновом пути для графа G может быть связана с задачей о гамильтоновом цикле в графе H, полученном из G добавлением новой универсальной вершины x , соединяющей x со всеми вершинами G. Таким образом, нахождение гамильтонова пути не может быть значительно медленнее (в худшем случае, как функция числа вершин), чем нахождение гамильтонова цикла.
• В другом направлении задача о гамильтоновом цикле для графа G эквивалентна задаче о гамильтоновом пути в графе H, полученном путем добавления конечных ( степени -1) вершин s и t, присоединенных соответственно к вершине v графа G и к v', расщепленной копии v , которая дает v' ту же окрестность, что и v . Гамильтонов путь в H, проходящий через вершины ⁠ ⁠, ${\displaystyle s-v-x-\cdots -y-v'-t}$ соответствует гамильтонову циклу в G, проходящему через ⁠ ⁠ ${\displaystyle v-x-\cdots -y(-v)}$ . ^[4]

Алгоритмы

Грубая сила

Чтобы решить, имеет ли граф гамильтонов путь, нужно проверить каждый возможный путь во входном графе G. Существует n ! различных последовательностей вершин, которые могут быть гамильтоновыми путями в данном n- вершинном графе (и являются таковыми в полном графе ), поэтому алгоритм поиска методом перебора , который проверяет все возможные последовательности, будет очень медленным.

Частичные пути

Ранним точным алгоритмом для поиска гамильтонова цикла на ориентированном графе был перечислительный алгоритм Мартелло. ^[3] Процедура поиска Фрэнка Рубина ^[5] делит ребра графа на три класса: те, которые должны быть на пути, те, которые не могут быть на пути, и неопределенные. По мере продолжения поиска набор правил принятия решений классифицирует неопределенные ребра и определяет, следует ли остановить или продолжить поиск. Ребра, которые не могут быть на пути, могут быть исключены, поэтому поиск становится все меньше. Алгоритм также делит граф на компоненты, которые могут быть решены по отдельности, что значительно уменьшает размер поиска. На практике этот алгоритм по-прежнему является самым быстрым.

Динамическое программирование

Также, динамический алгоритм программирования Беллмана, Хелда и Карпа может быть использован для решения проблемы за время O( n ² 2 ⁿ ). В этом методе определяется для каждого набора вершин S и каждой вершины v в S , существует ли путь, который охватывает точно вершины в S и заканчивается в v . Для каждого выбора S и v путь существует для ( S , v ) тогда и только тогда, когда у v есть сосед w такой, что путь существует для ( S − v , w ), который можно найти из уже вычисленной информации в динамической программе. ^{[6] [7]}

Монте-Карло

Андреас Бьёрклунд предложил альтернативный подход, использующий принцип включения-исключения , чтобы свести задачу подсчета числа гамильтоновых циклов к более простой задаче подсчета, подсчета циклических покрытий, которая может быть решена путем вычисления определенных матричных определителей. Используя этот метод, он показал, как решить задачу гамильтоновых циклов в произвольных графах с n вершинами с помощью алгоритма Монте-Карло за время O(1,657 ⁿ ); для двудольных графов этот алгоритм может быть дополнительно улучшен до времени O (1,415 ⁿ ). ^[8]

Откат назад

Для графов максимальной степени три тщательный поиск с возвратом может найти гамильтонов цикл (если он существует) за время O(1,251 ⁿ ). ^[9]

Булева выполнимость

Гамильтоновы пути можно найти с помощью решателя SAT . Гамильтонов путь является NP-полным, что означает, что его можно свести к задаче 3-SAT . В результате, нахождение решения задачи Гамильтонов путь эквивалентно нахождению решения для 3-SAT.

Нетрадиционные методы

Из-за сложности решения задач гамильтоновых путей и циклов на обычных компьютерах, они также изучались в нетрадиционных моделях вычислений. Например, Леонард Адлеман показал, что задача гамильтоновых путей может быть решена с использованием ДНК-компьютера . Используя параллелизм, присущий химическим реакциям, задача может быть решена с использованием ряда этапов химической реакции, линейно зависящих от числа вершин графа; однако для участия в реакции требуется факториальное число молекул ДНК. ^[10]

Также было предложено оптическое решение гамильтоновой проблемы. ^[11] Идея состоит в том, чтобы создать графоподобную структуру из оптических кабелей и светоделителей, через которые проходит свет, чтобы построить решение проблемы. Слабым местом этого подхода является требуемое количество энергии, которое экспоненциально зависит от числа узлов.

Сложность

Задача поиска гамильтонова цикла или пути находится в FNP ; аналогичная задача решения заключается в проверке существования гамильтонова цикла или пути. Направленные и ненаправленные задачи гамильтонова цикла были двумя из 21 NP-полных задач Карпа . Они остаются NP-полными даже для специальных видов графов, таких как:

• двудольные графы , ^[12]
• неориентированные планарные графы максимальной степени три, ^[13]
• ориентированные планарные графы с полустепенью захода и исхода не более двух, ^[14]
• безмостовые неориентированные планарные 3- регулярные двудольные графы ,
• 3-связные 3-регулярные двудольные графы, ^[15]
• подграфы графа квадратной сетки , ^[16]
• кубические подграфы графа квадратной сетки. ^[17]

Однако для некоторых специальных классов графов задача может быть решена за полиномиальное время:

• Четырехсвязные планарные графы всегда являются гамильтоновыми согласно результату Тутта , и вычислительная задача нахождения гамильтонова цикла в этих графах может быть выполнена за линейное время ^[18] путем вычисления так называемого пути Тутта.
• Тутте доказал этот результат, показав, что каждый 2-связный планарный граф содержит путь Тутте. Пути Тутте, в свою очередь, могут быть вычислены за квадратичное время даже для 2-связных планарных графов, ^[19] что может быть использовано для поиска гамильтоновых циклов и длинных циклов в обобщениях планарных графов.

Объединяя все эти условия, остается открытым вопрос, должны ли 3-связные 3-регулярные двудольные планарные графы всегда содержать гамильтонов цикл, и в этом случае задача, ограниченная этими графами, не может быть NP-полной; см. гипотезу Барнетта .

В графах, в которых все вершины имеют нечетную степень, аргумент, связанный с леммой о рукопожатии, показывает, что число гамильтоновых циклов через любое фиксированное ребро всегда четное, поэтому если задан один гамильтонов цикл, то должен существовать и второй. ^[20] Однако нахождение этого второго цикла, похоже, не является простой вычислительной задачей. Пападимитриу определил класс сложности PPA для инкапсуляции таких проблем, как эта. ^[21]

Полиномиальный верификатор времени

Предложенное решение {s,w,v,u,t} образует допустимый гамильтонов путь в графе G.

Задача о гамильтоновом пути является NP-полной , что означает, что предлагаемое решение может быть проверено за полиномиальное время . ^[1]

Алгоритм верификатора для гамильтонова пути будет принимать в качестве входных данных граф G, начальную вершину s и конечную вершину t. Кроме того, верификаторам требуется потенциальное решение, известное как сертификат , c. Для задачи о гамильтоновом пути c будет состоять из строки вершин, где первая вершина является началом предлагаемого пути, а последняя — концом. ^[22] Алгоритм определит, является ли c допустимым гамильтоновым путем в G, и если да, то примет.

Чтобы решить это, алгоритм сначала проверяет, что все вершины в G появляются ровно один раз в c. Если эта проверка проходит, далее алгоритм гарантирует, что первая вершина в c равна s, а последняя вершина равна t. Наконец, чтобы проверить, что c является допустимым путем, алгоритм должен проверить, что каждое ребро между вершинами в c действительно является ребром в G. Если любая из этих проверок не пройдена, алгоритм отклонит. В противном случае он примет. ^{[22] [23]}

Алгоритм может проверить за полиномиальное время, появляются ли вершины в G один раз в c. Кроме того, требуется полиномиальное время для проверки начальных и конечных вершин, а также ребер между вершинами. Таким образом, алгоритм является полиномиальным верификатором для задачи о гамильтоновом пути. ^[22]

Приложения

Сети на чипе

Сети на кристалле (NoC) используются в компьютерных системах и процессорах , служащих для связи между компонентами на кристалле. ^[24] Производительность NoC определяется методом, который он использует для перемещения пакетов данных по сети . ^[25] Задача гамильтонового пути может быть реализована как метод на основе пути в многоадресной маршрутизации . Многоадресные алгоритмы на основе пути определят, существует ли гамильтонов путь от начального узла до каждого конечного узла, и отправят пакеты по соответствующему пути. Использование этой стратегии гарантирует маршрутизацию без взаимоблокировок и цепочек , повышая эффективность NoC. ^[26]

Компьютерная графика

Движки рендеринга — это форма программного обеспечения, используемого в компьютерной графике для генерации изображений или моделей из входных данных. ^[27] При рендеринге трехмерной графики обычным входом для движка является полигональная сетка . Время, необходимое для рендеринга объекта, зависит от скорости получения входных данных, то есть чем больше входные данные, тем больше время рендеринга. Однако для треугольных сеток время рендеринга может быть уменьшено в три раза. Это делается путем «упорядочивания треугольников таким образом, чтобы последовательные треугольники имели общую грань». ^[28] Таким образом, между каждым последовательным треугольником меняется только одна вершина. Этот порядок существует, если двойственный граф треугольной сетки содержит гамильтонов путь.

Ссылки

Медиа, связанные с проблемой гамильтоновой траектории на Wikimedia Commons

1. Sipser, Michael (2013). Введение в теорию вычислений (3-е изд.). Cengage Learning. стр. 292–314.
2. Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman and Company. стр. 60.
3. Held, M.; Karp, RM (1965). «Построение алгоритмов дискретного динамического программирования». IBM Systems Journal . 4 (2): 136–147. doi :10.1147/sj.42.0136. ISSN  0018-8670.
4. Редукция от гамильтонова цикла к гамильтонову пути
5. Рубин, Фрэнк (1974), «Процедура поиска путей и цепей Гамильтона», Журнал ACM , 21 (4): 576–80, doi : 10.1145/321850.321854 , S2CID  7132716
6. Беллман, Ричард (январь 1962 г.). «Решение проблемы коммивояжера с помощью динамического программирования». Журнал ACM . 9 (1): 61–63. doi : 10.1145/321105.321111 . ISSN  0004-5411. S2CID  15649582.
7. Хелд, Майкл; Карп, Ричард М. (март 1962 г.). «Подход динамического программирования к задачам последовательности». Журнал Общества промышленной и прикладной математики . 10 (1): 196–210. doi :10.1137/0110015. ISSN  0368-4245.
8. Бьорклунд, Андреас (октябрь 2010 г.). «Определяющие суммы для ненаправленной гамильтоновости». 2010 IEEE 51-й ежегодный симпозиум по основам компьютерной науки . IEEE. стр. 173–182. arXiv : 1008.0541 . doi :10.1109/focs.2010.24. ISBN 978-1-4244-8525-3.
9. Ивама, Казуо; Накашима, Такуя (2007), Лин, Гохуэй (ред.), "Улучшенный точный алгоритм для кубического графа TSP", Вычисления и комбинаторика , Конспект лекций по информатике, т. 4598, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 108–117, doi :10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1, получено 2023-10-07
10. Адлеман, Леонард (ноябрь 1994 г.), «Молекулярное вычисление решений комбинаторных задач», Science , 266 (5187): 1021–1024, Bibcode : 1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565 , doi : 10.1126/science.7973651, JSTOR  2885489, PMID  7973651 .
11. Михай Олтеан (2006). Устройство на основе света для решения задачи о гамильтоновом пути . Нетрадиционные вычисления. Springer LNCS 4135. С. 217–227. arXiv : 0708.1496 . doi :10.1007/11839132_18.
12. "Доказательство того, что существование гамильтонового пути в двудольном графе является NP-полным". Computer Science Stack Exchange . Получено 2019-03-18 .
13. Garey, MR ; Johnson, DS ; Stockmeyer, L. (1974), «Некоторые упрощенные NP-полные задачи», Proc. 6th ACM Symposium on Theory of Computing (STOC '74) , стр. 47–63, doi :10.1145/800119.803884, S2CID  207693360.
14. Plesńik, J. (1979), «NP-полнота задачи гамильтонова цикла в планарных орграфах со степенью, ограниченной двумя» (PDF) , Information Processing Letters , 8 (4): 199–201, doi :10.1016/0020-0190(79)90023-1.
15. Акияма, Таканори; Нисидзеки, Такао ; Сайто, Нобудзи (1980–1981), «NP-полнота задачи гамильтонова цикла для двудольных графов», Журнал обработки информации , 3 (2): 73–76, MR  0596313.
16. Итай, Алон; Пападимитриу, Христос; Шварцфитер, Джейме (1982), «Пути Гамильтона в графах сетки», SIAM Journal on Computing , 4 (11): 676–686, CiteSeerX 10.1.1.383.1078 , doi : 10.1137/0211056 .
17. Buro, Michael (2001), «Простые эндшпили Amazons и их связь с гамильтоновыми схемами в кубических подсетчатых графах» (PDF) , Компьютеры и игры , Конспект лекций по информатике, т. 2063, стр. 250–261, CiteSeerX 10.1.1.40.9731 , doi :10.1007/3-540-45579-5_17, ISBN  978-3-540-43080-3.
18. Чиба, Норисиге; Нисидзеки, Такао (1989), «Проблема гамильтонова цикла разрешима за линейное время для 4-связных планарных графов», Журнал алгоритмов , 10 (2): 187–211, doi :10.1016/0196-6774(89)90012-6
19. Шмид, Андреас; Шмидт, Йенс М. (2018), «Вычисление путей Тутте», Труды 45-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'18), которые будут опубликованы.
20. Томасон, АГ (1978), «Гамильтоновы циклы и графы с уникальной раскраской рёбер», Успехи в теории графов (Кембриджская комбинаторная конференция, Тринити-колледж, Кембридж, 1977), Анналы дискретной математики, т. 3, стр. 259–268, doi :10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, МР  0499124.
21. Пападимитриу, Христос Х. (1994), «О сложности аргумента четности и других неэффективных доказательствах существования», Журнал компьютерных и системных наук , 48 (3): 498–532, CiteSeerX 10.1.1.321.7008 , doi :10.1016/S0022-0000(05)80063-7, MR  1279412 .
22. Бан, Марк (ноябрь 2022 г.). «Теория вычислений Бостонского университета» (PDF) .
23. Бретшер, А. (5 февраля 2021 г.). «Конспект лекций 7-й недели CSCC63 Университета Торонто» (PDF) .
24. Бан, Джун Хо. «Обзор сети на кристалле». Калифорнийский университет в Ирвайне .
25. Сатиш, Э.Г. (2022). «Сравнительный анализ производительности топологии маршрутизации для архитектуры NoC». Новые исследования в области вычислений, информации, связи и приложений . Конспект лекций по электротехнике. Том 790. С. 431–440. doi :10.1007/978-981-16-1342-5_34. ISBN 978-981-16-1341-8– через Springer.
26. Бахребар, П.; Строобандт, Д. (2014). «Улучшение методов маршрутизации на основе гамильтониана для сетей на кристалле: подход с использованием модели очередности». Конференция и выставка «Проектирование, автоматизация и тестирование в Европе» 2014 г .: 1–4 – через IEEE.
27. Гарсиэль, Тали; Айриш, Пол (5 августа 2011 г.). «Как работают браузеры».
28. Аркин, Эстер М.; Митчелл, Джозеф С.Б.; Хелд, Мартин; Скиена, Стивен С. «Гамильтоновы триангуляции для быстрого рендеринга» (PDF) . Кафедра компьютерных наук Университета Стоуни-Брук .