--- title: 图表搜索 广度 深度 优先搜索 贝尔曼-福特算法 戴克斯算法 A\*搜索算法 url: 'https://yayi.site/archives/图表搜索广度深度优先搜索贝尔曼-福特算法戴克斯算法a搜索算法' categories: 算法与设计 cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/犬吠·埼 風.png' tags: '图表搜索,深度广度搜索,A star 搜索算法,戴克斯算法,贝尔曼-福特算法' abbrlink: 8f99a990 date: 2020-09-23 21:58:21 updated: 2021-05-14 22:04:58 ---  ## 图表搜索 ### 广度优先搜索 !\[image-20200921122424199\](http://img.yayi.site/csdn/facbff647a9753a986b3b7dda097a55f.png-watermaskStyle) 1. 我们以A为起点，G为搜索目标。 A向下 有BC 两个点，==选择B ，C则作为候选点== B 再向下有 D E 两个先，==选D ，E作为新的候选点==。这些候选点可以使用==先进先出== 特点的 ==队列==的数据结构存储 然后选择 候选点C 。==F ,G添加进候选点==。 这时，AB AC 两条路径 走完了， C 候选点已用 ，开始使用DE 候选点，BD BE 这两条路径也走了。 再到F G候选点 ，发现CG 找到了。 结束 2. 特点就是 ==横向==优先搜索的。 ### 深度优先搜索 还是那个图 1. A为起点，k为搜索目标。 2. A 到 B ,C , B和C作为候选点。 3. 选择最新被添加到候选点中的点 ，B 和C 是最新，为了方便选择B 4. 到B ， D E 则添加进新的候选点， D和E是最新的，选D 5. 到D 重复操作，直到找到相应点，或者到叶子结点，或者搜索完所有点。 6. 使用完H，I 点。D也用了，先进先出的队列中剩下E 和C ,到E 7. 同理，找到了k 。结束搜索。 关键点： 向下搜索优先，数据结构来保存候选点？ ### 贝尔曼-福特算法 查找图的最短路径算法 !\[image-20200923205354827\](http://img.yayi.site/csdn/3fd022c1e263e944e37603f067a68a13.png-watermaskStyle) 1. 设置每个点的初始成本。将起点为0 ，其它为 infty 无穷∞ 2. 从所有的边里面选择一个边，为了方便，我们选择了连接staring to node 3 的边缘。 3. 分别计算从一个点追踪到选定的另一个点的成本。计算方法是"原点成本+移动成本"。计算从单方向进行，但从任何一边开始都可以。如staring node to node 3 为0+9=9 4. 如果 计算结果少于 当前 值 ，我们将用新值更新成本。 !\[image-20200923205848140\](http://img.yayi.site/csdn/c7e2e8936acb6e2985622ec348499221.png-watermaskStyle) 5. 接下来计算从相反方向node 3到 starting node 为 9 +9=18 所 以不更新。选择starting node 另一条边 6. 对所有边执行相同动作，边的顺序是任意的，这次我们选择starting node to node1 0+2=2 更新， 7. 类似的，，选 node 1 to node 3 则是 2 +6=8 更新 node 3 为 8 。发现 ，可以看出 经过 node 1 比 starting node 到 node 3 成本要低 8\< 9. !\[image-20200923210454405\](http://img.yayi.site/csdn/2b89316f8cce2ec79e8ab179f858df22.png-watermaskStyle) 8. 这时到了 node 3 点了，同样的道理 node 5 和 node 2 类似的。第一轮结果 如下 ： !\[image-20200923211240944\](http://img.yayi.site/csdn/380e61ec61dd257acada06f3bc8d020d.png-watermaskStyle) 9. 对所有的边进行重复操作，直到成本不再更新。 10. 所以找到了路径 为 staring node to node 1 to node 2 to node 4 to END node 这个算法也可以用于有 来回成本不一样的路径。也可以求负成本的值 。如果出现闭环则不行了。 --- 这算法待更新..... ### 戴克斯算法 这个比上面那个更有效。 同样的设置初始成本。起点为0，其他点为无限大。 !\[image-20200923212220344\](http://img.yayi.site/csdn/7c96658d2da343e3b1b2e689307e8b9b.png-watermaskStyle) 1. 从起点开始。从当前点追踪还未查找的点。找到的点作为下一个追踪的候选。 starting node to node 3 , starting node to node 1 2. 计算每个候选点的成本。计算方法是，"当前点的成本+移动到候选点的成本"。 如 0+2=2 。0+5=5 。如果新值小于当前值 ，则更新成本。 3. 从候选点中选择成本最低的点，在这种情况下。它将是node 3 . 因为这种情况下，通过node 1 去 node3 成本会增加？？ 4. 移动到node 3 。 候选的有 node 1 node 2 node 5 . 到 node 1 再到 node 5 最后 end 5. 重复操作直到end node 。 这个算法 是一个一个确定到每个点最短路径 来搜索图的算法 。 这个算法通过选择哪个点更有效。 也适用于来回成本不一样或者单行道的边。 但不适用于有负成本的。 这个算法 待更新。 --- ### A\*搜索算法 发音为 A star . 是戴克斯特拉算法 的发展。用来解决迷宫的最短路径 。 可以理解迷宫为成本为的相邻点。 !\[image-20200923214252299\](http://img.yayi.site/csdn/fa8627de27eda6b6e6dff105789c3bd9.png-watermaskStyle) 实际上 遍历了大部分的路径。有时候会远离目标。 A \* 算法不仅考虑到从起点开始的成本，还考虑当前点到目标的估计成本。 以目标点为圆心 ，靠近圆心。 1. 开始遍历。选择一个成本最低的点。标志已探索。计算成本。选择相加成本更少的前进。 不一定好。计算量大。 它经常用于游戏跟随玩家 的敌人AI等。 ---- 这个方法算法待更新