算法提高课-搜索-A*(A star)算法-AcWing 179. 八数码：A星算法求解

题目分析

来源：acwing

分析：

A*算法是什么呢？

A算法是一种bfs的变式，需要用到一个“估价函数”，用来计算任意状态到目标状态所需代价的估计值。然后在搜索中，维护一个堆，不断从堆中取出“当前代价 + 未来代价”最小 的状态进行扩展。
所以，A = 优先队列 bfs+ 估价函数。

A*算法需要估价函数需要满足一个基本准则：

设当前状态state到目标状态所需代价的估计值为f(state)
设在未来的搜索中，实际求出的从当前状态state到目标状态的最小代价为g(state)

对任意的state，应该有$f(state)\le g(state)$

用文字表述：A*算法的准则：估价函数的估值要小于等于未来实际代价。

很自然地想到dijkstra算法，其实，在形式上，可以把dijkstra算法看作是A*算法的特殊情况：估价函数始终为0.

本题解析：

八数码问题有一个充要条件可以判断是否有解：把所有数字按行读出，组成一个序列，如果其中逆序对的数量是偶数个，则八数码问题一定有解；如果逆序对的数量是奇数个，则一定无解。

ac代码

#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int, string> PIS; int f(string state){int res = 0;for(int i = 0; i < state.size(); i ++){if(state[i] != 'x'){int t = state[i] - '1';res += abs( i/ 3 - t /3) + abs(i % 3 - t% 3);}}return res; }string bfs(string start){string end = "12345678x";char op[] = "urdl";int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};unordered_map<string, int > dist; // 距离unordered_map<string, pair<char,string>> pre; // 前驱状态 priority_queue<PIS, vector<PIS>, greater<PIS>> heap;//里面存的是 估价函数，状态dist[start] = 0;heap.push({f(start), start});while( heap.size()){auto t = heap.top();heap.pop();string state = t.y;if(state == end) break;// 找到空格‘x’int x, y;for(int i = 0; i < 9; i ++){if(state[i] == 'x'){x = i /3, y = i % 3;break;}}string source = state;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;state = source;swap(state[3 *x + y], state[ 3 * a + b]);if(! dist.count(state) || dist[state] > dist[source] + 1){dist[state] = dist[source] + 1;pre[state] = {op[i], source};heap.push({dist[state] + f(state),state});}}}string res;while(end != start){res += pre[end].x;end = pre[end].y;}reverse(res.begin(), res.end());return res; }int main(){string start, seq;char c;while(cin >> c){start += c;if( c != 'x') seq += c;}int cnt = 0;// 求逆序对的数量for(int i = 0; i < 8; i ++)for(int j = i; j < 8; j ++)if(seq[i] > seq[j]) cnt ++;if(cnt & 1) puts("unsolvable");else cout << bfs(start) << endl; }

题目来源

https://www.acwing.com/problem/content/181/

总结

以上是生活随笔为你收集整理的算法提高课-搜索-A*(A star)算法-AcWing 179. 八数码：A星算法求解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。