【笔记】A* 算法与IDA*算法
zyctc
·
·
个人记录
A*寻路
参考资料1 CSDN-关于A*寻路算法正确性证明的笔记
若干定义
A* 可以理解为在 bfs 时将队列中的元素按 f(x)=g(x)+h(x) 排序从而提高算法效率。
其中 g(x) 表示从点 st 到达节点 x 的当前最小代价。 g^* (x) 表示从点 st 到达节点 x 的实际最小代价。 g(x) 可能会随着寻路过程更新。 并且当 g(x) 从 OPEN 表中移去时，满足 g(x)=g^* (x) 。
显然的，$ h(x) $ 越接近 $ h^* (x) $，算法优化程度越高。$ h(x)=0 $ 时，算法退化为普通 bfs。
A* 算法正确性的充分条件是 $ g^* (x)\leq g(x) $ 且 $ h(x)\leq h^* (x) $，后面会给出证明。
## 算法流程
```
给出一张OPEN表，一张CLOSE表。两张表初始时都是空。
1. 将初始节点st加入OPEN表中，st的父节点为NULL；
2. 检查OPEN表是否为空，若为空，则无解，退出算法；
3. 把OPEN表中f值最小的节点取出，放入CLOSE表中，并记该节点为x；
4. 考察节点x是否为目标节点，若是，则问题求得解，退出算法；否则继续以下流程；
5. 考察节点x的任一相邻可达节点y
(1)如果y不在OPEN表和CLOSE表中，把它加入OPEN表中，并认为此时节点y的父节点为x，计算g(y)的值并计算f(y)的值；
(2)如果y已经在OPEN表当中，检查是否需要更新g(y)，若需要，则更新，并把y的父节点改成x节点；
(3)如果y在CLOSE表中，判断g(y)是否需要更新，若需要更新，则更新g(y)，更新y的父节点为x，把y节点从CLOSE中删除后放入OPEN表中；
6. 排序后，跳转到2继续操作。
跳出算法的循环后，若有解，根据end节点的父节点，依次回退到起点st，就是要找的路径。
```
### 小tips-关于重载运算符
```cpp
struct node{int val,key;};
bool operator < (const node & a,const node &b){
return a.key>b.key;//优先队列的排序是反过来的
}
priority_queue<node>q;//默认的小根堆
```
## 正确性
假设一条从 $ v_0 $ 到 $ v_{k+1} $ 的最短路径为 $ Pst $ 。
设 $ |Pst|=N $ ， $ |Pstar|=M $ 。则 $ N<M $ 。
设路径 $ Pst $ 为 $ v_0->v_i->v_{k+1} (i \in [1,k])$ 。
在算法中，我们总是取 $ OPEN $ 表中 $ f $ 值最小的节点进行后续操作。
在这里， $ f(v_{k+1})=g(v_{k+1})+h(v_{k+1}) $ 。 $h(v_{k+1})=h^* (v_{k+1})=0$。
$g(v_0)=g^* (v_0)=0$。算法的第一步为将 $v_0$ 加入 $ OPEN $ 列表。
假设 $v_i$ 在 $ OPEN $ 列表取出时有 $ g(v_i)=g^* (v_i) $。
因为 $ f(v_i)=g^* (v_i)+h(v_i) ≤ g^* (v_i) + h^* (v_i)=N<M $ 。这意味着，如果想通过 $ A^* $ 算法对 $ end $ 节点操作，那么必须在此之前已经对节点 $ v_i $ 操作过了。
假设在算法进行到某一刻，取了 $OPEN$ 表中 $v_i$ 节点，将它放入 $CLOSE$ 表，考虑它相邻的节点。显然的， $v_{i+1}$ 与 $v_i$ 相邻。
若 $v_{i+1}$ 未在 $OPEN$ 表中，则将 $v_{i+1}$ 放入 $OPEN$ 表中。
若 $v_{i+1}$ 已经在 $CLOSE$ 表中，则意味着 $v_{i+1}$ 在取出 $end$ 前进行过操作。所以 $v_{i+1}$ 最后一定会在取出节点 $end$ 前放入 $OPEN$ 表中。
考虑 $g(v_{i+1})$ 的值。若更新，则有 $ g(v_{i+1})=g^*(v_i)+ |Pst(v_i->v_{i+1})| =|Pst(st->v2)|=g^*(v_{i+1}) $ 。又因为在任意时刻 $ g^* (v_{i+1}) \leq g(v_{i+1})$，因此此次更新后必然有 $g(v_{i+1})= g^* (v_{i+1}) $。且若 $g(v_{i+1})$ 没被加入 $OPEN$ 表中，意味着 $v_{i+1}$ 曾满足 " 在 OPEN 表中，且 $g(v_{i+1})= g^* (v_{i+1}) $ "。
因此有对于 $i \in [0,k+1]$ ，$g(v_i)= g^* (v_i) $ 。而 $f(v_{k+1})=g(v_{k+1})+h(v_{k+1})=g*(v_{k+1})$，根据 $g(x)$ 定义 ，此时有 $ |Pastar|=g（end）=g*（end）=|Pst| $ ，即 $ N=M $ ，这显然与我们最初的假设“通过A*算法找到的路径不是最小值，也就是N<M”矛盾。所以假设不成立，通过A*算法找到的就是最短路径。
> note 2026.04.14
>
> 注意限制 $h(x)\le h^*(x)$ 是充分条件，而非必要条件。不要考虑为什么他是“对的”，而要考虑这个巧妙的限制提供了算法的正确性。
>
> 一个直观的正确理解是，在该条件成立时，设最段路径长为 $C$，目标节点为 $T$，则正确路径上都有
> $$
> f(x)=g(x)+h(x)\le g(x)+h^*(x)=C
> $$
>
> 非最短的路径必然有
>
> $$
> f(T)=g(T)+h(T)=g(T)=C'\gt C
> $$
>
> 不难看出非最优解的更新一定不会出现在最优解的更新前。
# IDA*
## 算法流程
在dfs迭代加深的基础上加上估价函数即可
~~迭代加深是怎么加上估价函数的呢？迭代加深相信大家都很熟悉，但是迭代加深是怎么加上估价函数的呢，下面就让小编带大家一起了解吧。~~
```cpp
void dfs (int step) {
if (step + h() >= Min) return;
//...
}
```
# 题
## [[SCOI2005]骑士精神](https://www.luogu.com.cn/problem/P2324)
### 题目描述
给定 5*5 的棋盘，棋盘上有 12 个白色的骑士和 12 个黑色的骑士，且有一个空位。每次使一个骑士按日字移动到空位上，求变为目标棋盘的最少步数。
若最少步数多于 15，输出-1
共 T (T ≤ 10) 组数据
### Solution
估价函数：
```cpp
int ck[maxn][maxn]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};
int check(){
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[i][j]!=ck[i][j])res++;
return res;
}
```
其中 ```mp[i][j]``` 表示当前棋盘第 $i$ 行，第 $j$ 列骑士颜色，```0``` 为白, ```1``` 为黑
## [[COCI 2009] POSLOZI](https://www.luogu.com.cn/problem/P5183)
### 题目描述
给定一个长为 $n(n\leq12)$ 的排列和 $m$ 个操作，每个操作能交换两个数 $a[i], a[j]$。求使原排列变为 $1,2,\dots,n$ 的最少操作数和具体操作。
### Solution
考虑预处理从一个位置到另一位置的最小步数```mp[i][j]```，估价函数即：
```cpp
int h(){
int res=0;
for(int i=1;i<=n;i++)
res+=mp[i][a[i]];
return ((res+1)>>1);
}
```
## [旋转游戏 The Rotation Game](https://www.luogu.com.cn/problem/UVA1343)
~~这题我云的~~
### 题目描述
如图所示，有一个 “#” 形的棋盘，上面有 1,2,3 三种数字各 8 个。给定 8 种操作，分别为图中的 A∼H。这些操作会按照图中字母与箭头所指明的方向，把一条长度为 8 的序列循环移动 1 个单位。
例如下图最左边的 “#” 形棋盘执行操作 A 时，会变为图中间的 “#” 形棋盘，再执行操作 C 后会变为图中最右边的 “#” 形棋盘。
### Solution
考虑每次操作最多在中间八个中增加一个相同的数，有估价函数：
```cpp
int h(){
int cnt[4]={0,0,0,0};
for(int i=0;i<8;i++)
cnt[mp[center[i]]]++;
return 8-max(cnt[1],cnt[2],cnt[3]);
}
```
## [机关](https://www.luogu.com.cn/problem/P5507)
### 题面描述
给定 12 个按钮的初始状态和目标状态，每个按钮的状态为1~4。每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转。
### Solution
考虑到每次旋转最多使两个按钮状态离目标状态更近一步，有估价函数：
```cpp
int h(int s[]){
int cnt=0;
for(int i=1;i<=12;i++)
cnt+=((tar[i]-s[i])%4+4)%4;
return cnt/2;
}
```
## [[AHOI2012]铁盘整理](https://www.luogu.com.cn/problem/P2534)
### 题目描述
给定 $n(n\leq 16)$ 个大小不同的铁盘，每次操作可以翻转最上面若干个铁盘，求使铁盘按从小到大排序的最少操作次数。
### Solution
考虑到每次翻转最多改变一对相邻数的差，因此有估价函数：
```cpp
int h(){
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=(abs(a[i]-a[i+1])!=1);
return cnt;
}
a[n+1]=n+1;
```
# 基于 A* 的 k 短路算法
给定一张有向有权图和$st$、$ed$，求 $st$ 到 $ed$ 的前 $k$ 短路。~~（虽然基本上A* 都会被卡）~~
## 算法流程
有 $f(x)=g(x)+h(x)$，其中 $g(x)$ 为当前搜到的路径长度，$h(x)$为估价函数。此处 $h(x)$ 等于 $x$ 到 $ed$ 的最短路，用 $spfa/dijkstra$ 预处理。
从1出发保留所有走出去的路，同时把 spfa 的队列换成优先队列。每次取出来到了哪个点就计数x++，若 x>=k 则不再计入路径。因为估价函数为到 $ed$ 的最短路，因此到达了终点K次就退出。
### 关于每个点扩展次数不超过k次的证明
假设有一点 $x$ 需被扩展 $>k$ 次，即有一路径 $P_x : st-x_1-x-ed$ 满足在前 $k$ 短中，且在 $x_1$ 前已有 $>k$ 次对 $x$ 点的扩展。
不妨设前 $k$ 次扩展中仅有 $m$ 条路径满足 $g(x_i)+edge(x_i,x)>g(x_1)+edge(x_1,x)$，则因为该 $m$ 个点较 $x_1$ 提前取出更新，有 $f(x_i)=g(x_i)+min\_len(x_i,ed) <= f(x_1)=g(x_1)+min\_len(x_1,ed) <= g(x_1)+edge(x_1,x) +min\_len(x,ed) = P_x$。
即至少有 $k-m$ 条经过 $x$ 的路径短于 $P_x$，且至少有 $m$ 条走到 $x_i$ 后直接走最短路（不经过 $x$，因为 $f(x_i)<=f(x_1)<=P_x<g(x_i)+edge(x_i,x)++min\_len(x,ed)$）的路径短于 $P_x$，与假设矛盾。
## 部分代码
```cpp
void A_s(int k){
priority_queue<node>q;
q.push((node){1,0,ldis[1]});
while(!q.empty()){
node u=q.top();q.pop();
if(u.f>E)return ;
ccnt[u.id]++;
if(u.id==n){
E-=u.f,ans++;
continue;
}
if(ccnt[u.id]>k)continue;
for(int i=hd_e[u.id];i;i=e[i].nxt)
q.push((node){e[i].t,u.h+e[i].w,u.h+e[i].w+ldis[e[i].t]});
}
}
int main(){
//输入
spfa();
A_s(k);
//输出
return 0;
}
```