Dijkstra和BFS最大的不同是：在容器中弹出元素的规则不同，对于BFS是按照队列先入先出原则，Dijkstra每次弹出的元素是具备最小的g(n), g(n)表示从起点到节点n累计的最短距离
Dijkstra有特点：对于未扩展的节点m 会根据刚刚的新节点n 重新计算g(m),看看能不能下降
可以保证已扩展的点是最优点
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PpK9lxBf-1660050151431)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714214910086.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YGgkyzIB-1660050151433)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714215058419.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GHQZe67g-1660050151433)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714215222570.png)]
在入队之后，会自动优先把g小的放前面（优先队列）
优点：完备的且最优的（完备：若有解肯定能找到，找到的解是最优的
缺点：和BFS一样，是往所以方向均匀往外找的，因为没有终点信息，如果他的边全为1，Dijkstra就退化为BFS了
第2.2 A*（Dijkstra+启发式搜索）其实就是Dijkstra的cost=g(n)+加了一个函数h(n)
g(n)：起点到n节点的累计的cost
h(n)：当前n节点到目标的节点的估计代价
现在A*的策略就是优先队列优先弹出的是g(n)+h(n)最小的
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pC3wsbwF-1660050151433)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714220225705.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qd6ZD4qH-1660050151433)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714220323420.png)]
A*一定最优吗？下面这样就不是 1若要保证最优：估计值<实际到终点的值—这样的启发函数称：admissible[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f17AksFb-1660050151434)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714220456798.png)]
2可容许的启发函数的设计（Admissible Heuristic）–使得A*搜索结果最优| 欧氏距离----一定对 | 曼哈顿------如果允许对角线距离，那么就不对，否则 对 | =无穷，肯定对 | =0，肯定对 |
|---|---|---|---|
| [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yn3SGiBN-1660050151434)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714221048882.png)] | [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sunKGiLu-1660050151434)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714221113875.png)] | 退化成Dijkstra，而Dijkstra是最优的 |
Dijkstra是均为往外找，A*是启发式 找
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ExaPpVn1-1660050151435)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714221322620.png)]
3. Weighed A* 本来要让A*最优就是让h尽可能小，小到比实际距离小就行， 如果我们现在不追求这个，就让h大一点，比实际的h还要大，则可以认为A*算法在往贪心算法方向演变，虽然次最优结果，但是快啊（因为越贪心往外扩展的就越少）（用最优性换速度） 这样算出的次最优结果，而且已经被证明，cost<=epsilion*最优cost 但速度可能会指数级增加[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mt4q6vx0-1660050151435)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222241505.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Pcp8yzZc-1660050151435)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222703914.png)]
| 最贪心(不好) | weighted-A* | A*（最优） | Dijkstra |
|---|---|---|---|
| [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TX0A8tw2-1660050151435)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222720962.png)] | [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GvjNZ22L-1660050151436)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222846181.png)] | [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G0LouBfE-1660050151437)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222820022.png)] | [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RjDDu0se-1660050151437)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714222913795.png)] |
确定连通方式，常用的为8连通
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ukEHI2rQ-1660050151437)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220714223106588.png)]
C++中优先队列的选择
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ReLic7Pb-1660050151438)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220715161055347.png)]
2. 如何在A*搜索中找到最合适的启发式函数以下这些都是可以的，但不是最好的
欧式距离-可
曼哈顿-不可
无穷-可
0（退化成-可
欧氏距离：结果确实最优，但是扩展范围广，效率低，其他的也是
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LFcbEcu7-1660050151438)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220715161628614.png)]
为什么呢：因为他们都不是tight的，虽然h<=h*就行了，但上面的方法下的h，中间留下很多gap，导致有很多搜索空间。因为欧式距离比真实距离要小很多，欧式距离是直接算对角线，而真实的情况，只能一个格子里面对角线。
对于一个非常结构化的地图，如栅格地图，有结构化的移动规则（直行、对角），最短的路径可以直接准确算出真值，所以估计值=真值，即最tight的，所以这种对角启发式函数下的搜索范围是很少的
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LvjBlJZG-1660050151438)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220715162740487.png)]
3.打破平衡（Tie Break）| 即：在A*搜索过程中如果出现两个点的距离是一样的，会任意选择一个点，每次都这样，就会造成一个平衡 会让搜索范围变大。而若只选择一个方向的点，则会打破平衡，减少搜索范围 | 方法1：稍微扩大一点启发式函数，对于f相等的两个节点，会把某个节点的h稍微扩大一点，p<一步最小的cost/地图内最大可能的cost，这个最大值一定存在因为地图有限。这样f+h就不一样了。 但这样做也会轻微的打破h的admissible，因为若h本来就=真值，则扩大一点就会超过，不满足admissible，但实际情况基本不会出现，h很难等于真值，因为有障碍物 |
|---|---|
| [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gN4CZL7o-1660050151438)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220715163149090.png)] | [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aA0wrcYq-1660050151439)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220715163642670.png)] |
| 方法2：当f相等的时候，比较h | 方法3：对每个节点加上随机的数值，这个数值要事先根据坐标定下，所以要构建一个基于坐标的哈希表，这个稍微有点复杂，但效果可能更好 |
| 方法4：加一个倾向型，如倾向于往目标点的直线方向走，引入cross变量=可选择的位置到直线方向的距离，再h=h+cross*0.001 | 方法4在没有障碍物的时候效果特别好，但有障碍物的时候就可能不太好，可能还会收到更恶劣的后果：因为在生成轨迹之后要优化成一条尽量光滑的曲线，而方法4的初始轨迹很波折，就很难优化。示意图如下 |
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rUAqUzTU-1660050151439)(C:UsersAdministrator.DESKTOP-B3VBL7LAppDataRoamingTyporatypora-user-imagesimage-20220716222924053.png)]
有很多Tie breaker方法，具体选什么要看具体情况
后面介绍的Jump Point Search（JPS）就是一种系统性的打破tie的方法
