我正在尝试使用DFS解决knight tour problem。我生成了图表(在本例中,我有5x5矩阵):
{
0: set([11, 7]),
1: set([8, 10, 12]),
2: set([9, 11, 5, 13]),
3: set([12, 14, 6]),
4: set([13, 7]),
5: set([16, 2, 12]), 6: set([17, 3, 13, 15]), 7: set([0, 4, 10, 14, 16, 18]), 8: set([19, 1, 11, 17]), 9: set([2, 12, 18]), 10: set([1, 17, 21, 7]), 11: set([0, 2, 8, 18, 20, 22]), 12: set([1, 3, 5, 9, 15, 19, 21, 23]), 13: set([2, 4, 6, 16, 22, 24]), 14: set([23, 17, 3, 7]), 15: set([12, 22, 6]), 16: set([23, 7, 5, 13]), 17: set([6, 8, 10, 14, 20, 24]), 18: set([9, 11, 21, 7]), 19: set([8, 12, 22]), 20: set([17, 11]), 21: set([10, 12, 18]),
22: set([19, 11, 13, 15]),
23: set([16, 12, 14]),
24: set([17, 13])
}
然后我试图调用DFS来找到长度为25的路径(每个正方形都已到达)。为此,我跟踪当前路径,将其与所需的长度进行比较,如果未递归到达,则跨越所有相邻的DFS。如果没有未经检查的邻居(我们到达了死胡同,但仍有正方形应该到达),我将从路径中删除最后一个元素。在
^{pr2}$我遗漏了一些显而易见的东西,因为在我的例子中,它找不到完整的路径,并且被[0, 11, 2, 9, 12, 1, 8, 19, 22, 13, 4, 7, 10, 17, 6, 3, 14, 23, 16]
卡住了。你知道我的错误在哪里吗?在
你没有回溯,所以你的算法最终会被困在一条无法工作的路径上(除非它幸运地第一次得到了结果)。下面是一个稍微简单一点的实现:
注意,如果递归调用返回了truth-y(即找到了完整的路径),则只返回
path
,否则它将删除该邻居并继续检查其他邻居的可能路径。在这是另一个很好的补充版本,这就是Jon的另一个问题:
称为
knightTour(0, 25, [])
,结果是[0, 11, 2, 9, 12, 1, 8, 19, 22, 13, 4, 7, 10, 21, 18, 17, 6, 3, 14, 23, 16, 5, 15, 20, 24]
相关问题 更多 >
编程相关推荐