A*算法的原理

A* 算法是一种高效的启发式搜索算法，在二维的栅格地图上寻路效果好，它通过估算节点的代价评估函数值并作为节点的综合优先级，当选择下一个需要遍历的节点时，再选取综合优先级最高的节点，逐步地找到最优路径。A* 算法可以快速的找到代价值最小，路程最短的路径，但是随着栅格精度的提高和地图尺寸的扩大，对无用节点的重复搜索评估会导致 A* 算法搜索时间呈指数级增长。

代价计算公式：F(n)=G(n)+H(n)

A*算法的原理之定义：

• G(x)：G(x)表示从起点A移动到网格上指定方格x的实际移动代价
• H(x)：H(x)表示从当前点x移动到终点B的预计代价（H的计算方法不固定，按照问题来修改），即用启发函数来计算当前点x移动到终点B的预计代价。
• F(x)：F(x)=G(x)+H(x)，即表示当前点x到终点B的总代价
• OPEN列表：记录下所有被考虑来寻找最短路径的各自的列表
• CLOSED列表：记录下不会再被考虑的格子
• POINT：属性：是否为障碍物，是否为父亲节点
• Path Sorting(路径排序)：具体往哪个节点移动由以下公式确定：F(x) = G(x) + H(x) 。G(x)代表的是从起点A沿着已生成的路径到指定方格x的移动开销。H(x)代表的是从当前点x移动到终点B的预计代价

A算法的原理之过程

第一步：把搜寻的区域划分成了正方形的格子，这就简化为了 2 维数组。数组的每一项代表一个格子，它的状态就是可走或不可走。这里用free[i][j]进行表示（free[i][j] == 1表示可走，free[i][j] == 0表示不可走）。现用A*算法寻找出一条自A(绿色)到B(红色)的最短路径，每个方格的边长为10，即垂直水平方向移动代价为10。因此沿对角移动开销约等于14（浮点数舍入为整数）。

第二步：从起点 A 开始，把它加入到一个由方格组成的OPEN列表中。OPEN列表里的格子是可能会是沿途经过的，也有可能不经过。因此可以将其看成一个待检查的列表。查看与A相邻的8个方格 ，把其中可走的或可到达的方格加入到OPEN列表中。并把起点 A 设置为这些方格的父节点。然后把 A 从OPEN列表中移除，加入到CLOSED列表中，CLOSED列表中的每个方格都是不需要再考虑。

如下图所示，深绿色的方格为起点A，它的外框是亮蓝色，表示该方格被加入到了OPEN列表。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点A。

第三步：从OPEN列表中选一个与起点A相邻的方格。优先选F值最小的那个。在标有字母F的方格中G = 10 （与起点直接相邻的上方，下方，左方的方格的 G 值都是 10 ，对角线的方格 G 值都是14 ）。H值通过估算起点到终点 ( 红色方格 ) 的 Manhattan 距离得到，仅作横向和纵向移动，并且忽略沿途的障碍。使用这种方式，起点右边的方格到终点有3 个方格的距离，因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ，因此 H = 40 。

比较OPEN列表中节点的F值后，发现起点A右侧节点C的F=40，值最小。选作当前处理节点，并将这个点从OPEN列表删除，移到CLOSED列表中。

对这个节点周围的8个格子进行判断，若是不可通过或已经在CLOSED列表中，则忽略该点。否则执行以下步骤：

• 若当前处理节点的相邻格子已经在OPEN列表中，则检查这条路径是否更优，即计算经由当前处理节点到达那个方格是否具有更小的G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父节点设为当前处理节点 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。
• 若当前处理节点的相邻格子不在OPEN列表中，那么把它加入，并将它的父节点设置为该节点。

按照上述规则继续搜索，选择起点A右边的方格C作为当前处理节点。它的外框是亮蓝色，被放入了CLOSED列表中。然后我们检查与它相邻的方格。它右侧的3个方格是不可达的，忽略。它左边的方格是起点A，在CLOSED列表中，也忽略。其他4个相邻的方格均在OPEN列表中，需要检查经由当前节点到达那里的路径是否更好。看看上面的方格E，它现在的G值为14 ，如果经由当前方格到达那里， G值将会为20( 其中10为从起点到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10) ，因此这不是最优的路径。当把4个已经在OPEN列表中的相邻方格都检查后，没有发现经由当前节点的更好路径，因此不做任何改变。

接下来要选择下一个待处理的节点。因此再次遍历OPEN列表，现在OPEN列表中只有7个方格，需要选择F值最小的那个。这次有两个方格的F值都是54，选哪个呢？没什么关系。从速度上考虑，选择最后加入OPEN列表的方格更快。因此选择起点右下方的方格D，如下图所示。

接下来把起点右下角F值为54的方格D作为当前处理节点，检查其相邻的方格。发现它右边是墙（墙下面的一格也忽略掉，假定墙角不能直接穿越)，忽略之。这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入OPEN列表 ，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的 3 个方格中，有 2 个已经在CLOSED列表中 ( 一个是起点A，一个是当前方格上面的方格C) ，我们忽略它们。最后一个方格，也就是当前方格D左边的方格，检查经由当前方格到达那里是否具有更小的G 值，没有。因此我们准备从OPEN列表 中选择下一个待处理的方格。
不断重复这个过程，直到把终点也加入到了OPEN列表中，此时如下图所示。注意在起点A下方 2 格处的方格的父亲已经与前面不同了。之前它的G值是28并且指向它右上方的方格D。现在它的 G 值为 20 ，并且指向它正上方的方格。这是由于在寻路过程中的某处使用新路径时G值更小，因此父节点被重新设置，G和F值被重新计算。

第四步：实际路径：从终点开始，沿着箭头向父节点移动，直至回到起点，这就是实际路径。

A*算法的原理之总结

• 把起点加入OPEN列表。
• loop：（不断重复此过程）
  • 遍历OPEN列表 ，查找F值最小的节点，把它作为当前要处理的节点，然后移到CLOSED列表中（可以用优先队列进行维护）
  • 对当前方格的 8 个相邻方格进行检查，如果它是不可抵达的或者它在CLOSED列表中，忽略它。否则，做如下操作：（完成之后goto loop）
    • 如果它不在OPEN列表中，把它加入OPEN列表，并且把当前方格设置为它的父亲
    • 如果它已经在OPEN列表中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更近。如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值。如果OPEN列表是按F值排序的话，改变后可能需要重新排序。
  • 遇到下面情况停止搜索：
    • 把终点加入到了CLOSED列表中，此时路径已经找到了
    • 查找终点失败，并且OPEN列表是空的，此时没有路径。
• 从终点开始，每个方格沿着父节点移动直至起点，形成实际路径。

A*算法的原理之应用

八数码问题

对于８数码问题，每个结点有８个数字和一个空格，可以将空格看成０，那么一共有９个数字，32位的int可以表示，可以用一个整数表示一个结点对应的信息。计算一个整数中０（即空格）的位置比较耗时间，用一个整数存储当前结点０的位置，还要存储对应的G , H值以及该结点由哪个结点扩展来的信息。

当前状态的估价函数H是当前在状态理想情况下到达目标状态的代价：比如现在走了G步，估价为H步。

如何定义估价函数H呢？

这里可以简单估计：当前状态有几处数字和对应的目标状态不同那么代价就+1。（这里的状态用string来保存，其中g是目标状态，now是当前状态，res是代价）

如何让所有的节点按照F的值进行排序呢？

定义一个优先队列，元素是节点，并且按照节点的F的值从小到大排序。

struct Node{
    string s;int F,G;
    bool operator < (Node x)const{//优先队列的排序：按F的大小从小到大
        return F>x.F;
    }
};
priority_queue<Node>q;

代码如下：

int H(string now){//估计函数H的计算：如果当前方格的数字与目标状态的对应数字不同（可省略：并且当前目标状态的数字不为0）就H(now)++，
	int res = 0;
	for(int i=0;i<9;i++){
		if (g[i]!=now[i])res++;
	}
	return res;
} 

执行A*算法的过程：

• 把起点节点加入优先队列：

  mp[s]=1;//标记初始状态
  dist[s]=0;//初始状态的移动代价为0
  q.push((Node){s,H(s),0});(s是状态，总代价是H(s)+0=H(s)，当前实际代价为0)
  

• while(队列不为空)：

  • 查找队列中F值最小的节点（即优先队列的队首元素），把它作为当前要处理的节点，然后移到CLOSED列表中（即剔除队列）
    • 找到这个节点之后需要找个0号的下标，然后将它和周围的可交换的点进行交换，得到下一个节点的相关信息，并且根据它是否到达过以及它的实际代价dist是否可以更新来决定是否进入队列
  • 遇到下面情况停止搜索：
    • 把终点加入到了CLOSED列表中，此时路径已经找到了，直接输出答案：now.F或者now.G.
    • 查找终点失败，并且队列是空的，此时没有路径。

代码如下：参考题目—洛谷-P1379 八数码难题[https://www.luogu.com.cn/problem/P1379]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
int a[4][4];
string g="123804765";//目标状态
int dx[5]={0,1,-1,0};
int dy[5]={1,0,0,-1};//上下左右的移动
int sx=0,sy=0;//0的坐标
string s;//初始状态
unordered_map<string,bool>mp;unordered_map<string,int>dist;
struct Node{
    string s;int F,G;
    bool operator < (Node x)const{//优先队列的排序：按F的大小从小到大
        return F>x.F;
    }
};
bool check(string now){//判断当前状态now是否等于目标状态
    if(now==g)return 1;
    return 0;
}
int H(string now){//估计函数H的计算：如果当前方格的数字与目标状态的对应数字不同（可省略：并且当前目标状态的数字不为0）就H(now)++，
	int res = 0;
	for(int i=0;i<9;i++){
		if (g[i]!=now[i]&&g[i]!= 0)res++;
	}
	return res;
} 
void A_STAR(){
    priority_queue<Node>q;
    mp[s]=1;//标记初始状态
    dist[s]=0;//初始状态的移动代价为0
    q.push((Node){s,H(s),0});//将初始状态节点加入优先队列
    while(!q.empty()){
        Node now=q.top();q.pop();
        string now_sta=now.s;
        if(check(now_sta)){//当前节点的粘贴就是目标状态则直接输出答案 此时now.F=now.G
            cout<<now.F<<endl;
            exit(0);
        }
        for(int i=0;i<9;i++){
            if(now_sta[i]-'0'==0)sx=i/3+1,sy=i%3+1;//计算0的二维坐标
        }
        int index_zero=3*(sx-1)+(sy-1);//计算0在now_sta中的下标
        for(int i=0;i<4;i++){
            int nex=sx+dx[i],ney=sy+dy[i];//下一个相邻节点
            if(nex<1||nex>3||ney<1||ney>3)continue;//越界则忽略
            int index_now=3*(nex-1)+(ney-1);//下一个相邻节点在sta_now中的下标
            swap(now_sta[index_zero],now_sta[index_now]);//交换该节点和0，相当于把该节点移动到了0处，0移动到了该相邻节点
            if(!mp[now_sta]||(mp[now_sta]&&(now.G+1)<dist[now_sta])){//如果now_sta未到达过或者now_sta到达过但是发现它的代价可以更加优化则更新
                dist[now_sta]=now.G+1;
				q.push((Node){now_sta,H(now_sta)+now.G+1,now.G+1});//将新的状态节点加入优先队列
				mp[now_sta]=1;//标记掉该状态：表明到达过该点
            }
            swap(now_sta[index_zero],now_sta[index_now]);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>s;
    if(check(s)){//特判初始状态==目标状态
        cout<<0<<endl;
    }
    else{//否则直接执行A*算法
        A_STAR();
    }
    return 0;
}

求解K短路问题

k短路定义：

要求在一张有向带权图G中，从起点s到终点t的可重复经过同一点的不严格递增的第k短路的长度。（默认边权非负）

对于一条边e，定义它的边权为w，起点为u，终点为v。d(u,v)表示u到v的最短距离。

思路：

总所周知，解决k短路问题的经典算法是A*，算法核心在于对当前状态的估价。

主要流程如下：

• 将所有边反向并使用最短路算法（spfa和dijkstra即可），得到任意一点v到终点t的最短路径d(v,t)
• 一开始状态位于点s，假设经过一段时间走到了点v，那么定义当时的预估代价F为已经走过的路径长度+d(v,t)
• 用一个堆Q来维护所有状态的预估代价F，每次从Q中取出预估代价F最小的状态，枚举其下一步走的边，将新的状态及其预估代价F放入Q中。（Q可以是优先队列，并且设置一个结构体存储状态信息）
• 直到找到k条s到t的路径

数据规模：

如果这张图恰好是一个n元环，那么A*的时间复杂度为O(nk)。

A算法和A*算法的区别

A算法由 f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)两个因素决定， g ( n ) g(n) g(n)是这一步的实际代价函数, h ( n ) h(n) h(n)是这一步的预估代价函数。

A*算法评判函数也是 f ( n ) = g ∗ ( n ) + h ∗ ( n ) f(n)=g_{ *}(n)+h_{ *}(n) f(n)=g∗​(n)+h∗​(n)，只不过加了约束条件， g ∗ ( n ) > 0 ， h ∗ ( n ) < = 任 意 h ( n ) g_{ *}(n)>0，h_{ *}(n)<=任意h(n) g∗​(n)>0，h∗​(n)<=任意h(n)

以上只是定义，对于一个实例来说， h ( n ) h(n) h(n)由很多种， h ( n ) h(n) h(n)只是估值函数的一个集合，有各种方法 h 1 ( n ) h 1 ( n ) h 2 ( n ) h 2 ( n ) h 3 ( n ) h 3 ( n ) … h1(n)h1(n)h2(n)h2(n)h3(n)h3(n)… h1(n)h1(n)h2(n)h2(n)h3(n)h3(n)…,取其中任意一个方法带入上述公式，组成评判函数，都是A算法的实现，现在取从集合中一个函数 h ∗ ( n ) h_{*}(n) h∗​(n)，使得它比集合中任意的函数都优秀，这样的算法叫A*算法。也就是A *算法是最优的A算法（因为估值函数最优）！

A算法本质上是图搜索和启发式函数的结合，这个启发式函数当然可以自己定义，而且具有多样性。A* 算法是在A算法的基础上，每一次都选择最佳节点产生后继，并且人为的规定最小费用的估计始终满足 h ≤ h*，防止搜索过程中偏离期望的最佳路径。(若偏离则搜索停止，说明问题可能无解，或最小费用的估计过小)在这种情况下，若问题有解，则一定可以通过 A * 算法找到最优解，该性质被称为可采纳性。

例如:八数码问题中，可以将初始状态下每个数字移动到相应位置的步数之和定义为 h ∗ ( n ) h_{ *}(n) h∗​(n)，此时搜索过程中就不会搜索到多余步骤的解，此时相当于优化了A算法的搜索模式。