找出游戏板上两个方块之间的最短距离

Question

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

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

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

^{pr2}$

…您可以选择1->；2->；3，也可以选择1->；3。在

我正在寻找一个算法来找出任意两个正方形之间的最短距离。最明显的想法是查找开始空格的键，然后取列表中的第一个数字，查找可能的空格，依此类推，当它碰到之前看到的数字或最后一个方块时，停止并返回到上一个列表（如果到达结果方块，则存储路径和距离，待完成后进行比较）。在

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

欢迎使用更好的解决方案或涉及其他数据结构的优化；我将数据存储在一个类似于此字典的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因为我找不到任何与我需要的数据格式相匹配的现有实现（每次移动都有固定的成本，因此距离不会存储在任何地方）。在

我知道我需要在最后对队列重新排序，但我不确定如何排序。我也不明白第25行和第26行是什么意思（评论说“所有剩余的顶点都无法从源代码访问”--这是否只是在保证已经找到最佳路径的情况下阻止它继续运行吗？）。我可能也弄坏了其他的东西，所以如果你能看看我会很感激的。在

Answer 1

你所描述的是一个shortest path problem。有几种方法可以解决这个问题。Dijkstra's algorithm是实现最简单的方法之一，但对于您的应用程序来说，这是一种过度使用。（它找到从一个节点到所有其他节点的最短路径）有一个相关的算法叫做A*，它稍微复杂一点，但它确实能满足您的需要。在

Answer 2

使用networkx。它很容易安装。在

从游戏板的照片上我认出了苏格兰场的比赛。
评论您与@Bill the Lizard的对话：
你确实可以预先计算出前面所有的最短路径。节点和边都不会改变。
您可以从13到达46，可以通过5个出租车台阶或1个地下台阶。在

我可能会使用一个包含所有边（出租车、公共汽车、地铁）的“大”图，以及几个结合了出租车+公共汽车、出租车+地铁和出租车的图形（我不太记得游戏规则。。。你必须弄清楚什么是有意义的）。在

我不确定networkx中的算法是如何处理关系的！在

所以，预先计算前面的所有最短路径。
然后只要有需要就去查一下。在

import networkx as nx

# simplified example
# data is in the format as you specified
data = data = {1: [2,3,4],
               2: [1,3,5],
               3: [1,2,4],
               4: [1,3,5],
               5: [2,4]}

# initialize empty graph
G = nx.graph()

# now we're adding all edges
# don't bother about duplicates   they're ignored
for n1, n in data.items():
    for n2 in n:
        G.add_edge(n1, n2)

# get ALL shortest paths
p = nx.shortest_path(G)

# lookup when needed, e.g. from 1 to 5
p[1][5]
# gives [1, 2, 5]