2020-2021:teams:no_morning_training:a_算法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:a_算法 [2020/05/22 22:46] nomansland 创建 |
2020-2021:teams:no_morning_training:a_算法 [2020/05/29 21:28] (当前版本) nomansland |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====A*算法===== | =====A*算法===== | ||
| + | A*算法与寻找最短路径的Dijkstra算法有相似之处。（不如说A*其实是Dijkstra的改版） | ||
| + | A*算法的应用场景仅限寻找起始状态到目标状态之间的最短路（Dijktra能找到起始状态到所有节点的最短路）。 | ||
| + | ====原理==== | ||
| + | A*算法最特别之处就是估价函数F(n)=G(n)+H(n)\\ | ||
| + | 其中F(n)表示起始状态经过状态n到目标状态的估计代价\\ | ||
| + | G(n)表示起始状态到状态n的最小代价\\ | ||
| + | H(n)表示状态n到目标状态的估计代价\\ | ||
| + | 与Dijkstra算法一样，所有的状态（点）可分为三类:\\ | ||
| + | 黑色：已经确定了起始状态到其的最短路\\ | ||
| + | 灰色：即将访问\\ | ||
| + | 白色：尚未访问\\ | ||
| + | 从起始状态开始（起始状态标黑），将其能到达的所有状态标灰，确定他们的G值（暂时）、H值，并算出F值。\\ | ||
| + | 接下来重复一下操作： | ||
| + | - 寻找灰色状态中F值最小的，成为当前状态\\ | ||
| + | - 当前状态标黑(即G值已确定)\\ | ||
| + | - 对于当前状态能到达的状态： | ||
| + | - 如果它是黑色，则略过。 | ||
| + | - 如果它是白色，计算它的G、H、F值，并标灰，把当前状态作为其父状态。 | ||
| + | - 如果它是灰色，检查G值能否更新，若能，则更新G、F，并将其父状态改为当前状态。 | ||
| + | - 若目标状态被标黑，则最短路径已找到。 | ||
| + | - 若目标未黑而已没有灰色状态，则路径不存在。 | ||
| + | ====与Dijkstra比较==== | ||
| + | Dijkstra仅以最短路径(即A*中的G)为优先搜索的判断依据；A*加入了H(n)更关注到目标状态的最短路。\\ | ||
| + | Dijkstra可应用于抽象的图模型，而A*因为需要构建H(n)估价函数，若图比较抽象，则构建有困难。\\ | ||
| + | ====关于估价函数H(n)==== | ||
| + | 有几种不同的构建方法。 | ||
| + | -直线距离。 | ||
| + | -曼哈顿方法，即在瓦块图中，水平距离加垂直距离。 | ||
| + | ====IDA*算法==== | ||
| + | A*算法存在一定的缺陷。\\ | ||
| + | 我们需要维护一个灰色和黑色节点列表，并且需要不时进行排序操作，需要占用大量的空间和时间。\\ | ||
| + | 为了结局这个问题，我们引入了ID（迭代加深）的思想，也就是在[[2020-2021:teams:no_morning_training:深度优先搜索及其优化|深搜]]里提到的限制深度。\\ | ||
| + | 我们设定一个H函数的阈值maxH，其最初为初始点的H值。然后进行深度优先搜索，过程中忽略所有H值大于maxH的节点；若没有解，则加大阈值maxH，重复。\\ | ||
| + | IDA*算法的优点是不用排序，不用保存节点。\\ | ||
| + | 也可把IDA*理解为在IDDFS基础上加了A*算法里F函数的剪枝。 | ||
| + | |||
2020-2021/teams/no_morning_training/a_算法.1590158790.txt.gz · 最后更改: 2020/05/22 22:46 由 nomansland
