BFS、Dijkstra、A*、求前K最优解的A*算法区别与联系
作者:
解矣
,
2023-10-13 15:39:09
,
所有人可见
,
阅读 130
BFS:使用队列实现,维护了队列的两段性,实际上相当于一个堆,但取堆顶元素的时间复杂度是O(1)。图中每个元素只入队一次,入队即最优,如果入队的点是终点,可以直接返回。
Dijkstra:使用优先队列实现,也就是堆,取堆顶元素的时间复杂度是O(log N),N为堆元素数量。途中每个元素可以入队多次,但是是有条件的入队,只有当前入队的元素具有更优的解时,才能入队。所以每个元素也能出队多次,当该元素出队时,就不能再让其入队了,并且出队的这个元素是最后入队的那个。剩余的在队列中的该元素都没用了,遇到了就直接丢弃。因为算法保证了第一次出队的元素具有最优解。
A*算法:使用优先队列维护。每个元素可以入队多次,也可以出队多次。某一个元素出队后,并不作任何标记,之后还可以继续入队。但也有入队条件,只有比当前解更有才能入队。也就是说第一次出队的元素并不具备最优解。但是终点出队可以得到最优解,此时从起点到终点上的所有元素都获得最优解。
A*求前K个最优解:使用优先队列维护。每个元素可以入队多次,也可以出队多次。某一个元素出队后,不做任何标记,之后还可以入队。并且入队也没有任何条件,符合规则就行,只需要维护每个元素的最短距离和路径即可。出队的节点需要将所有的后继节点全部入队。终点出队即可获得最优解,出队K次可以获得第K优的解。