algorithm - 通过连接的组件找到一条路径，其中每个顶点都被恰好访问一次

Question

我有一个大的连接顶点图(一个连接的组件)，我正在寻找一条通过所有这些顶点的路径，但绝不会通过一个顶点两次。这并不总是可能的。例如，在以下示例中 from wikipedia ，很明显，没有路径访问每个顶点，其中没有顶点被访问超过一次:

但是如果稍微调整一下，让它有更多的边(连接)，那么有些路径可以通过每个顶点恰好一次。我对它进行了调整并对顶点进行编号以提供这样一条路径:

我的图表就像这张图，我知道有一条可能的路径。然而，它非常大(20,000 个顶点，每个顶点有 2 到 11 条边)。我实现了深度优先搜索和广度优先搜索，但图太大而无法找到路径(计算时间太长)。

---

所以我的问题是:是否有另一种算法可以解决这个问题，特别是比深度优先或广度优先搜索更有效？

这有点像旅行商问题，只是城市只能从特定的其他城市到达，并且这些城市之间的距离相等。

Answer 1

您描述的问题称为 Hamiltonian path problem (哈密顿路径是通过每个节点一次且恰好一次的路径)。不幸的是，这个问题已知是NP-hard，因此没有已知的多项式时间算法来解决这个问题。因此，您不太可能使用简单的广度优先搜索或深度优先搜索找到有效的解决方案。

有一个有点著名的动态规划算法来解决这个问题。如果在线搜索“Hamiltonian path DP”，您应该会找到有关该主题的一些很好的链接。