logo标签列表

AI：最快的查找路径算法是什么？

algorithmartificial-intelligencepath-findinga-star
10
我正在寻找一种路径规划算法，用于控制一个在二维网格中移动的实体的AI，该实体需要从A点到达B点。它不一定要走最短路径，但必须计算速度非常快。该网格是静态的（永远不会改变），某些网格单元被障碍物占据。
我目前正在使用A*算法，但对于我的目的来说它太慢了，因为它总是试图计算最快的路径。主要性能问题出现在路径不存在时，此时A*将尝试探索过多的单元格。
如果路径不需要是最短路径，是否有其他算法可用于比A*更快地找到路径？
谢谢，
Luminal
2
一个基本的深度优先搜索算法在路径不存在时可能比A*更快，尽管它们具有相同的复杂度。原因是它的代码更简单。希望能有更好的解决方案。 - Pubby
你可以使用非可行启发式的A*算法，这可能会更好。但一般来说，你需要提供更多的信息才能得到一个好的答案。没有最快的算法。 - ziggystar
你是否满意，如果你知道路径是否存在，而不知道实际路径呢？（或者你能否在A*中使用它，以避免搜索不存在的路径？） - Martina
7个回答
9
假设您的网格是静态的且不会改变。在构建网格后，您可以计算图的连通分量一次。
然后您可以轻松地检查源顶点和目标顶点是否在一个组件内。如果是，则执行A*，如果不是，则不要执行，因为组件之间不存在路径。
您可以使用BFS或DFS获取图的连通分量。
4
要找到一条路径而不是最短路径，可以使用任何图遍历算法（例如深度优先或最佳优先）。它不一定会更快，实际上在某些图形上可能会比A*检查更多的节点，因此它取决于您的数据。但是，它将更容易实现，并且常数因子将显着降低。
为了避免在没有路径时搜索路径，您可以创建不相交集合（在构建图形后仅一次）以非常快速地检查两个给定点是否连接。这需要线性空间和线性时间来构建，并且查找需要平摊实际恒定时间，但有时仍然需要运行完整算法，因为它只会告诉您是否有路径，而不是路径的位置。
如果您已经预先构建数据结构，并且可以在运行时交换一些时间和空间以获得即时最短路径，那么您就可以两全其美：Floyd-Warshall算法以相对适中的O(|V|^3)时间给出了所有最短路径，这是最划算的选择，因为有|V|²个（起点，终点）对。它计算了一个|V| * |V|矩阵，可能有点大，但请考虑这是一个整数矩阵，您只需要|V| * |V| * log_2 |V|位（例如，对于1024个顶点，这是1.25 MiB）。
2
你可以使用DFS或BFS，因为你只想知道这两个顶点是否相连。这两种算法的时间复杂度都是O（|V|），其中V是图中所有顶点的集合。
如果你的启发式算法需要一些非平凡的时间来计算，请使用这两种算法之一；否则，我认为A*算法应该比DFS或BFS运行得更好或类似。
作为另一种选择，您可以使用Floyd-Warshall算法（O（V^3））来计算，在创建网格后，每对顶点之间的最短距离路径，因此在模拟开始时完成所有重要工作，并存储所有最短路径以进行O（1）访问的哈希表，或者如果这被证明过于消耗内存，则可以仅保留矩阵next，使得next[i] [j]存储我们必须从顶点i到顶点j。因此，我们可以从i到j建立路径，如(i，k1 = next [i] [j])，(k1，k2 = next [k1] [j]) ...（kr，j）。
Floyd-Warshall的时间复杂度为O(V^3)，空间复杂度为O(V^2)。当V达到10^6时，它的使用效果并不好。 - nhahtdh
@nhahtdh 是的，这就是我根据图形和约束条件提供 Floyd-Warshall 作为一个选项。否则应该使用 A*、DFS 或 BFS。 - Gustavo Torres
1
如果图很小，您可以使用Floyd-Warshall算法预先计算所有最短路径。这需要O(|V|²)内存来存储路径，并且需要O(|V|³)时间进行预处理。
显然，对于非常大的图，这不是一个选项。对于这些图，您应该使用Thomas的答案并预先计算连接组件（需要线性时间和内存），以避免最昂贵的A*搜索。
0
如果你的迷宫从未改变过，并且任何已存在的路径都会一直存在，那么你不能使用一种映射算法来查找迷宫中的“区域”并将其存储在某种格式中吗？内存使用量将随节点或单元格数量线性增加，而速度则取决于访问和比较数组中两个元素的速度。
计算（拆分成区域）可能需要更多时间，但这只需要在开始时完成一次。也许您可以为此目的调整一些泛洪算法？
以上内容不确定是否清晰，但我认为示例总是有帮助的。我希望您能原谅我使用PHP语法。
例如（5x5迷宫）（ [] 标记障碍物）：
    0 1 2 3 4
  +----------+
0 |[][]   2  |
1 |  [][]    |
2 |    []  []|
3 |  1 []    |
4 |    []    |
  +----------+

索引区域（使用数字哈希而不是“x:y”可能更好）：

$regions=array(
    '0:1'=>1,'0:2'=>1,'0:3'=>1,'0:4'=>1,'1:2'=>1,'1:3'=>1,'1:4'=>1,
    '2:0'=>2,'3:0'=>2,'3:1'=>2,'3:2'=>2,'3:3'=>2,'3:4'=>2,'4:0'=>2,
    '4:1'=>2,'4:3'=>2,'4:4'=>2
);

那么你的任务就是找出你的起点和终点是否在同一个区域内：

if ( $regions[$startPoint] == $regions[$endPoint] )
    pathExists();

现在如果我没记错的话，A*算法的复杂度（速度）取决于起点和终点之间的距离（或解的长度），这可能用于加快搜索速度。
我会尝试在迷宫中创建一些“交汇节点”（JN）。这些节点可以位于一个函数上（以便快速知道最近的JN在哪里），并且你可以预先计算所有相邻JN之间的路径。
因此，你只需搜索从起点到最近的JN的解决方案，以及从终点到其最近的JN（其中它们都位于同一个区域（上述所说的））。现在我可以想象一种情况（如果函数选择与迷宫的复杂性不符合），即有几个区域，其中一些可能根本没有JN，或者所有的JN都位于迷宫中的障碍物上...因此，如果可能的话，最好手动定义这些JN，或者使这个放置JN的函数非平凡（考虑每个区域的面积）。

一旦到达JN，您可以将它们之间的路径进行索引（以快速检索起点和终点JN之间的预定义路径），或者执行另一个A*路径查找，但这次仅在“交叉节点”集合上进行 - 因为这些节点较少，所以在JN之间进行路径搜索会更快。

0
A*、BFS、DFS 和所有其他搜索算法在没有路径时将不得不检查完全相同数量的节点，因此“首先使用DFS”不是一个好答案。而使用 Floyd-Warshall 算法是完全不必要的。
对于静态图，解决方案很简单；请参见 @Thomas 的答案。对于非静态图，问题更加复杂；请参见 this answer 以获取一个好的算法。
0
你可以考虑使用Anytime A*算法（ANA*或其他变种）。
这些算法会先进行贪婪的最佳优先搜索，以找到初始路径。
然后，它们会通过逐渐减少启发式函数的权重来进行增量改进。
你可以随时停止搜索，并获得目前为止找到的最佳路径。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接