Проблема гамильтонового пути

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

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

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

Скидки

Сведение от проблемы пути к проблеме цикла

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

С одной стороны, проблема гамильтонова пути для графа G может быть связана с проблемой гамильтонова цикла в графе H, полученном из G путем добавления новой универсальной вершины x , соединяющей x со всеми вершинами G . Таким образом, поиск гамильтонова пути не может быть значительно медленнее (в худшем случае, в зависимости от количества вершин), чем поиск гамильтонова цикла.
В другом направлении проблема гамильтонова цикла для графа G эквивалентна гамильтоновой задаче о путях в графе H, полученной добавлением терминальных ( степени -один) вершин s и t, прикрепленных соответственно к вершине v графа G и к v', расколотая копия v , которая дает v' ту же окрестность, что и v . Гамильтонов путь в H, проходящий через вершины ⁠ $s-v-x-\cdots -y-v'-t$ ⁠ соответствует гамильтонову циклу в G, проходящему через ⁠ $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]

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

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

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

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

Верификатор полиномиального времени

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

Ссылки

СМИ, связанные с проблемой гамильтонового пути, на Викискладе?

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

[:12-1] Перейти обратно: ^а ^б Сипсер, Майкл (2013). Введение в теорию вычислений (3-е изд.). Cengage Обучение. стр. 292–314.

[2] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Фриман и компания. п. 60.

[Held_1965_136–147-3] Перейти обратно: ^а ^б Хелд, М.; Карп, Р.М. (1965). «Построение дискретных алгоритмов динамического программирования» . Системный журнал IBM . 4 (2): 136–147. дои : 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 г.). «Решение задачи коммивояжера с помощью динамического программирования» . Журнал АКМ . 9 (1): 61–63. дои : 10.1145/321105.321111 . ISSN 0004-5411 . S2CID 15649582 .

[7] Держись, Майкл; Карп, Ричард М. (март 1962 г.). «Подход динамического программирования к задачам секвенирования» . Журнал Общества промышленной и прикладной математики . 10 (1): 196–210. дои : 10.1137/0110015 . ISSN 0368-4245 .

[8] Бьорклунд, Андреас (октябрь 2010 г.). «Детерминантные суммы для ненаправленной гамильтоновости» . 2010 51-й ежегодный симпозиум IEEE по основам информатики . IEEE. стр. 173–182. arXiv : 1008.0541 . дои : 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 , получено 7 октября 2023 г.

[10] Адлеман, Леонард (ноябрь 1994 г.), «Молекулярные вычисления решений комбинаторных задач», Science , 266 (5187): 1021–1024, Бибкод : 1994Sci...266.1021A , CiteSeerX 10.1.1.54.2565 , doi : 10.1126/science .7973651 , JSTOR 2885489 , PMID 7973651 .

[oltean_hamiltonian2-11] Михай Олтян (2006). Световое устройство для решения гамильтоновой проблемы пути . Нетрадиционные вычисления. Springer LNCS 4135. стр. 217–227. arXiv : 0708.1496 . дои : 10.1007/11839132_18 .

[12] «Доказательство того, что существование пути Гамильтона в двудольном графе NP-полно» . Обмен стеками в области компьютерных наук . Проверено 18 марта 2019 г.

[13] Гэри, MR ; Джонсон, Д.С .; Стокмейер, Л. (1974), «Некоторые упрощенные NP-полные задачи», Proc. 6-й симпозиум ACM по теории вычислений (STOC '74) , стр. 47–63, doi : 10.1145/800119.803884 , S2CID 207693360 .

[14] Плесник, Дж. (1979), «NP-полнота проблемы гамильтонова цикла в плоских орграфах со степенью, ограниченной двумя» (PDF) , Information Processing Letters , 8 (4): 199–201, doi : 10.1016/0020-0190 (79)90023-1 .

[15] Акияма, Таканори; Нисидзеки, Такао ; Сайто, Нобудзи (1980–1981), «NP-полнота проблемы гамильтонова цикла для двудольных графов», Journal of Information Processing , 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] Буро, Майкл (2001), «Простые эндшпили амазонок и их связь со схемами Гамильтона в кубических графах подсеток» (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-связных плоских графов», Journal of Algorithms , 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), «О сложности аргумента четности и других неэффективных доказательствах существования», Journal of Computer and System Sciences , 48 (3): 498–532, CiteSeerX 10.1.1.321.7008 , doi : 10.1016/S0022-0000(05)80063-7 , МР 1279412 .

[:0-22] Перейти обратно: ^а ^б ^с Бун, Марк (ноябрь 2022 г.). «Теория вычислений Бостонского университета» (PDF) .

[23] Бретчер, А. (5 февраля 2021 г.). «Конспекты лекций 7-й недели Университета Торонто CSCC63» (PDF) .

[24] Бан, Джун Хо. «Обзор сети на кристалле» . Калифорнийский университет в Ирвайне .

[25] Сатиш, Э.Г. (2022). «Сравнительный анализ производительности топологии маршрутизации для архитектуры NoC» . Новые исследования в области вычислений, информации, связи и приложений . Конспект лекций по электротехнике. Том. 790. стр. 431–440. дои : 10.1007/978-981-16-1342-5_34 . ISBN 978-981-16-1341-8 – через Спрингер.

[26] Бахребар, П.; Струбандт, Д. (2014). «Улучшение методов маршрутизации на основе гамильтона для внутрикристальных сетей: подход модели поворота». Конференция и выставка «Проектирование, автоматизация и испытания в Европе», 2014 г .: 1–4 – через IEEE.

[27] Гарсиэль, Тали; Ирландец, Пол (5 августа 2011 г.). «Как работают браузеры» .

[28] Аркин, Эстер М.; Митчелл, Джозеф С.Б.; Держись, Мартин; Скиена, Стивен С. «Гамильтоновы триангуляции для быстрого рендеринга» (PDF) . Факультет компьютерных наук Университета Стоуни-Брук .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]