一种最佳优先算法。用于图搜索。
以路径代价（例如路径长度）为标准，从小到大扩展代价，找到最佳路径的算法。
其扩展过程可以看作是从起点位置开始，以波形式向外扩展，直到抵达终点。
ref: 《AIMA》
概述
- 评价函数：以路径为评价，在路径一致的波中展开
- 理解为广度优先搜索的特殊形式，广度为动作代价，Dijkstra 为路径代价
- 后期目标测试：在扩展节点时测试是否为目标节点，而不是在生成节点时立即确认
- 推迟目标测试的时间，才能保证返回最佳的路径，而不是非最佳路径
计算复杂度
- C* 为搜索到最优解的代价（路径长度）
- 为动作的下界
相比广度优先算法更复杂，因为要根据路径代价迭代
完备性
算法是完备的，而且一般认为代价为最优
动态规划 视角
ref: https://www.zhihu.com/question/22311234/answer/2281654855
其实Dijkstra算法有动态规划成分，但一般被认为是贪心策略的一种，有以下相同的性质：
- 最优子结构：Dijkstra对于子路径是局部最优的
- 无后效性：Dijkstra对于前后的状态是不用重复计算的。仅是对于路径代价的拓展。