c++ - 如何找到一条路径访问尽可能多的顶点？

Question

给定一个正方形网格(无向图)，是否有任何方法可以找到一条路径，该路径将访问尽可能多的顶点。

每个顶点只能访问一次。这意味着路径将是汉密尔顿之旅(如果存在)，或者是最长的路径。

图中有一些墙。墙是一个顶点，没有边连接到邻居。

我有一个解决方案(在脑海中)，但它非常类似于找到所有路径并选择第一个访问了最多顶点的路径。

1. Find a path will visit all neighbors from given start vertex to the end (no way can go).

2. look back to the current path until the starting vertex, if there is any vertex has neighbors outside of the current path, process like step 1 from the found vertex and its new neighbors.

3. analysis and choose the longest path (has most vertices).

我找到了 similar problem ，不明白@Juho 是什么意思:

Choose a successor si to top(S), and try to find a path si−1⇝si avoiding vertices in F. If a path is found, insert the vertices on the path si−1⇝si to F.

我没有足够的声誉在那里添加评论。

我猜我的解决方案遇到了性能问题。有什么建议吗？

Answer 1

这更像是哈密顿路径问题。它是 NP 完全的，因此您需要进行详尽的搜索。让你的蛮力。我只能建议可以使用线程来缓解您的性能问题；在可用线程之间平均分配起始顶点。如果找到哈密顿路径，则终止，否则最长路径获胜。

算法本身只需要找到所有可能的路径。我可能有一种启发式方法，可以停止为似乎会产生不良结果的路径烦恼，但这意味着解决方案可能并不总是正确的。