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