搜索最少的跳数？

Question

我正在尝试创建一个A*寻路算法，但是我在起步时遇到了一些麻烦。一点背景：

我并不精通寻路算法，但我确实在几年前提到过这个问题（从那以后，我已经忘记了所学的一切）。我在网上玩夏娃，这是一个关于互联网宇宙飞船的在线游戏。开发人员为静态信息（游戏中的项目、太阳系位置等）发布数据转储。我正在寻找从太阳系A到太阳系B的最短路线

看看这个地图：http://evemaps.dotlan.net/map/UUA-F4这是游戏中的一个区域，每个节点都是一个系统。我想计算任何两个系统之间的最短距离。在

我的问题是：我在网上读到的所有关于A*的文章都是关于合并两个节点之间的距离（例如，两个城市之间的距离）来帮助计算最短路径。这对我的情况没有帮助，因为我更感兴趣的是跳数（节点1>；节点2>；节点3），而不是这些跳跃之间的距离。我不知道如何修改A*算法来合并它。在

我在数据库中的信息： 所有系统及其邻居的列表（因此，systemX与systemA和systemB链接） x、 三维网格中所有系统的y和z坐标

如果有人能给我指出正确的方向，那就太好了。我希望在PHP中使用它，但是我也已经开始在Python中工作了一段时间，这样就可以了。在

如有需要，可根据要求提供示例数据。在

编辑

正如一些人所指出的，与每一次跳跃相关的“成本”仅仅是1。但是，使用*时，还需要一个启发式算法来估计从当前节点到目标节点的距离。我不确定如何确定这个值，因为我不确定剩余的跃点。如前所述，我确实有每个节点的三维坐标（x，y，z），但我不确定这是否能提供任何见解，因为每个节点之间的物理距离并不重要。我知道没有一条路的跨度超过99次。在

编辑2

示例区域的MySQL数据。在

to -> from数据：http://pastebin.com/gTuwdr7h

系统信息（如果需要，x，y，z坐标：http://pastebin.com/Vz3FD3Kz

Answer 1

取linked graph的上半部分：

假设这些线代表2个方向（即，您可以去或从任何链接的节点），黑线的“成本”为1，红线的“成本”为2。在

该结构可以用以下Python数据结构表示：

graph = {'Q-KCK3': {'3C-261':1, 'L-SDU7':1},
         'L-SDU7': {'Q-KCK3':1, '3C-261':1,'4-IPWK':1},
         '3C-261': {'4-IPWK':1,'9K-VDI':1,'L-SDU7':1,'U8MM-3':1},
         'U8MM-3': {'9K-VDI':1,'3C-261':1, '9K-VDI':1, 'Q8T-MC':2},
         'Q8T-MC': {'U8MM-3':2, 'H55-2R':1, 'VM-QFU':2},
         'H55-2R': {'Q8T-MC':1, '9XI-OX':1, 'A3-PAT':1, 'P6-DBM':1},
         'P6-DBM': {'A3-PAT':1, 'H55-2R':1},
         'A3-PAT': {'P6-DBM':1, 'H55-2R':1, '9XI-OX':1,'YRZ-E4':1},
         'YRZ-E4': {'A3-PAT':1}, 
         'VM-QFU': {'IEZW-V':1, 'PU-128':2},
         'IEZW-V': {'VM-QFU':1, 'PU-128':1, 'B-DX09':1},
         'PU-128': {'VM-QFU':1, 'B-DX09':1, 'IEZW-V':1},
         'B-DX09': {'IEZW-V':1, 'PU-128':1, '1TS-WIN':1},
         '1TS-WIN': {'B-DX09':1, '16-31U':1},
         '16-31U': {'1TS-WIN':1}
        }

现在可以定义一个递归函数来导航该数据：

^{pr2}$

现在演示：

min_path(graph,'Q-KCK3','A3-PAT')
min_path(graph,'Q-KCK3','16-31U')

印刷品：

    All paths: [['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT']]
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'] 7
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'] 6
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'P6-DBM', 'A3-PAT'] 8
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'H55-2R', 'A3-PAT'] 7
Best path: Q-KCK3->3C-261:1
3C-261->U8MM-3:1
U8MM-3->Q8T-MC:2
Q8T-MC->H55-2R:1
H55-2R->A3-PAT:1   Total: 6

    All paths: [['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'], ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U']]
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 10
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 11
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'IEZW-V', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'B-DX09', '1TS-WIN', '16-31U'] 12
        evaluating: ['Q-KCK3', 'L-SDU7', '3C-261', 'U8MM-3', 'Q8T-MC', 'VM-QFU', 'PU-128', 'IEZW-V', 'B-DX09', '1TS-WIN', '16-31U'] 13
Best path: Q-KCK3->3C-261:1
3C-261->U8MM-3:1
U8MM-3->Q8T-MC:2
Q8T-MC->VM-QFU:2
VM-QFU->IEZW-V:1
IEZW-V->B-DX09:1
B-DX09->1TS-WIN:1
1TS-WIN->16-31U:1   Total: 10

如果您想要最小的跃点数，只需修改min_path以返回最短的列表长度，而不是跳的最小总开销。或者，计算每跳的成本1。在

看看my previous answer regarding trains。在

Answer 2

如果“跳跃”的数量对你来说很重要，那么把它当作你的距离，也就是说，如果两个位置通过一个跳跃连接起来，那么距离就是1。在

对于A*，你需要两样东西：

1. 从一个位置到每个邻居的成本，在您的情况下，这似乎是恒定的（跳数）。

2. 一种启发式方法，用于估计从当前“节点”或位置到目标的成本。如何估计这在很大程度上取决于你的问题。重要的是，你的启发式方法不能*过高*估计真实成本，否则A*将无法保证最佳结果。