python - 找出游戏板上两个正方形之间的最短距离

Question

我将游戏板上的路径存储在字典中，格式如下:

{1: [2,3,4], 2: [1,3,5], 3: [1,2,4], ...}

这意味着如果您在空间 1，则可以移动到空间 2、3 或 4，依此类推。每个键链接到列表中的至少两个值；许多有四个或更多。棋盘上共有 199 个空格。一个值得注意的问题是有时您可能会跳过一个空格，所以在...

{1:[2,3,4], 2:[3]}

...您可以选择 1 -> 2 -> 3，也可以直接选择 1 -> 3。

我想创建一种算法来找到任意两个正方形之间的最短距离。显而易见的想法是查找起始空格的键，然后取列表中的第一个数字，查找可能的空格，依此类推，当它遇到之前看到的数字时停止并返回到之前的列表或最终方 block (如果命中结果方 block 则存储路径和距离，完成后进行比较)。

不过，我对如何开始实现它知之甚少。 (如果只有两个步骤，我会使用嵌套循环，但显然这在这里行不通，因为我不知道它可能深入多少层)。

欢迎更好的解决方案或涉及其他数据结构的优化；我将数据存储在类似于这本字典的 CSV 文件中，因此我可以轻松地将其转换为其他格式，如果这样效果更好的话。

这是我正在使用的电路板图片的链接: http://goo.gl/Rasq6

编辑:好的，我正在尝试实现 Dijkstra 算法。这是我得到的:

  1 movedict, transdict = boardstruct.prepare_board()
  2 
  3 source = 87
  4 dest = 88
  5 
  6 dist = {}
  7 prev = {}
  8 for v in movedict.keys():
  9     dist[v] = float('inf')
 10     prev[v] = None
 11 
 12 dist[source] = 0
 13 q = movedict.keys()
 14 
 15 while q:
 16     smallest = float('inf')
 17     for i in q:
 18         dist_to = dist[i]
 19         if dist_to < smallest:
 20             smallest = dist_to
 21     print smallest
 22     u = q.pop(smallest)
 23     print u
 24 
 25     if dist[u] == float('inf'):
 26         break
 27 
 28     for v in movedict[u]:
 29         alt = dist[u] + 1 # distance = flat 1
 30         if alt < dist[v]:
 31             dist[v] = alt
 32             prev[v] = u
 33             # reorder queue?

(21 和 23 是我忘记删除的调试语句)

我正在使用来自维基百科 (http://en.wikipedia.org/wiki/Dijkstra's_algorithm#Pseudocode) 的伪代码，因为我找不到任何现有的实现来匹配我需要的数据格式(每一步都有固定的成本，因此距离不会存储在任何地方。

我知道我需要在最后重新排序队列，但我不确定如何。我也不明白第 25 行和第 26 行的用途(评论说“所有剩余的顶点都无法从源代码访问”——这是否只是在保证已经找到最佳路径时阻止它继续运行？)。我可能也搞砸了其他事情，所以如果你能看一下，我将不胜感激。

Answer 1

您所描述的是 shortest path problem .有几种方法可以解决它。 Dijkstra's algorithm是最简单的实现方式之一，但它对您的应用程序来说太过分了。 (它找到从一个节点到所有其他节点的最短路径。)有一个相关的算法称为 A*这有点复杂，但它完全符合您的要求。