我有一个问题。在网格图中，是否有一种高效的方法可以获取两个节点之间的哈密顿路径，并留出一些预定义的节点？
例如 (4*3 网格图)
1 0 0 0
0 0 0 0
0 0 2 3
在这个网格中寻找连接1和2的哈密顿路径，但不包括3？似乎二分图是一种方法，但在您看来，最有效的方法是什么？问题本身是NP完全的。
不规则网格和哈密顿路径
3
在这个网格中寻找连接1和2的哈密顿路径，但不包括3？似乎二分图是一种方法，但在您看来，最有效的方法是什么？问题本身是NP完全的。
- Arun Shyam
11
你的图形表示是什么？这些行是邻接表吗？ - user334856
我需要找到从编号为1（起点）的顶点到编号为2（终点）的哈密顿路径，但是路径中不能包含编号为3的顶点。 - Arun Shyam
这个图的连通性是什么？只有左右上下吗？还是包括对角线？所有边的权重都相等吗？ - user334856
一个例子是1--0--0--0
|
0--0--0--0
|
0--0--2 3这个例子展示了一种锯齿形的连接方式。 - Arun Shyam
7根据这篇论文，问题的陈述确实是NP完全问题（详见第2节，推论2 [第681页]）。 - collapsar
显示剩余6条评论
2个回答
0
删除您不需要包含的节点，并运行暴力算法以查找哈密顿路径。这将花费O（（n-h）！+ n）的时间，这是NP问题，其中h是删除的节点数，但这是您能做到的最好的。此外，要找到哈密顿路径，还有一种动态方法，但这也是指数级的（O（2 ^ n * n ^ 2））。
- Aditya
0
没有必要排除那些预定义的节点：只需将它们视为已访问，您仍然可以将图形作为矩形网格图进行处理。如果效率很重要，我建议使用位集或位向量表示网格。
当网格这么小，4x3时，暴力方法是最快的。动态规划使其变慢，除非您有一个更大的图形（6x7+）。您还可以使用启发式算法来修剪搜索树，但同样，只有在图形更大之前才会有所帮助。
- Miro Lehtonen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接