我有一个问题。是否有一种有效的方法来获取网格图中两个节点之间的哈密顿路径，而忽略一些预定义的节点？
例如。 (4*3格)
1 0 0 0
0 0 0 0
0 0 2 3
在此网格黑白顶点 1 和 2 中找到哈密顿路径，但不覆盖 3？看起来二分图是一种方法，但根据你的说法必须是最有效的方法。问题本身是 NP 完全的。
最佳答案
删除不需要包含的节点并运行蛮力算法以找到哈密顿路径。这将花费 O((n-h)!+n)，这是 NP，其中 h 是删除的节点数，但这是您能做的最好的。同样要找到哈密顿路径，有一种动态方法，但这也是指数的(O(2^n*n^2))
关于c++ - 不规则网格和哈密顿路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8638945/