5

我在 23:14 通过http://youtu.be/gGQ-vAmdAOI?t=23m14s工作时，我觉得带有“扩展列表”的分支和绑定与 Dijkstra 的算法非常相似。稍后在讲座中，当算法再次用可接受的启发式扩展时，我们得到 A*。

这让我想到 Dijkstra 的算法就是这个分支与界限的子类。是对的吗？

总结讲座：

探索了搜索算法。特别是，它们从一个简单的分支定界解决方案开始：

直到目标节点被访问（扩展），访问距离源节点最近的节点，并将其后继节点加入优先访问节点队列（按最小距离排序）。这还没有检测到周期（例如多次访问节点）并且由于组合爆炸而效率很低。

一个简单的扩展使算法执行得更好：记住哪些节点已经被访问过（扩展，因此扩展列表）。现在没有节点被访问两次，并且算法的性能要好得多。

在最后一部分中，将一个可接受的启发式添加到混合中以获得 A*。

我希望这是足够的信息，并且我不必复制讲座中的示例。如果不是，请告诉我，我会做的！

4

2 回答 2

3

区别只是在实现上，思路是一样的。Dijkstra 算法的特别之处在于它是用堆完成的分支和绑定（这给了你很大的加速）。

于 2017-09-26T15:43:31.933 回答
1

是的，您是对的，只要我们假设可以动态检查扩展列表。如果我们在 中有一个状态"extended list"，这意味着我们已经通过一条路径访问了该状态value = n。

如果我们遇到访问该节点的路径，则运行算法时，value < n我们"extended list"可以选择在 的优先级队列中替换该路径，BnB本质上是Djikstra. 您可以使用一个哈希表来实现这一点，该哈希表为每个节点保存算法运行的每一刻的最短路径值，就像Djikstra.

于 2019-02-11T05:09:44.790 回答