5

我知道 Dijkstra 的算法、Floyd-Warshall 算法和 Bellman-Ford 算法,用于查找图中 2 个顶点之间的最廉价路径。

但是当所有边的成本都相同时,最便宜的路径是边数最少的路径吗?我对吗?没有理由实现 Dijkstra 或 Floyd-Warshall,最好的算法是从源头进行广度优先搜索,直到达到目标?在最坏的情况下,你将不得不遍历所有的顶点,所以复杂度是 O(V)?有没有更好的解决方案?我对吗?

但是互联网上有大量文章讨论了有障碍物的网格中的最短路径,并且提到了 Dijkstra 或 A*。即使在 StackOverfow -找到最短路径的算法,有障碍物 或这里http://qiao.github.io/PathFinding.js/visual/

那么,这些人都是傻子吗?还是我傻?为什么他们向只想将敌人移动到常规网格中的主角的初学者推荐如此复杂的东西,例如 Dijkstra?就像有人问如何在一个列表中找到最小的数字,你建议他实现堆排序,然后从排序后的数组中取出第一个元素。

4

3 回答 3

5

BFS(广度优先搜索)只是一种遍历图的方式。它的目标是访问所有顶点。就这样。移动图的另一种方式可以是例如 DFS。

Dijkstra 是一种算法,其目标是找到从给定顶点 v 到所有其他顶点的最短路径。

Dijkstra 并没有那么复杂,即使对于初学者也是如此。它遍历图表,使用 BFS + 做更多事情。这更多的是存储和更新有关当前访问顶点的最短路径的信息。

如果你想找到 2 个顶点 v 和 q 之间的最短路径,你可以通过对 Dijkstra 稍作修改来做到这一点。到达顶点 q 时停止。

最后一种算法 - A* 在某种程度上是最聪明的(也可能是最困难的)。它使用启发式方法,一个神奇的仙女,它会建议你去哪里。如果你有一个很好的启发式函数,这个算法优于 BFS 和 Dijkstra。A* 可以看作是 Dijktra 算法的扩展(启发式函数是一个扩展)。

但是当所有边的成本都相同时,最便宜的路径是边数最少的路径吗?我对吗?

正确的。

没有理由实现 Dijkstra 或 Floyd-Warshall,最好的算法是广度优先搜索?我对吗?

当涉及到所有边都具有相同权重的这种简单情况时——你可以使用任何你喜欢的方法,一切都会奏效。但是,具有良好启发式的 A* 应该比 BFS 和 Dijkstra 更快。在您提到的模拟中,您可以观察到这一点。

那么,这些人都是傻子吗?还是我傻?为什么他们向只想将敌人移动到常规网格中的主角的初学者推荐如此复杂的东西,例如 Dijkstra?

他们有一个不同的问题,这改变了解决方案。仔细阅读问题描述:

(...) 任何一点(不包括 A 和 B)的捕获都可能有障碍物阻碍路径,因此必须绕道。

敌人在通往主角的路上可能会遇到障碍。因此,例如 A* 在这种情况下是一个不错的选择。

于 2013-04-27T07:36:58.537 回答
2

BFS 就像在未加权图中找到最短路径的“蛮力”。Dijkstra 就像加权图的“蛮力”。如果您要在未加权图上使用 Dijkstra,它将完全等同于 BFS。

因此,Dijkstra 可以被认为是 BFS 的扩展。这并不是一个真正“复杂”的算法;它只比 BFS 稍微复杂一点。

A* 是 Dijkstra 的扩展,它使用启发式算法来加速寻路。

于 2013-04-29T15:43:29.067 回答
0

但是当所有边的成本都相同时,最便宜的路径是边数最少的路径吗?. 是的

如果您真的了解您链接的帖子,您会注意到他们想要解决的问题与您的不同。

于 2013-04-27T07:37:54.400 回答