A*算法的原理及应用
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：属性：是否为障碍物，是否为父亲节点PathSorting(路径排序)：具体往哪个节点移动由以下公式确定：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列表中，忽略它。否则，做如下操作：（完成之后gotoloop）如果它不在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的值从小到大排序。
structNode{strings;intF,G;booloperator//估计函数H的计算：如果当前方格的数字与目标状态的对应数字不同（可省略：并且当前目标状态的数字不为0）就H(now)++，intres=0;for(inti=0;is,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]
#includeusingnamespacestd;typedeflonglongll;constintmaxn=1e6+50;inta[4][4];stringg="123804765";//目标状态intdx[5]={0,1,-1,0};intdy[5]={1,0,0,-1};//上下左右的移动intsx=0,sy=0;//0的坐标strings;//初始状态unordered_mapmp;unordered_mapdist;structNode{strings;intF,G;booloperator//判断当前状态now是否等于目标状态if(now==g)return1;return0;}intH(stringnow){//估计函数H的计算：如果当前方格的数字与目标状态的对应数字不同（可省略：并且当前目标状态的数字不为0）就H(now)++，intres=0;for(inti=0;ipriority_queueq;mp[s]=1;//标记初始状态dist[s]=0;//初始状态的移动代价为0q.push((Node){s,H(s),0});//将初始状态节点加入优先队列while(!q.empty()){Nodenow=q.top();q.pop();stringnow_sta=now.s;if(check(now_sta)){//当前节点的粘贴就是目标状态则直接输出答案此时now.F=now.Gcoutintnex=sx+dx[i],ney=sy+dy[i];//下一个相邻节点if(nex3||ney3)continue;//越界则忽略intindex_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)now_sta,H(now_sta)+now.G+1,now.G+1});//将新的状态节点加入优先队列mp[now_sta]=1;//标记掉该状态：表明到达过该点}swap(now_sta[index_zero],now_sta[index_now]);}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>s;if(check(s)){//特判初始状态==目标状态cout