AI：找最快的算法，如果路径存在？(AI: Fastest algorithm to find if

我要寻找一个寻路算法使用一个AI控制，需要找到从A到B.这并不一定是最短路径的路径的2D网格的实体，但它需要非常快的计算。网格是静态的（不会改变）和一些网格单元被障碍物所占据。

我目前使用的A *，但它是我的目的，速度太慢，因为它总是试图计算出最快路径。当路径不存在，在这种情况下，A *将尝试探索太多的细胞发生的主要性能问题。

是否有不同的算法，我可以使用，可以找到一个路径比A *更快，如果路径不必是最短路径？

谢谢，

鲁米

Answer 1:

假设您的网格是静态的，不会改变。您可以构建网格后，一旦计算出你图的连接部件。

然后，你可以很容易地检查，如果源和目标顶点是组件之内还是之外。如果是，则执行A *，如果不是的话就不要因为不能有组件之间的路径。

你可以使用BFS或DFS曲线的连接部件。

Answer 2:

为了找到一个路径，而不是最短路径，使用任何图的遍历（如深度优先或最佳优先）。它不一定会更快，实际上它可以检查更多的节点比一些图表A *，所以它取决于你的数据。然而，这将是更容易实现和持续性因素会显著降低。

为避免搜索路径时是没有的，你可以创建独立集合（您构建的图形后一次），以非常快速检查两个特定点是否连接。这需要线性空间，并建立线性时间，并查找需要摊销几乎恒定的时间，但你仍然需要在时间运行完整的算法，因为它只会告诉你是否有路径，而不是在那里这条道路去。

如果你已经在构建数据结构提前，并有更多的时间和空间，在运行时即时最短路径进行交易，你可以有你的蛋糕和熊掌兼得：在弗洛伊德- Warshall算法让你在所有的最短路径相对温和的O(|V|^3)的时间，这是考虑到有所述最大收益| V | 2（启动，目的地）对。它计算一个|V| * |V| |V| * |V| 矩阵，这可能是有点大，但考虑到这是一个整数矩阵，你只需要|V| * |V| * log_2 |V| |V| * |V| * log_2 |V| 位（例如，这是1.25 MIB为1024点的顶点）。

Answer 3:

您可以使用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)

Answer 4:

如果图足够小，可以使用预先计算所有最短路径Floyd-Warshall算法。这需要O(|V|²)存储器，用于存储路径，并且O(|V|³)时间预计算。

显然，这不是非常大的图形选项。对于那些你应该使用托马斯的答案，并预先计算连接的组件（需要线性时间和内存），以避免最昂贵的A *搜索。

Answer 5:

A *，BFS，DFS，和所有其他搜索算法必须准确检查相同数量的节点时，有没有道路，所以“先使用DFS”不是一个很好的答案。并采用弗洛伊德-沃肖尔是完全不必要的。

对于静态图形，该解决方案是简单的; 看到@托马斯的答案。对于非静态的图表，这个问题比较复杂; 看到这个答案有一个良好的算法。

Answer 6:

如果你的迷宫永远不会改变，并存在发生任何路径永远，你能不能使用映射算法至极会发现你的迷宫“地区”，并存储这些以某种格式？存储器使用将与节点或细胞和速度的量是线性访问和比较阵列的两个元件的速度。

计算（劈裂到地区）可能会比较费时，但它在开始时进行一次。也许你能适应用于此目的的一些洪水填充算法？

不知道是否是从上面清楚的，但我认为一个例子是始终ahelp。我希望你能使用PHP语法原谅我。

例如（5×5迷宫）（ []标记的障碍物）：

    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方案（如果该功能不能很好地与问候迷宫的comlexity选择），或者你所有的JN落到迷宫障碍。 ..所以它可能是更好的，如果可能的手动定义那些JN或使该载置JN函数非平凡（以考虑到每个区域的面积）。

一旦你到达JN你可能有他们之间的通路也索引（快速检索的开始和结束JN之间预定义的路径），或者仅在集“结节点”的执行另一A *寻路，只是这一次-因为有少得多那些JN之间的路径搜索会更快。