題目分析

來源：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星算法求解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。