测试Hamiltonian路径查找器实现

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，并且没有来自甲到d（长度0）连接。

该网络中的最大长度路径是E-> D-> A-> C-> B。它的总长度是2 + 3 + 3 + 3 = 11。我相信贪婪算法能够在这种情况下找到最好的解决方案，并且它可能很明显是最好的解决方案。

Answer 1

正如你已经阅读了哈密顿路径上的Wiki条目，你应该已经注意到找到哈密尔顿路径是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 

贪心算法ABCDEF找到路径与21的总长度，而最佳路径ACBEDF总长度为22（其中更多长度相同）。

如果你的算法工作方式不同，它可能适用于这个例子，但是如果它是贪婪的，它仍然会有一个反例。发布你的代码，如果是这样的话，你有兴趣。