c++ - 不规则网格和哈密顿路径

我有个问题。有没有一种有效的方法来获取网格图中两个节点之间的汉密尔顿路径，而忽略了一些预定义的节点？

例如。 (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/