Нахождение гамильтонова пути и гамильтонова цикла

Question

У меня есть SimpleGraph в JGraphT и хотите знать, если есть

1. гамильтонов путь

2. гамильтонов цикл

И если он существует, я бы тоже хотел его получить.

Я только нашел TwoApproxMetricTSP а также HamiltonianCycle,

Но оба требуют полных графиков.

Одно очевидное решение состоит в том, чтобы добавить ребра в мой граф и сделать его взвешенным графом с весом добавленных ребер, настолько большим, что они не будут использоваться в пути.

Но это добавило бы много краев, которых я хотел бы избежать.

Есть ли лучший способ получить гамильтонову путь / цикл без самостоятельной реализации алгоритма?

Answer 1

Решение задачи "содержит ли граф гамильтонов цикл (HC)" является NP-полным. JGraphT не включает алгоритмы, которые работают с неполными графами, поэтому единственное решение - сделать граф завершенным, добавив ребра с достаточно большим весом. Тогда HC существует тогда и только тогда, когда вы найдете тур без каких-либо дорогих ребер, которые вы добавили. Обратите внимание, что в следующем выпуске (1.1.1) появился новый точный алгоритм (см. Ветку master, метод динамического программирования Held Karp). Этот алгоритм не масштабируется за пределы 32 вершин. Если у вас большой график, я бы рекомендовал использовать TwoApproxMetricTSP. Если вам действительно нужно решать графики (разумного размера), вам придется прибегнуть к линейному программированию. Также взгляните на TSP Solver Concorde. Для большинства приложений TSP я бы реализовал выделенную, высокоэффективную структуру данных, например, для хранения ребер / соседей в массиве целых чисел.