淺談 A* 算法

概論

計(jì)算最短路，通常使用兩種算法：BFS 或 Dijkstra，前者用于無權(quán)圖，后者用于有權(quán)圖。

兩者都是計(jì)算單源多匯最短路的算法，現(xiàn)在我們考慮一種更特殊的情況，即單源單匯最短路。

由于有“單匯”這一特殊條件，我們可以思考是否擁有優(yōu)化的空間。

于是，我們有 A* 算法，是一種啟發(fā)式搜索算法，它能夠計(jì)算單源單匯最短路，可看作對于 BFS 和 Dijkstra 針對“單匯”這一特性的優(yōu)化。

算法流程與分析

記 \(dis[i]\) 為 \(i\) 點(diǎn)到起點(diǎn)的最短距離。

與堆優(yōu)化 Dijkstra 相同，我們維護(hù)一個(gè)優(yōu)先隊(duì)列。

開始，初始化源點(diǎn) \(dis[start] = 0\)，其余點(diǎn) \(dis\) 設(shè)為無窮大，并將起點(diǎn)入隊(duì)。

之后，不斷取出堆頂元素 \(u\)，遍歷其鄰居 \(v\)，記兩者邊權(quán)為 \(w\)，如果 \(dis[v] > dis[u] + w\)，就令 \(dis[v] > dis[u] + w\)，最后將 \(v\) 入隊(duì)。

如果取出了匯點(diǎn)，則結(jié)束循環(huán)。

可以看到，其過程事實(shí)上與堆優(yōu)化 Dijkstra 完全相同，從而 A* 算法也只能處理沒用負(fù)權(quán)的最短路，兩者區(qū)別在于優(yōu)先隊(duì)列的排序。

A* 算法的優(yōu)先隊(duì)列中根據(jù)節(jié)點(diǎn)的 \(f(x)\) 從小到大排序，其中 \(f(x) = g(x) + h(x)\)，\(g(x)\) 表示源點(diǎn)到點(diǎn) \(x\) 的最短路徑（即 \(dis[x]\)），\(h(x)\) 是 \(x\) 點(diǎn)到匯點(diǎn)的最短路的一個(gè)估價(jià)函數(shù)（也就是對到匯點(diǎn)最短路的一個(gè)估計(jì)）。

因此，A* 算法的優(yōu)化其實(shí)就體現(xiàn)在引入了一個(gè)估價(jià)函數(shù)，每一次選擇 \(f(x)\) 最小的，也就是選擇估計(jì)最有可能在最短路上的點(diǎn)優(yōu)先訪問，便能提高優(yōu)先訪問到匯點(diǎn)的概率，使得搜索范圍降低，帶來了常數(shù)上的優(yōu)化，其中 \(h(x)\) 越接近實(shí)際最短路，算法越快（但不能超過，詳見性質(zhì) \(1\)）。

值得注意的是，由于在排序上多引入了一個(gè) \(h(x)\) 函數(shù)，導(dǎo)致其與 Dijkstra 產(chǎn)生了差異：彈出堆頂?shù)狞c(diǎn)此時(shí)的 \(dis\) 并不一定是最短的，也就是說一個(gè)點(diǎn)被彈出堆頂后的 \(dis\) 仍然有可能被松弛，然后再次入堆（當(dāng)然，一個(gè)好的 \(h(x)\) 函數(shù)不會(huì)讓一個(gè)點(diǎn)重復(fù)入堆，詳見性質(zhì) \(2\)）。

特別地，當(dāng) \(h(x) = 0\) 時(shí)，A* 退化為 Dijkstra，當(dāng) \(h(x) = 0\) 且邊權(quán)為 \(1\) 時(shí)，A* 退化為 BFS。

性質(zhì)

1. \(h(x)\) 是低估函數(shù)是 A* 算法正確的充分條件

記 \(x\) 到匯點(diǎn)的真實(shí)最短路長度為 \(h'(x)\)。

\(h(x)\) 可以低估，不能高估，也就是說 \(h(x) \le h'(x)\)。

證明如下：

令 \(h(x)\) 為低估函數(shù)，記源點(diǎn)為 \(s\)，匯點(diǎn)為 \(t\)。

假設(shè)最后得到的 \(dis[t]\) 錯(cuò)誤，由于 \(dis[t]\) 必然是路徑累加而成，所以 \(dis[t]\) 必然是相對正確結(jié)果大。

那么既然算法結(jié)束，t 必然已經(jīng)出堆，也就是堆中不存在 \(f(x)\) 比 \(f(t) = g(t) + h(t) = g(t) = dis[t]\) 小（低估函數(shù)，\(h(t)\) 必為 \(0\)）。

現(xiàn)在我們考慮原先 \(s\) 到 \(t\) 的最短路，記 A* 此時(shí)沿著這條路徑走到了 \(u\)（已出堆），再記在最短路上 \(u\) 后面點(diǎn)為 \(v\)，此時(shí) \(v\) 在堆中，那么我們有：

這與“堆中不存在 \(f(x)\) 比 \(f(t)\) 小”的結(jié)論矛盾，故假設(shè)不成立，得證。

簡單地說，就是不管錯(cuò)誤的路徑的估價(jià)多么小，能夠被優(yōu)先訪問，但只要到達(dá)與匯點(diǎn)相鄰的點(diǎn)，便會(huì)將 \(f(t)\) 放入堆中，此時(shí)的 \(f(t)\) 必然就是這條路徑的真實(shí)長度，由于 \(h(x)\) 是低估函數(shù)，所以真實(shí)沿著最短路走到的點(diǎn)的 \(f(x)\) 必定不大于實(shí)際最短路，更加小于之前放入的 \(f(t)\)，使得錯(cuò)誤的 \(f(t)\) 將始終被卡在后面，不會(huì)出堆，那么也就是只有對的才會(huì)出堆。

反之，如果高估，就可能導(dǎo)致真實(shí)的最短路被高估得大于入堆的錯(cuò)誤路徑長度，以至于錯(cuò)誤的會(huì)被先彈出。

2. \(h(x)\) 滿足一致性能使得出堆的點(diǎn)的 \(dis[i]\) 必為最小值

一致性是對于所有的邊 \((u,v)\)，都保證 \(h(u) \le w(u, v) + h(v)\)（滿足三角不等式）。

只要滿足一致性，那么出堆的點(diǎn)的 \(dis[i]\) 就必為最小。

證明如下：

若 \(g(u)\) 能更新 \(g(v)\)，則有 \(g(u) + w(u,v)< g(v)\)。

結(jié)合一致性 \(h(u) \le w(u,v) + h(v)\)，累加兩式，得 \(f(u) < f(v)\)，則 \(u\) 優(yōu)先于 \(v\) 出堆。

對于所有點(diǎn)，能夠更新它的點(diǎn)都在它之前出堆，也就是在它之后出堆的點(diǎn)不能更新它，這使得其出堆時(shí)的 \(dis\) 無法被松弛，即為最小。

因此我們需要注意，A* 算法與 Dijkstra 不一樣的地方在于，不一定能在一個(gè)點(diǎn)出堆后發(fā)現(xiàn)其被訪問過就跳過這個(gè)點(diǎn)，此步驟僅能在滿足一致性的情況下能夠使用。

例題

羅密歐與朱麗葉

題目大意

給出一個(gè) \(n \times m\) 的迷宮，在兩個(gè)位置分別有兩個(gè)人，兩者每秒分別都能往上下左右走一格，求他們相遇需要至少幾秒鐘。

數(shù)據(jù)范圍

\(1<n,m\le 2000\)

解題思路

問題可以簡化為求兩者最短路，最后答案除以 \(2\) 即可。

由于無邊權(quán)，采用 A* 的 BFS 寫法。

這是一個(gè)網(wǎng)格圖問題，對于網(wǎng)格圖，我們通常取到終點(diǎn)的曼哈頓距離作為估價(jià)函數(shù)，即 \(h(x) = |x_{end} - x|+|y_{end} - y|\)。

估價(jià)函數(shù)顯然是低估的。

估價(jià)函數(shù)也符合一致性，走一步曼哈頓距離只會(huì)減小 \(1\)，則有 \(h(u) = w(u, v) + h(v)\)，一致性成立。

故套用模板即可。

代碼實(shí)現(xiàn)

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 2e3 + 10;

struct node
{
	int x, y, f;
	bool operator < (const node &a) const
	{
		return f > a.f;
	}
};

int n, m, sx, sy, ex, ey;
bool b[N][N], vis[N][N];
int dis[N][N];
int dx[10] = {0, 1, 0, -1, 0};
int dy[10] = {0, 0, 1, 0, -1};

priority_queue<node> q;

int h(int x, int y)
{
	return abs(ex - x) + abs(ey - y);
}

int astar()
{
	dis[sx][sy] = 0;
	q.push((node) {sx, sy, h(sx, sy)});
	while (!q.empty())
	{
		int x = q.top().x, y = q.top().y;
		q.pop();
		if (vis[x][y])
		{
			continue;
		}
		vis[x][y] = 1;
		if (x == ex && y == ey)
		{
			return dis[x][y];
		}
		for (int i = 1; i <= 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && b[nx][ny] && dis[nx][ny] > dis[x][y] + 1)
			{
				dis[nx][ny] = dis[x][y] + 1;
				q.push((node){nx, ny, dis[nx][ny] + h(nx, ny)});
			}
		}
	}
	return -1;
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char ch;
			cin >> ch;
			if (ch == 'o')
			{
				b[i][j] = 1;
			}
			else if (ch == '#')
			{
				b[i][j] = 0;
			}
			else if (ch == 'R')
			{
				b[i][j] = 1;
				sx = i, sy = j;
			}
			else
			{
				b[i][j] = 1;
				ex = i, ey = j;
			}
			dis[i][j] = 1e9;
		}
	}
	int ans = astar();
	if (ans == -1)
	{
		cout << "forever" << endl;
	}
	else
	{
		cout << fixed << setprecision(1) << 1.0 * ans / 2 << endl;
	}
	return 0;
}

無人駕駛

題目大意

給出一個(gè) \(n\times m\) 的迷宮，空地上有 \(1\sim 9\) 的數(shù)字表示走入這一格的費(fèi)用，并且還有 \(p\) 次撞破墻走入該格子的機(jī)會(huì)，會(huì)產(chǎn)生 \(1\) 的額外費(fèi)用，求從 \((a, b)\) 到 \((n, m)\) 的最小代價(jià)。

數(shù)據(jù)范圍

\(a \le n \le 200\)，\(b \le m \le 200\)，\(p \le 40\)

解題思路

由于有邊權(quán)，采用 A* 的 Dijkstra 寫法。

對于估價(jià)函數(shù)，我們?nèi)匀徊捎玫浇K點(diǎn)的曼哈頓距離，證明已經(jīng)給出。

這里還有 \(p\) 次撞墻的機(jī)會(huì)，考慮使用拆點(diǎn)和分層圖解決，將一個(gè)點(diǎn) \((x, y)\) 拆成若干個(gè)點(diǎn) \((x, y, p)\)，其中 \(p\) 表示還有幾次撞墻的機(jī)會(huì)。

撞墻實(shí)際上就是從 \((x, y, p)\) 走到 \((nx, ny, p - 1)\)，邊權(quán)為 \(1\)，其他情況照做即可。

答案即為 \(\min_{0 \le x \le p}(n, m, x)\)。

代碼

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 210, M = 50;

struct node
{
	int x, y, p, f;
	bool operator < (const node &a) const
	{
		return f > a.f;
	}
};

int n, m, sx, sy, sp;
int a[N][N];
int dis[N][N][M];
bool vis[N][N][M];
int dx[10] = {0, 1, 0, -1, 0};
int dy[10] = {0, 0, 1, 0, -1};

priority_queue<node> q;

int h(int x, int y)
{
	return n - x + m - y;
}

void astar()
{
	dis[sx][sy][sp] = a[sx][sy];
	q.push((node) {sx, sy, sp, dis[sx][sy][sp] + h(sx, sy)});
	while (!q.empty())
	{
		int x = q.top().x, y = q.top().y, p = q.top().p;
		q.pop();
		if (vis[x][y][p])
		{
			continue;
		}
		vis[x][y][p] = 1;
		if (x == n && y == m)
		{
			return;
		}
		for (int i = 1; i <= 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i], np = p, w = a[nx][ny];
			if (a[nx][ny] == -1)
			{
				if (!np)
				{
					continue;
				}
				np--;
				w = 1;
			}
			if (1 <= nx && nx <= n && 1 <= ny && ny <= m && !vis[nx][ny][np] && dis[nx][ny][np] > dis[x][y][p] + w)
			{
				dis[nx][ny][np] = dis[x][y][p] + w;
				q.push((node) {nx, ny, np, dis[nx][ny][np] + h(nx, ny)});
			}
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> sx >> sy >> sp;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		s = " " + s;
		for (int j = 1; j <= m; j++)
		{
			if (s[j] == '#')
			{
				a[i][j] = -1;
			}
			else
			{
				a[i][j] = s[j] - '0';
			}
			fill(dis[i][j], dis[i][j] + sp + 1, INT_MAX);
		}
	}
	astar();
	int ans = *min_element(dis[n][m], dis[n][m] + sp + 1);
	if (ans == INT_MAX)
	{
		cout << "mission impossible" << endl;
	}
	else
	{
		cout << ans << endl;
	}
	return 0;
}