我有一个问题。在网格图中,是否有一种高效的方法可以获取两个节点之间的哈密顿路径,并留出一些预定义的节点?
例如 (4*3 网格图)
1 0 0 0
0 0 0 0
0 0 2 3
在这个网格中寻找连接1和2的哈密顿路径,但不包括3?似乎二分图是一种方法,但在您看来,最有效的方法是什么?问题本身是NP完全的。
我有一个问题。在网格图中,是否有一种高效的方法可以获取两个节点之间的哈密顿路径,并留出一些预定义的节点?
例如 (4*3 网格图)
1 0 0 0
0 0 0 0
0 0 2 3
没有必要排除那些预定义的节点:只需将它们视为已访问,您仍然可以将图形作为矩形网格图进行处理。如果效率很重要,我建议使用位集或位向量表示网格。
当网格这么小,4x3时,暴力方法是最快的。动态规划使其变慢,除非您有一个更大的图形(6x7+)。您还可以使用启发式算法来修剪搜索树,但同样,只有在图形更大之前才会有所帮助。