1

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

{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。

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

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

欢迎涉及其他数据结构的更好的解决方案或优化；我将数据存储在类似于这本字典的 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 行是做什么用的（评论说“所有剩余的顶点都无法从源访问”——这是否只是在保证已经找到最佳路径时阻止它继续运行？）。我可能也搞砸了别的东西，所以如果你能看一下，我会很感激的。

4

2 回答 2

3

你所描述的是一个最短路径问题。有几种方法可以解决它。 Dijkstra 的算法是最容易实现的算法之一，但它对您的应用程序来说太过分了。（它找到从一个节点到所有其他节点的最短路径。）有一种称为A*的相关算法稍微复杂一些，但它完全符合您的要求。

于 2012-12-31T04:53:07.427 回答
2

使用networkx。它易于安装。

从游戏板的图片中，我认出了苏格兰场游戏。
评论您与@Bill the Lizard 的对话：
您确实可以预先计算所有最短路径。节点和边都不会改变。
您可以46通过135 个出租车台阶或 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]
于 2012-12-31T19:38:31.293 回答