在复杂性方面最好的寻路算法是什么？
What's the best pathfinding algorithm in complexity?
我需要在我的一个程序中实现寻路算法。目标是知道路径是否存在。因此，了解路径本身并不重要。
我已经做了一些研究，但我不确定该选哪一个。 This post 一直在说 DFS 或 BFS 更适合这种程序，但我宁愿确认知道确切的情况。我也有兴趣了解程序本身的复杂性，但我想我可以找到它。不分享就好了
这是我正在使用的图表：假设我有一个 x*y 网格，其中包含路径可以和不能采用的区域。
我想知道是否存在从图的顶部开始并在图的底部结束的现有路径。这是红色路径的示例：
我相信 DFS 在复杂性方面是最好的，但我也不确定如何在知道路径可以采用的不同起点的情况下确切地实现它。我不确定在路径可以开始的每个不同点上启动 DFS 是否更好，或者如果我添加一层区域，路径可以通过让一个测试工作。
感谢您的帮助！
您可以在此处采用多种不同的方法。假设您正在使用的网格的大小与上面显示的大致相同，并且假设您不是，比如说，一次处理数百万个网格，那么广度优先搜索和深度优先搜索都有可能会同样有效。广度优先搜索的优点是，它会找到从顶部任意位置到底部任意位置的最短路径；缺点是它通常需要比深度优先搜索更多的内存。但是同样，如果您正在处理大约有数百或数千个单元格的网格，那么这种内存开销很可能不会成为太大的问题。我会说选择你觉得最舒服的算法并使用它。
至于如何实现从 "anywhere in the top" 到 "anywhere in the bottom," 的搜索，您可以通过几种不同的方式实现。
如果您使用的是深度优先搜索，您可以 运行 从顶行的每个单元格进行一次深度优先搜索，然后搜索一条路径向下到底排。 DFS 要求您维护一些有关哪些单元格已被访问和未被访问的信息。如果您在对 DFS 的所有调用中循环使用相同的信息，您将确保没有两个调用执行任何重复的工作，因此最终的解决方案应该非常高效，运行宁时间 O(mn) m×n格.
如果您使用的是广度优先搜索，则修改非常简单：不是仅在搜索开始时将单个起点入队，而是将队列中的每个单元格入队搜索开头的第一行。然后 BFS 将自然地探索所有可能的路径，从顶行的任何位置开始。
这两种想法都可以用不同的方式来思考。假设您的网格是一个 graph，其中每个单元格都是一个节点，边对应相邻单元格对。然后，您可以添加一个位于网格顶行上方并连接到顶行中每个节点的新节点。然后添加一个新节点，它位于底行的正下方，并连接到底行中的每个节点。现在，如果有一条从新顶部节点到新底部节点的路径，则意味着有一条从顶行中的某个节点到底行中的某个节点的路径，因此在此图中进行一次搜索就足以检查路径是否存在。 （有趣的事实：上面对 DFS 和 BFS 的两个修改都可以被认为是在这个新图中隐式地进行搜索。）
您可能要考虑另一种选择，它实施起来相当容易，而且效率比 DFS 或 BFS 低得难以察觉，那就是使用 disjoint-set forest data structure 来确定连接的内容。该数据结构支持两种查询：
- 给定两个单元格，标记有一种方法可以从第一个单元格到达第二个单元格。 ("Union")
- 给定两个单元格，确定它们之间是否有路径，可以是直接路径，也可以是通过将多条其他路径链接在一起形成的。 ("Find")
您可以通过构建一个不相交集的森林，将所有相邻单元对合并在一起，然后将顶行中的所有节点合并在一起并合并底行中的所有节点来实现您的连通性查询。执行 "find" 查询以查看是否有任何一个顶部节点连接到任何底部节点将解决您的问题。这将花费 O(mn α(mn)) 函数 α(mn) ，它增长如此缓慢以至于它基本上是三个或四个，所以它实际上与 BFS 或 DFS 一样有效。
我需要在我的一个程序中实现寻路算法。目标是知道路径是否存在。因此，了解路径本身并不重要。
我已经做了一些研究，但我不确定该选哪一个。 This post 一直在说 DFS 或 BFS 更适合这种程序，但我宁愿确认知道确切的情况。我也有兴趣了解程序本身的复杂性，但我想我可以找到它。不分享就好了
这是我正在使用的图表：假设我有一个 x*y 网格，其中包含路径可以和不能采用的区域。 我想知道是否存在从图的顶部开始并在图的底部结束的现有路径。这是红色路径的示例：
我相信 DFS 在复杂性方面是最好的，但我也不确定如何在知道路径可以采用的不同起点的情况下确切地实现它。我不确定在路径可以开始的每个不同点上启动 DFS 是否更好，或者如果我添加一层区域，路径可以通过让一个测试工作。
感谢您的帮助！
您可以在此处采用多种不同的方法。假设您正在使用的网格的大小与上面显示的大致相同，并且假设您不是，比如说，一次处理数百万个网格，那么广度优先搜索和深度优先搜索都有可能会同样有效。广度优先搜索的优点是，它会找到从顶部任意位置到底部任意位置的最短路径；缺点是它通常需要比深度优先搜索更多的内存。但是同样，如果您正在处理大约有数百或数千个单元格的网格，那么这种内存开销很可能不会成为太大的问题。我会说选择你觉得最舒服的算法并使用它。
至于如何实现从 "anywhere in the top" 到 "anywhere in the bottom," 的搜索，您可以通过几种不同的方式实现。
如果您使用的是深度优先搜索，您可以 运行 从顶行的每个单元格进行一次深度优先搜索，然后搜索一条路径向下到底排。 DFS 要求您维护一些有关哪些单元格已被访问和未被访问的信息。如果您在对 DFS 的所有调用中循环使用相同的信息，您将确保没有两个调用执行任何重复的工作，因此最终的解决方案应该非常高效，运行宁时间 O(mn) m×n格.
如果您使用的是广度优先搜索，则修改非常简单：不是仅在搜索开始时将单个起点入队，而是将队列中的每个单元格入队搜索开头的第一行。然后 BFS 将自然地探索所有可能的路径，从顶行的任何位置开始。
这两种想法都可以用不同的方式来思考。假设您的网格是一个 graph，其中每个单元格都是一个节点，边对应相邻单元格对。然后，您可以添加一个位于网格顶行上方并连接到顶行中每个节点的新节点。然后添加一个新节点，它位于底行的正下方，并连接到底行中的每个节点。现在，如果有一条从新顶部节点到新底部节点的路径，则意味着有一条从顶行中的某个节点到底行中的某个节点的路径，因此在此图中进行一次搜索就足以检查路径是否存在。 （有趣的事实：上面对 DFS 和 BFS 的两个修改都可以被认为是在这个新图中隐式地进行搜索。）
您可能要考虑另一种选择，它实施起来相当容易，而且效率比 DFS 或 BFS 低得难以察觉，那就是使用 disjoint-set forest data structure 来确定连接的内容。该数据结构支持两种查询：
- 给定两个单元格，标记有一种方法可以从第一个单元格到达第二个单元格。 ("Union")
- 给定两个单元格，确定它们之间是否有路径，可以是直接路径，也可以是通过将多条其他路径链接在一起形成的。 ("Find")
您可以通过构建一个不相交集的森林，将所有相邻单元对合并在一起，然后将顶行中的所有节点合并在一起并合并底行中的所有节点来实现您的连通性查询。执行 "find" 查询以查看是否有任何一个顶部节点连接到任何底部节点将解决您的问题。这将花费 O(mn α(mn)) 函数 α(mn) ，它增长如此缓慢以至于它基本上是三个或四个，所以它实际上与 BFS 或 DFS 一样有效。