A-star
在先前提到的优先队列BFS方法中，是每轮从堆中取出的 “当前代价最小” 的状态进行扩展，这样每个状态第一次从堆中取出时，就得到了从初始状态到该状态的最小代价
如果目标状态是给定的，那么这个方法存在缺陷：一个状态可能到初状的代价很小，但到目标态的代价很大；一个状态可能到初态的代价很大，但到目标态的代价很小
而对于优先队列BFS来说，他会选择前者进行更新，从而导致求出最优解的搜索量增大
为提高效率，考虑引入能够对未来可能产生的代价进行预估的方法
我们可以设计一个 “估价函数”，以任意状态为输入，计算出从该状态到目标状态所需代价的估值
在搜索中，仍需要建立一个堆，不断从堆中取出 “当前代价 未来估价” 最小 的状态扩展
设计估价函数的基本准则：
- 设当前状态
state到目标状态所需代价的估值为f(state) - 设在未来的搜索中，实际求出的从当前状态
state到目标状态的最小代价为g(state) - 对于任意的
state，始终有f(state) <= g(state)（估值永远不能大于未来的实际代价）
在保证估值不大于未来实际代价后，那么即使估价不太精确，导致非最优解搜索路径上的状态 s 先扩展到了目标状态，但随着 “当前代价” 的不断累加，在目标状态被取出之前的某一时刻：
- 根据
s并非最优，s更新的目标状态的 “当前代价” 就会大于从初态到目标态的最小代价 - 对于最优解搜索路径上的状态
t，因为f(t) <= g(t)，所有t的 “当前代价” 加上估值必定小于等于t的 “当前代价” 加上未来实际代价，而后者的含义就是初态到目标态的最小代价
结合上述两点，可知 “t 的当前代价加上 f(t)” 小于 s 更新的目标状态的当前代价。因此，t 就会被从堆中取出进行扩展，最终更新到目标状态上，产生最优解。（并且该事件发生在目标状态被取出优先队列之前）
这种 带有估价函数的优先队列BFS就成为A-star算法
只要保证对于任意状态state，都有f(state) <= g(state)，A-star算法就一定能 在目标状态第一次从堆中被取出时得到最优解，并且 在搜索过程中每个状态只需要被扩展一次 （之后再被取出时就可以直接忽略）
估价f(state)越接近g(state)，效率就越高；若估价为 0，则退化为优先队列BFS
习题
第 K 短路
题目描述
给定一张
个点（编号
），
条边的有向图，求从起点
到终点
的第
短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数
和
。
接下来
行，每行包含三个整数
，表示点
与点
之间存在有向边，且边长为
。
最后一行包含三个整数
，分别表示起点
，终点
和第
短路。
输出格式
输出占一行，包含一个整数，表示第
短路的长度，如果第
短路不存在，则输出 −1。
数据范围
输入样例：
代码语言：javascript复制2 2
1 2 5
2 1 4
1 2 2
输出样例：
代码语言：javascript复制14
解答
易知，当点
第
次从优先队列队头取出时，求得的就是从起点到点
的第
短路代价
直接用优先队列做的时间复杂度为
考虑设计估价函数 f(x) 为 x 到点 T 的最短路距离
这样在第 K 短路中，点x 到点T的估计距离f(x)小于实际距离，估价函数设计成立
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 20010;
int S, T, K, n, m;
int hp[N], hn[N], e[M], w[M], ne[M], idx;
int cnt[N], dist[N];
bool st[N];
void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ;
}
void dijkstra()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> heap;
dist[T] = 0;
heap.push({0, T});
while (heap.size())
{
PII t = heap.top(); heap.pop();
if (st[t.y]) continue;
st[t.y] = true;
for (int i = hn[t.y]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t.y] w[i])
{
dist[j] = dist[t.y] w[i];
heap.push({dist[j], j});
}
}
}
}
int f(int id)
{
return dist[id];
}
int astar()
{
memset(cnt, 0, sizeof cnt);
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
heap.push({f(S), {0, S}});
while (heap.size())
{
PIII t = heap.top(); heap.pop();
int ver = t.y.y, d = t.y.x;
cnt[ver] ;
if (cnt[T] == K) return d;
for (int i = hp[ver]; ~i; i = ne[i])
{
int j = e[i];
if (cnt[j] < K)
heap.push({d w[i] f(j), {d w[i], j}});
}
}
return -1;
}
int main()
{
cin >> n >> m;
memset(hp, -1, sizeof hp);
memset(hn, -1, sizeof hn);
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(hp, a, b, c);
add(hn, b, a, c);
}
cin >> S >> T >> K;
if (S == T) K ;
dijkstra();
cout << astar() << endl;
return 0;
}
八数码
题目描述
在一个
的网格中，
这
个数字和一个 X 恰好不重不漏地分布在这
的网格中。
例如：
代码语言：javascript复制1 2 3
X 4 6
7 5 8
在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
代码语言：javascript复制1 2 3
4 5 6
7 8 X
例如，示例中图形就可以通过让 X 先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
代码语言：javascript复制1 2 3 1 2 3 1 2 3 1 2 3
X 4 6 4 X 6 4 5 6 4 5 6
7 5 8 7 5 8 7 X 8 7 8 X
把 X 与上下左右方向数字交换的行动记录为 u、d、l、r
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。
输入格式
输入占一行，将
的初始网格描绘出来。
例如，如果初始网格如下所示：
代码语言：javascript复制1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个字符串，表示得到正确排列的完整行动记录
如果答案不唯一，输出任意一种合法方案即可
如果不存在解决方案，则输出 unsolvable
输入样例：
代码语言：javascript复制2 3 4 1 5 x 7 6 8
输出样例
代码语言：javascript复制ullddrurdllurdruldr
解答
估价函数设置为所有数字在 state 中的位置与目标位置 end 中的位置的曼哈顿距离之和：
#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;
typedef pair<int, string> PIS;
int f(string state)
{
int res = 0;
for (int i = 0; i < 9; i)
{
if (state[i] != 'x')
{
int t = state[i] - '1';
res = abs(t / 3 - i / 3) abs(t % 3 - i % 3);
}
}
return res;
}
string astar(string start, string end)
{
char op[5] = {"udlr"};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> prev;
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
heap.push({f(start), start});
while (!heap.empty())
{
PIS t = heap.top();
heap.pop();
string state = t.second;
if (state == end) break;
int x, y;
for (int i = 0; i < 9; i)
{
if (state[i] == 'x')
{
x = i / 3, y = i % 3;
break;
}
}
for (int i = 0; i < 4; i)
{
int a = x dx[i], b = y dy[i];
if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
string temp = state;
swap(temp[a * 3 b], temp[x * 3 y]);
int d = dist[state] 1;
if (!dist.count(temp) || dist[temp] > d)
{
dist[temp] = d;
prev[temp] = {op[i], state};
heap.push({dist[temp] f(temp), temp});
}
}
}
string path;
while (start != end)
{
path = prev[end].first;
end = prev[end].second;
}
reverse(path.begin(), path.end());
return path;
}
int main()
{
string start, x, seq;
while (cin >> x)
{
start = x;
if (x != "x") seq = x;
}
string end = "12345678x";
int t = 0;
for (int i = 0; i < 8; i)
for (int j = i 1; j < 8; j)
if (seq[i] < seq[j])
t;
if (t & 1) puts("unsolvable");
else cout << astar(start, end) << endl;
return 0;
}
