Тестирование реализации поиска гамильтоновых путей

Question

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

Поскольку в Википедии подразумевается, что гамильтоновы пути являются только подходящим термином для неориентированных графов, предположим, что "гамильтоновый путь" означает путь, который посещает каждый узел один раз и ровно один раз в данной сети, направленный или иным образом.

Для простоты можно предположить, что каждое соединение (или "ребро") имеет положительное целочисленное значение (или "длину"). Можно также предположить, что ни один узел не связан с самим собой, и между любыми двумя узлами может быть не более одного ребра в каждом направлении.

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

Где или как я могу получить направленные сети, для которых был решен TSP? Было бы еще лучше, если бы существовало реальное и жадное (или другое эвристическое) решение. Сети должны быть достаточно большими, чтобы проводить информативный тест, но достаточно маленькими, чтобы я мог вручную проверить решение (если решение изначально неизвестно). Они должны быть достаточно топологически разнообразными, чтобы охватить как "простые", так и "проблемные" сети.

Для тех, кто ищет то же самое; лучшее, что у меня есть, это следующая сеть:

  A B C D E
A 0 1 2 0 1
B 1 0 0 0 1
C 0 3 0 1 2
D 4 0 0 0 0
E 1 0 0 2 0

Это список смежности, строки - это грани, а столбцы - места назначения. Числа являются длинами каждого ребра, а 0 указывают на отсутствие ребра. Например, 4 показывает, что длина ребра от D до A равна 4, и нет соединения от A до D (длина 0).

Максимальная длина пути в этой сети составляет E->D->A->C->B. Его общая длина составляет 2+3+3+3=11. Я полагаю, что жадный алгоритм способен найти лучшее решение в этом случае, и оказывается очевидным, что он является наилучшим возможным решением.

Answer 1

Когда вы прочитали статью в вики о гамильтоновом пути, вы должны были заметить, что найти гамильтоновый путь сложно с точки зрения NP (если быть точным, то, что вы решаете, это TSP - но это не сильно изменится). Этот единственный факт предполагает, что жадный алгоритм не даст вам оптимального решения проблемы.

Если ваш жадный алгоритм работает как

взять ребра в порядке убывания значения / длины,

добавить край к пути в конструкции, если это не

(а) создает цикл

(б) создает узел степени =3 в пути в строительстве

в противном случае пропустите это

вот минимальный контрпример, который я могу придумать, где жадность делает его неудачным:

  A B C D E F
A 0 5 4 0 0 0
B 5 0 5 0 4 0
C 4 5 0 1 0 0
D 0 0 1 0 5 4
E 0 4 0 5 0 5
F 0 0 0 4 5 0

Жадный алгоритм находит путь ABCDEF общей длиной 21, тогда как оптимальным является путь ACBEDF с общей длиной 22 (их больше с одинаковой длиной).

Если ваш алгоритм работает по-другому, он может хорошо работать в этом примере, но все равно будет контрпример, если он жадный. Разместите свой код, если это так, и вы заинтересованы.