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

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 - но это мало что меняет). Этот единственный факт говорит о том, что жадный алгоритм не даст вам оптимального решения проблемы.

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

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

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

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

(b) создает узел степени = 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

Жадный алгоритм находит путь A-B-C-D-E-F общей длиной 21, тогда как оптимальный путь - A-C-B-E-D-F общей длиной 22 (их больше с такой же длиной).

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