logo标签列表

分支定界法（+扩展列表）和Dijkstra算法在图形中的区别

algorithmgraphdijkstrabranch-and-bound
6
我正在学习http://youtu.be/gGQ-vAmdAOI?t=23m14s，在23:14时，我感觉到“扩展列表”的分支限界算法与Dijkstra算法非常相似。在后面的讲座中，当算法再次通过一个可接受的启发式扩展时，我们得到了A*算法。
这使我想到Dijkstra算法是分支限界算法的一个子类。这样对吗？
总结讲座内容如下：
探讨了搜索算法。特别是，从简单的分支和限界解决方案开始：
直到访问（扩展）目标节点为止，访问距离源节点最短的节点，并将其后继节点添加到要访问的节点的优先级队列中（按最小距离排序）。这还没有检测到循环（例如多次访问节点），由于组合爆炸而效率低下。
一个简单的扩展使算法表现得更好：记住已经访问过的节点（扩展，因此为扩展列表）。现在不会再访问任何节点两次，算法的性能大大提高。
在最后一部分中，添加了一个可接受的启发式方法来获得A*。
希望这些信息足够了解讲座内容。如果不够，请告诉我，我可以提供更多的例子！
1
我最近刚刚看完这些讲座，也有同样的想法。你是否找到了这个问题的答案？ - trianta2
很遗憾，我没有。但我相当确定我是正确的。我已经不再关注这个讲座了，但我认为唯一的区别可能在于，在Dijkstra算法中，我们会放松已经入队的节点，而分支和界限法则似乎是将一个重复的节点入队。不过，这只是一个实现细节。 - Sebastian Graf
你会说其中一个是完整的，而另一个不是吗？ - MD Islam
1
我不确定你所说的“complete”是什么意思。 - Sebastian Graf
2个回答
3

两者的思想是相同的，不同之处在于实现。Dijkstra算法之所以特殊，是因为它是使用堆进行分支和限界（这可以大大加快速度）。

1

是的，只要我们假设扩展列表可以动态检查，你说得对。如果在“扩展列表”中有一个状态，这意味着我们已经访问了该状态，并且路径上的值为n。

当我们运行算法时，如果我们遇到一条访问该节点的路径，其值小于n，则“扩展列表”给我们提供了将该路径替换为“BnB”的优先级队列的选项，这本质上是“Djikstra”。您可以使用哈希表实现，该哈希表为每个节点保留算法运行时最短路径的值，就像“Djikstra”一样。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接