浅谈毒瘤算法——A*

### 注：本文后面有附加篇：$IDA*$ ### 再注：$IDA*$附加篇过会再写 --- ## $A*$ emm……说甚好呢？只能说$A*$真是个魔性的玄学东西2333 > $A*$算法，$A*$（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。 > ——百度百科 好，BB结束。 那么，$A*$到底是什么鬼呢？ 答：$A*$ $=$ $BFS$+$H(x)$。 其中，BFS懒得多说，~~为了像我这样的蒟蒻~~，贴上几句解释： ---- BFS，即$BreadthFirstSearch$，是一种通用的~~玄学~~图论搜索算法，是使用队列结构进行的玄学系列爆搜。 > 已知图$G=(V,E)$和一个源顶点$s$，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”$s$所能到达的所有顶点，并计算$s$到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为$s$且包括所有可达顶点的宽度优先树。对从$s$可达的任意顶点$v$，宽度优先树中从$s$到$v$的路径对应于图G中从$s$到$v$的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。 > 之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和$s$距离为$k$的所有顶点，然后再去搜索和$s$距离为$k+1$的其他顶点。 > ——某奆佬博客（百度百科上也有） 时间复杂度$O(RP+IQ)$。 ---- 接下来，请允许我向您们介绍$A*$算法中最玄学的玩意：上面那个式子里的$H(x)$。 #### 人类篇 $H(x)$本质上是一个~~玄学函数~~估价函数，它的意思是： 我们认为接下来从此节点到目标节点的距离为$H(x)$，实际距离为$S(x)$，则$H(x) \leq S(x)$。 所以$H(x)$~~本质上就是猜蒙试凑~~ #### 神犇篇 那么，如果发生了$H(x)> S(x)$，会发生什么？~~世界会终结~~你会爆0。 理由是：（过程自己YY） 鉴于我们的基础是BFS，所以我们在拿着一个咕价函数搞事，但实际上我们的基础还是小顶堆。（BFS只用队列的请自觉走开） 或者说，是 ```cpp priority_queue< int,vector<int>,greater<int> > PQ;//文艺小顶堆 ``` 那么，如果您因为作死，制造了一个比实际更劣的估价，我们就会悲催的发现： $\color{goldenrod}\text{你的最优解弹不出来了QAQ}$ ~~真香~~ 原因在于： 我们的小顶堆每次弹出节点代价$+$预估代价最小的节点，所以如果预估代价比实际代价劣，我们就不能弹出最优解，而是一直在次优解徘徊orz。（详情请看后面的CZ篇） #### CZ篇 以下是这个算法最~~玄妙精深~~毒瘤鬼畜的部分，$\color{red}\text{非战斗人士尽快撤离！}$ 你没有逃？勇气可嘉！ 为毛线我们要用文艺の优先队列呢？ > 因为好像只有迷宫搜索之类的才用队列，别的最优解问题好像都是用$* $顶堆来做的2333 接下来讲为什么$A*$要比文艺小顶堆+BFS优。 我们可以造一个图，比如这样：  ~~好吧我是画图画的能有多好~~ 那么，现在，别管基佬紫的两条边，只管深蓝和蓝色的那两组边。 我们发现，从A节点到γ节点距离为14，而A到δ的距离只有12。珂是，γ到B距离为1，而δ到B距离为8，在此情况下，原先被抛弃的“次优解”γ反倒变成了最优解orz，却要到很晚才会被扩展。 因此，（基佬紫警告） $\color{purple}\text{普通BFS在这样的图上是效率较低的！}$ 所以，我们要引入新的算法：$A*$玄学大法！ ---- ~~画外音：BB结束了？~~ 实际上，$A*$玄学大法主要就是看你的咕价函数的质量。比如，如果你的咕价函数$H(x)=\varrho$，其中$\varrho$为常数，那么，$A*$就只能看你RP了233 > 1968年发明的$A*$算法就是把启发式方法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一起的算法。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管$A*$基于无法保证最佳解的启发式方法，$A*$却能保证找到一条最短路径。 > ——来自某大佬翻译的$A*$介绍 那么，为啥要学习$A*$这种神仙算法呢？ > 答：因为dijkstra啥的太慢，BFS容易搞错。 好，现在继续讲废话。 估价函数不好会怎么样？  BFS写炸了会怎么样？ 瞎写咕价函数会怎么样？ 我扯完了。 继续开始讲正事吧： $A*$借鉴了各种玄学的算法，保证了可以找出最优解。那么，我们就以这道问题为例搞一搞。 [体验四川省选的力量](https://www.luogu.org/problemnew/show/P2324) ```cpp #include<cstdio> #include<iostream> #include<cstring> #define INF 536870912 using namespace std; char map[6][6]; char check[6][6]={ '0','0','0','0','0','0', '0','1','1','1','1','1', '0','0','1','1','1','1', '0','0','0','*','1','1', '0','0','0','0','0','1', '0','0','0','0','0','0', }; int xm[9]={0,-2,-2,-1,-1,1,1,2,2}; int ym[9]={0,-1,1,-2,2,-2,2,-1,1}; int ans; inline void swap(char &p1,char &p2){ char mid=p1; p1=p2; p2=mid; } inline int dif(){ int ret=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]!=check[i][j]) ret++; } } return ret; } inline void dfs(int x,int y,int d,int f){ int l=dif(); if(d+l>16) return ; if(d>=ans) return ; if(l==0){ ans=d; return ; } for(int i=1;i<=8;i++){ if((x+xm[i]<1)||(x+xm[i]>5)) continue; if((y+ym[i]<1)||(y+ym[i]>5)) continue; if(f+i!=9){ swap(map[y+ym[i]][x+xm[i]],map[y][x]); dfs(x+xm[i],y+ym[i],d+1,i); swap(map[y+ym[i]][x+xm[i]],map[y][x]); } } } inline void init(){ int x,y; for(int i=1;i<=5;i++) cin>>map[i]+1; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]=='*') { x=j; y=i; } } } ans=25; dfs(x,y,0,0); printf("%d\n",ans==25?-1:ans); } int main() { int t; scanf("%d",&t); while(t--) init(); return 0; } ``` > 来自@Luan_233 dalao的玄学$A*$ 先来围观估价函数： ```code inline int dif(){ int ret=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(map[i][j]!=check[i][j]) ret++; } } return ret; } ``` 玄学啊233 主要就是$\color{red}\colorbox{green}{逐字比对，每找到一个不同的计数加一，直到结束}$。（蒟蒻专属豪华蒟蒻色背景） 好吧。。BB不下去了，正篇结束。