您现在的位置是:首页 >技术杂谈 >【刷题】搜索——BFS:八数码【A*模板】网站首页技术杂谈
【刷题】搜索——BFS:八数码【A*模板】
A*简介
某点u的距离f(u)定义如下:
f
(
u
)
=
g
(
u
)
+
h
(
u
)
f(u) = g(u) + h(u)
f(u)=g(u)+h(u)
g(u):起点到u走的距离
h(u):u到终点估计的距离,保证
0
≤
h
(
u
)
≤
h
′
(
u
)
0 leq h(u) leq h'(u)
0≤h(u)≤h′(u)。其中h’(u)是真实距离
和普通BFS不同,A*算法用的是优先队列,根据f从小到大排序(小根堆)。拓展点时只有g(u)变小才进队,终点出队时停止。
性质1
估计距离<=真实距离,保证了终点第一次出队时,一定是最优解。
反证法:
假设终点e第一次出队时距离f(e)不是最优解f(e)',之后才会由其他点更新进队再出队得到最优解。
由于之后还要再更新,所以最优解路径上总有点会在队列里,不妨设点为u。
那么
g
(
u
)
+
h
(
u
)
≤
g
(
u
)
+
h
′
(
u
)
=
f
(
e
)
′
g(u) + h(u) leq g(u) + h'(u) = f(e)'
g(u)+h(u)≤g(u)+h′(u)=f(e)′。
因为D不是最优解,所以
f
(
e
)
>
f
(
e
)
′
f(e) > f(e)'
f(e)>f(e)′,故有
f
(
e
)
>
f
(
e
)
′
≥
g
(
u
)
+
h
(
u
)
=
f
(
u
)
f(e) > f(e)' geq g(u) + h(u) = f(u)
f(e)>f(e)′≥g(u)+h(u)=f(u)。
那么此时应该出队的是点u,而不是终点,矛盾。
性质2
除了终点以外的点出队,不一定是最优解
假设点u是最优解上的点,起点到u有两条路径a和b,真实距离分别是3和5。假设所有点的h都为0,但是路径a上某点v的h(v)为一个很大的数(但小于到终点的真实距离)。
那么在进队时,走到点v前,会先将路径b上的其他点都进队(因为h(v)很大导致f(v)很大)。并通过路径b更新u的距离5,此时u的最优距离显然是3。
基于这个性质,A*无法判断重复,只能通过终点出队停止。
PS. BFS入队时就可以判断重复,dijkstra出队的时候判断重复。
八数码
题目
题目链接
x表示空位置,每次可以将一个数字移到空位置上,问从给定状态移动到目标状态(1 2 3 4 5 6 7 8 x)至少要几步。
输入初始状态,输出x移动的路径,上下左右对应:u、d、l、r。无解输出unsolvable。
判断是否有解
可以看序列的逆序对的数量,偶数则有解,奇数则无解。
必要性:如果有解则逆序对数量是基数。
如题目所示:
2 3 4
1 5 x
7 6 8
序列为:2 3 4 1 5 x 7 6 8
当移动的数是左右移动时,例如5向右移,不会改变序列的位置,逆序对不变。
当移动的数是上下移动时,例如8向上移。序列变为:2 3 4 1 5 8 7 6 x。可以看到上下移只会导致一个数往前后往后移动两位。那么只有可能改变两个逆序对,这边是新增(8, 7),(8, 6),其他情况则是减少两个、或者加一减一。都不会改变逆序对的奇偶性。
充分性证明较复杂,不再赘述。
估计距离函数h
当前状态中各个数的位置,到其目标位置的曼哈顿距离之和。
代码
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
typedef pair<int, string> PIS;
void findX(int &x, int &y, string &ts) {
for (int i = 0; i < 9; i ++ ) {
if (ts[i] == 'x') {
x = i / 3;
y = i % 3;
}
}
}
int h(string s) {
int dis = 0;
for (int i = 0; i < 9; i ++ ) {
if (s[i] == 'x') continue;
int num = s[i] - '1';
dis += abs(num / 3 - i / 3) + abs(num % 3 - i % 3);
}
return dis;
}
string bfs(string start) {
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
unordered_map<string, int> g;
unordered_map<string, PIS> pre;
string ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
char ds[5] = "uldr";
heap.push({h(start), start});
g[start] = 0;
while(!heap.empty()) {
PIS t = heap.top();
heap.pop();
string ts = t.second;
if (ts == "12345678x") {
while(ts != start) {
PIS preTs = pre[ts];
int i = preTs.first;
ts = preTs.second;
ans = ds[i] + ans;
}
return ans;
}
int x, y;
findX(x, y, ts);
for (int i = 0; i < 4; i ++ ) {
int tx = x + dx[i];
int ty = y + dy[i];
if (tx > 2 || ty > 2 || tx < 0 || ty < 0) continue;
string newS = ts;
swap(newS[x * 3 + y], newS[tx * 3 + ty]);
if (!g.count(newS) || g[newS] > g[ts] + 1) {
g[newS] = g[ts] + 1;
heap.push({g[newS] + h(newS), newS});
pre[newS] = {i, ts};
}
}
}
return "";
}
int main() {
char ch;
string input, invS;
for (int i = 0; i < 9; i ++ ) {
cin >> ch;
input += ch;
if (ch != 'x') invS += ch;
}
int invCnt = 0;
for (int i = 0; i < 9; i ++ ) {
for (int j = i + 1; j < 9; j ++ ) {
if (invS[i] > invS[j]) {
invCnt ++ ;
}
}
}
if (invCnt & 1) {
printf("unsolvable
");
}
else {
string ans = bfs(input);
cout << ans << endl;
}
return 0;
}