1

我正在实现一种算法，该算法在有向图中找到最佳哈密顿路径。我已经实现了一个看起来运行良好的算法，但是我不完全确定在某些情况下是否存在细微的错误或其他问题。因此，我需要一些已知解决方案的不同网络，以检查我的实现是否也在按应有的方式解决它们。

由于 Wikipedia 暗示哈密顿路径只是无向图的适当术语，因此假设“哈密顿路径”是指在给定网络上访问每个节点一次且恰好一次的路径，无论是有向的还是其他的。

为简单起见，我们可以假设每个连接（或“边”）都有一个正整数值（或“长度”）。我们还可以假设没有节点与自身相连，并且在任何两个节点之间的每个方向上都不能有超过一条边。

我碰巧对总长度最长的路径感兴趣，因此“最佳”意味着最长，尽管如果我想要最短的总长度（如在传统 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。我相信贪心算法能够在这种情况下找到最佳解决方案，而且很明显它是最好的解决方案。

4

1 回答 1

0

当您阅读有关哈密顿路径的 Wiki 条目时，您应该已经注意到找到哈密顿路径是 NP 难的（准确地说，您要解决的是 TSP - 但这并没有太大变化）。这一事实表明，贪心算法不会为您提供问题的最佳解决方案。

如果你的贪心算法像

取按值/长度降序排列的边，

将边缘添加到构建中的路径，除非它

(a) 创建一个循环

(b) 在 path-in-construction 中创建一个 deg=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

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

如果您的算法工作方式不同，它可能适用于这个例子，但如果它是贪婪的，仍然会有一个反例。如果是这种情况并且您感兴趣，请发布您的代码。

于 2012-01-14T12:49:21.417 回答