A*


本页面将简要介绍 A*算法。

定义

A*搜索算法(英文:A*search algorithm,A*读作 A-star),简称 A*算法,是一种在图形平面上,对于有多个节点的路径求出最低通过成本的算法。它属于图遍历(英文:Graph traversal)和最佳优先搜索算法(英文:Best-first search),亦是

BFS 的改进。

过程

定义起点 ,终点 ,从起点(初始状态)开始的距离函数 ,到终点(最终状态)的距离函数 1,以及每个点的估价函数

A*算法每次从优先队列中取出一个 最小的元素,然后更新相邻的状态。

如果 ,则 A*算法能找到最优解。

上述条件下,如果 满足三角形不等式,则 A*算法不会将重复结点加入队列。

时,A*算法变为

Dijkstra;当 并且边权为 时变为
BFS

例题

题目大意:在 的棋盘上,摆有八个棋子,每个棋子上标有 的某一数字。棋盘中留有一个空格,空格用 来表示。空格周围的棋子可以移到空格中,这样原来的位置就会变成空格。给出一种初始布局和目标布局(为了使题目简单,设目标状态如下),找到一种从初始布局到目标布局最少步骤的移动方法。

    123
    804
    765

函数可以定义为,不在应该在的位置的数字个数。

容易发现 满足以上两个性质,此题可以使用 A*算法求解。


按顺序求一个有向图上从结点 到结点 的所有路径最小的前任意多(不妨设为 )个。

很容易发现,这个问题很容易转化成用 A*算法解决问题的标准程式。

初始状态为处于结点 ,最终状态为处于结点 ,距离函数为从 到当前结点已经走过的距离,估价函数为从当前结点到结点 至少要走过的距离,也就是当前结点到结点 的最短路。

就这样,我们在预处理的时候反向建图,计算出结点 到所有点的最短路,然后将初始状态塞入优先队列,每次取出 最小的一项,计算出其所连结点的信息并将其也塞入队列。当你第 次走到结点 时,也就算出了结点 到结点 短路。

由于设计的距离函数和估价函数,每个状态需要存储两个参数,当前结点 和已经走过的距离

我们可以在此基础上加一点小优化:由于只需要求出第 短路,所以当我们第 次或以上走到该结点时,直接跳过该状态。因为前面的 次走到这个点的时候肯定能因此构造出 条路径,所以之后再加边更无必要。

参考资料与注释

Footnotes

  1. 此处的 h 意为 heuristic。详见 启发式搜索 - 维基百科A*search algorithm - Wikipedia 的 Bounded relaxation 一节。

贡献者:@Yufan@WenzelTian@ree-chee@interestingLSY@kenlig@mgt@Leo@Xeonacid@夜轮_NachtgeistW@Shuhao@ksyx@Henry-ZHR@ouuan@LKM@Haoshen@hsfzLZH1@WanZ@心旷神怡@Ir1d

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组