我在看马里奥人工智能大赛中的人一直在做什么,其中一些人利用A*(A-Star)路径算法构建了一些漂亮的马里奥机器人.
替代文字http://julian.togelius.com/mariocompetition2009/screen1.png
(马里奥·博特在行动视频)
我的问题是,A-Star与Dijkstra相比如何？看着它们,它们看起来很相似.
为什么有人会使用一个而不是另一个？特别是在游戏路径的背景下？
有人可以告诉我为什么Dijkstra的单源最短路径算法假设边缘必须是非负的.
我说的只是边缘而不是负重量周期.
我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:
2
A-------B
\ /
3 \ / -2
\ /
C
来自网站:
假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(A,x),即(A,B).然后设置d(A,B)= 2并选择另一个边(y,C),使d(A,y)+ d(y,C)最小化; 唯一的选择是(A,C),它设置d(A,C)= 3.但它从未找到从A到B的最短路径,通过C,总长度为1.
我无法理解为什么使用Dijkstra的以下实现,d [B]将不会更新为1(当算法到达顶点C时,它将在B上运行放松,看到d [B]等于2,因此更新它的价值1).
Dijkstra(G, w, s) {
Initialize-Single-Source(G, s)
S ? Ø
Q ? V[G]//priority queue by d[v]
while Q ? Ø do
u ? Extract-Min(Q)
S ? S U {u}
for each vertex v in Adj[u] do
Relax(u, v)
}
Initialize-Single-Source(G, s) {
for each vertex v ? V(G)
d[v] ? ?
?[v] …两者都可用于从单一来源找到最短路径.BFS运行O(E+V),而Dijkstra运行O((V+E)*log(V)).
另外,我见过Dijkstra在路由协议中使用了很多.
因此,如果BFS可以更快地做同样的事情,为什么要使用Dijkstra的算法呢？
Dijkstra的算法教给我如下
while pqueue is not empty:
distance, node = pqueue.delete_min()
if node has been visited:
continue
else:
mark node as visited
if node == target:
break
for each neighbor of node:
pqueue.insert(distance + distance_to_neighbor, neighbor)
但是我一直在阅读关于算法的一些阅读,我看到的很多版本都使用了reduce-key而不是insert.
为什么会这样,这两种方法之间有什么区别？
algorithm dijkstra priority-queue graph-algorithm data-structures
Dijkstra和Prim的算法之间的确切区别是什么？我知道Prim会给MST,但是Dijkstra生成的树也是MST.那究竟是什么区别？
algorithm graph dijkstra minimum-spanning-tree prims-algorithm
根据我的理解,我使用下面给出的邻接表将Dijkstra算法的时间复杂度计算为big-O表示法.它没有像它应该的那样出来,这让我逐步理解它.
O(log(V)).E*logV.O(VElogV).但是Dijkstra算法的时间复杂度是O(ElogV).为什么？
我目前正处于MMO浏览器游戏的设计阶段,游戏将包括一些实时位置的瓦片地图(因此每个单元格的瓦片数据)和一般世界地图.我更喜欢使用MongoDB进行持久数据世界的游戏引擎.
我还将实现一个运输模拟(我将在下面详细解释),它基本上是一个Dijkstra模块,我已经决定使用图形数据库,希望它能让事情变得更容易,因为它很受欢迎.
我对MongoDB + Neo4J设置感到满意,但后来注意到了OrientDB,它看起来像MongoDB和Neo4J(两者都是最好的？),甚至还有MongoDB和Neo4J的VS页面.
重点是,我听到一些关于MongoDB丢失数据的恐怖故事(尽管不确定它仍然存在)并且我没有这样的奢侈品.而对于Neo4J,我不是每年12K€的"忠实启动"成本的忠实粉丝,尽管我可能没有数百万的顶点数据库.OrientDB似乎是一个可行的选择,因为可能还有一些使用一个数据库解决方案的机会.
在这种情况下,一个逻辑移动可能会跳转到OrientDB,但它有一个小社区,并且没有找到很多关于它的评论,MongoDB和Neo4J是广泛使用的流行工具,我担心如果OrientDB是冒险.
我的第一个问题是,如果您对这些数据库有任何经验/意见.
而第二个问题是其图形数据库是一个航运仿真更好.使用数据库有望计算从任何顶点到任何顶点的最便宜路线并遍历它(经典Dijkstra).但也必须根据"国家B对国家A禁运的情况改变权重,因此任何来自A国的物品都不能通过B,在XYZ地区有洪水,因此无法进行陆路运输"等.此外,该数据库预计会缓存结果.我希望不超过1000个顶点,但边缘很多.
如果问题有点含糊,请提前致谢并提前道歉
PS:我在标题上添加了ArangoDB,但是没有太多机会去看看.
截至2016年4月18日的后期编辑:在评估了对我的问题和发展策略的反应之后,我决定使用ArangoDB,因为他们的路线图对我来说更有希望,因为他们显然没有尝试添加大量半炒的炒作功能.
我们可以使用具有负权重的Dijkstra算法吗？
停!在你想到"大笑之后,你可以无休止地在两点之间跳跃并获得一条无限廉价的道路"之前,我更多地考虑单向路径.
申请将是一个山区地形,上面有点.显然,从高到低不会消耗能量,事实上,它会产生能量(因此负路径重量)!但是,除非你是查克诺里斯,否则再回去就行不通.
我想增加所有点的权重,直到它们是非负的,但我不确定这是否会起作用.
经过大量的谷歌搜索后,我发现大多数消息来源称Dijkstra算法比Bellman-Ford算法"更有效".但在什么情况下Bellman-Ford算法比Dijkstra算法更好？
我知道"更好"是一个广泛的陈述,所以具体来说,我的意思是速度和空间,如果适用.当然,在某些情况下,贝尔曼 - 福特方法比Dijkstra方法更好.