1

我正在开发一个 PHP 类，该类能够计算未加权和有向图系统中两点的路线（尤其是 EVE Online）。我从来没有开发过图形解决方案，所以我真的不知道计算图形路径的最快方法是什么，所以我在网上四处寻找，即使我发现除了以数学为中心的讨论或过于特殊的解决方案。

我的第一个想法是找到从节点 A 到节点 B 的所有路径并比较它们的长度。后来我注意到这是不必要的，因为我不需要比较，而是要找到第一条最短路径。

然后我创建了一个递归系统，它实现了 Deepening Depth-First Search 算法（我在这里提出），但是当两个节点之间的距离增加时，使用它仍然太重了。我在几秒钟内成功跟踪了 16 步或更少的路径。当涉及到搜索更远的节点时，它不会在 90 秒内完成。

你能帮我找到一个更快的解决方案吗？我想过创建一个包含各个节点之间所有距离和路径的表，但我们谈论的是数千个节点，构建它（并维护它）将永远存在。

http://hastebin.com/tilusubeli.coffee

类“跳跃”。

  • 该构造以字符串或整数的形式接受原点 (from) 和目标 (to) 节点。在前一种情况下，它会解析它的ID（整数）并使用它（方法getSystemID，你可以忽略它）。“jumpsTable”初始化程序以这种形式创建一个数组：

$this->jumpsTable[node_id] = array(next_node_id_1, next_node_id_2, ...)

jumpsTable 是图的数据表示。

  • 公共方法“分析”将简单地调用 IDDFS

算法：

  • IDDFS 从深度 0 开始调用 DLS，一直持续到（最大深度），直到 DLS 返回有效路径。这样，它不会在两条相同长度的路线之间进行选择，而是选择第一条。

  • DLS 是一种递归方法并查找其“子”节点：如果其中一个子节点是目标节点，则返回路径，否则将每个子节点称为“起始节点”，并降低深度值。如果任何 DLS 调用返回路径，则退出循环。如果没有 DLS 返回路径，则返回 null。

4

1 回答 1

0

如果进行深度优先搜索，则无法保证找到的第一条路径是最短的。您应该改为执行广度优先搜索，因为您的图未加权（否则，标准算法将是A*）。

但是，您需要对您的实现进行彻底的修改，因为递归方法不适合广度优先搜索。请注意，这是一个非常经典的算法，您应该更容易找到像这个这样的现有 PHP 实现并将其调整为您自己的数据结构。

PS：处理您的问题的另一种方法是使用具有迭代加深的深度优先搜索，这基本上是使用深度限制应用的深度优先搜索，并以增加的限制重复应用（直到找到目标节点）。

PPS：如果时间是主要问题，请务必检查您是否多次处理同一节点。

PPPS：你可能对这个问题感兴趣：给定一个有向图，找出两个节点之间是否有一条路线。

于 2013-07-15T14:18:33.333 回答