WikiDer > Гамильтонова проблема пути

Hamiltonian path problem
Эта статья посвящена конкретной проблеме определения того, существует ли гамильтонов путь или цикл в данном графе. Общие концепции теории графов см. Гамильтонов путь.

в математический поле теория графов то Гамильтонова проблема пути и Проблема гамильтонова цикла проблемы с определением того, Гамильтонов путь (путь в неориентированном или ориентированном графе, который посещает каждую вершину ровно один раз) или гамильтонов цикл существует в данном график (будь то направленный или ненаправленный). Обе проблемы НП-полный.[1]

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

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

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

  • В одном направлении проблема гамильтонова пути для графа G эквивалентна проблеме гамильтонова цикла в графе H, полученном из G путем добавления новой вершины Икс и подключение Икс ко всем вершинам графа G. Таким образом, поиск гамильтонова пути не может быть значительно медленнее (в худшем случае, в зависимости от числа вершин), чем поиск гамильтонова цикла.
  • С другой стороны, проблема гамильтонова цикла для графа G эквивалентна задаче гамильтонова пути в графе H, полученном копированием одной вершины v графа G, v ', то есть позволяя v' иметь ту же окрестность, что и v, и добавив две фиктивные вершины первой степени и соединив их с вершинами v и v 'соответственно.[2]

Алгоритмы

Есть п! различные последовательности вершин, которые мощь быть гамильтоновыми путями в заданном п-вершинный граф (и находятся в полный график), так что поиск грубой силы Алгоритм, который проверяет все возможные последовательности, будет очень медленным. Ранним точным алгоритмом для поиска гамильтонова цикла на ориентированном графе был алгоритм перечисления Мартелло.[3] Процедура обыска Фрэнка Рубина[4] делит ребра графа на три класса: те, которые должны быть на пути, те, которые не могут быть на пути, и не определившиеся. По мере продолжения поиска набор правил принятия решений классифицирует нерешенные ребра и определяет, следует ли остановить или продолжить поиск. Алгоритм делит граф на компоненты, которые можно решить отдельно. Также динамическое программирование алгоритм Беллман, Хельд и Карп можно использовать для решения задачи за время O (п2 2п). В этом методе определяется для каждого набора S вершин и каждой вершины v в S, существует ли путь, который точно охватывает вершины в S и заканчивается в v. Для каждого выбора S и v, путь существует для (S,v) если и только если v есть сосед ш такой, что существует путь для (S − v,ш), который можно найти на основе уже вычисленной информации в динамической программе.[5][6]

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

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

Гамильтоновы пути и циклы можно найти с помощью SAT решатель.

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

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

Сложность

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

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

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

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

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

использованная литература

СМИ, связанные с Гамильтонова проблема пути в Wikimedia Commons

  1. ^ Майкл Р. Гарей и Дэвид С. Джонсон (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, ISBN 978-0-7167-1045-5 A1.3: GT37–39, стр. 199–200.
  2. ^ Сведение от гамильтонова цикла к гамильтонову пути
  3. ^ Мартелло, Сильвано (1983), "Перечислительный алгоритм для поиска гамильтоновых схем в ориентированном графе", Транзакции ACM на математическом ПО, 9 (1): 131–138, Дои:10.1145/356022.356030
  4. ^ Рубин, Франк (1974), "Процедура поиска путей и цепей Гамильтона", Журнал ACM, 21 (4): 576–80, Дои:10.1145/321850.321854
  5. ^ Беллман, Р. (1962), "Динамическое программирование решения задачи коммивояжера", Журнал ACM, 9: 61–63, Дои:10.1145/321105.321111.
  6. ^ Held, M .; Карп, Р.М. (1962), «Подход динамического программирования к задаче определения последовательности» (PDF), J. SIAM, 10 (1): 196–210, Дои:10.1137/0110015, HDL:10338.dmlcz / 103900.
  7. ^ Björklund, Андреас (2010), "Детерминантные суммы для неориентированной гамильтоничности", Proc. 51-й симпозиум IEEE по основам компьютерных наук (FOCS '10), стр. 173–182, arXiv:1008.0541, Дои:10.1109 / FOCS.2010.24, ISBN 978-1-4244-8525-3.
  8. ^ Ивама, Кадзуо; Накашима, Такуя (2007), "Улучшенный точный алгоритм для кубического графа TSP", Proc. 13-я ежегодная международная конференция по вычислениям и комбинаторике (COCOON 2007), Конспект лекций по информатике, 4598, стр. 108–117, CiteSeerX 10.1.1.219.1672, Дои:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.
  9. ^ Адлеман, Леонард (Ноябрь 1994 г.), «Молекулярное вычисление решений комбинаторных задач», Наука, 266 (5187): 1021–1024, Bibcode:1994Научный ... 266.1021A, CiteSeerX 10.1.1.54.2565, Дои:10.1126 / science.7973651, JSTOR 2885489, PMID 7973651.
  10. ^ Михай Олтеан (2006). Световое устройство для решения задачи о гамильтоновой траектории. Нетрадиционные вычисления. Springer LNCS 4135. С. 217–227. arXiv:0708.1496. Дои:10.1007/11839132_18.
  11. ^ «Доказательство того, что существование пути Гамильтона в двудольном графе NP-полно». Обмен стеками информатики. Получено 2019-03-18.
  12. ^ Гарей, М.; Джонсон, Д.С.; Штокмейер, Л. (1974), "Некоторые упрощенные NP-полные задачи", Proc. 6-й симпозиум ACM по теории вычислений (STOC '74), стр. 47–63, Дои:10.1145/800119.803884.
  13. ^ Плешник, J. (1979), «NP-полнота проблемы гамильтонова цикла в плоских орграфах со степенью два» (PDF), Письма об обработке информации, 8 (4): 199–201, Дои:10.1016/0020-0190(79)90023-1.
  14. ^ Акияма, Таканори; Нисизэки, Такао; Сайто, Нобуджи (1980–1981), "NP-полнота проблемы гамильтонова цикла для двудольных графов", Журнал обработки информации, 3 (2): 73–76, Г-Н 0596313.
  15. ^ Итаи, Алон; Пападимитриу, Христос; Szwarcfiter, Jayme (1982), "Пути Гамильтона в сеточных графах", SIAM Журнал по вычислениям, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, Дои:10.1137/0211056.
  16. ^ Бюро, Майкл (2000), «Простые эндшпиль амазонок и их связь со схемами Гамильтона в кубических подсеточных графах» (PDF), Конференция по компьютерам и играм, Конспект лекций по информатике, 2063, стр. 250–261, CiteSeerX 10.1.1.40.9731, Дои:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.
  17. ^ Чиба, Норишиге; Нишизеки, Такао (1989), "Проблема гамильтонова цикла линейно разрешима для четырехсвязных плоских графов", Журнал алгоритмов, 10 (2): 187–211, Дои:10.1016/0196-6774(89)90012-6
  18. ^ Шмид, Андреас; Шмидт, Йенс М. (2018), «Вычисление всех путей», Труды 45-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'18), чтобы появиться.
  19. ^ Томасон, А. Г. (1978), "Гамильтоновы циклы и однозначно раскрашиваемые ребра графы", Достижения в теории графов (Кембриджская комбинаторная конференция, Тринити-колледж, Кембридж, 1977), Анналы дискретной математики, 3, стр.259–268, Дои:10.1016 / S0167-5060 (08) 70511-9, ISBN 9780720408430, Г-Н 0499124.
  20. ^ Пападимитриу, Христос Х. (1994), "О сложности аргумента четности и других неэффективных доказательствах существования", Журнал компьютерных и системных наук, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, Дои:10.1016 / S0022-0000 (05) 80063-7, Г-Н 1279412.