我正在尝试使用DFS解决骑士巡逻问题。我生成了我的图形(在这个例子中,我有一个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,则将其删除。如果没有未选中的邻居(我们到达了死胡同,但仍然有应该到达的方块),我会从路径中删除最后一个元素。
def knightTour(current, limit, path):
if len(path) == limit:
return path
path.append(current)
neighbors = graph[current]
if len(neighbors):
for i in neighbors:
if i not in set(path):
return knightTour(i, limit, path)
else:
path.pop()
return False
knightTour(0, 24, [])
我可能错过了一些明显的东西,因为在我的情况下,它找不到完整路径,卡在了[0,11,2,9,12,1,8,19,22,13,4,7,10,17,6,3,14,23,16]
。你知道我的错误在哪里吗?
return
了,而不是尝试所有路径。 - jonrsharpe