八數碼問題是一個經典的搜索問題，本文將介紹如何使用啟發式搜索—— AStar 算法來求解八數碼問題。

問題描述

八數碼問題的A星搜索算法實現

要求：設計估價函數，并采用c或python編程實現，以八數碼為例演示A星算法的搜索過程，爭取做到直觀、清晰地演示算法，代碼要適當加注釋。

八數碼難題：在3×3方格棋盤上，分別放置了標有數字1,2,3,4,5,6,7,8的八張牌，初始狀態S0可自己隨機設定，使用的操作有：空格上移，空格左移，空格右移，空格下移。試采用A*算法編一程序實現這一搜索過程。

算法描述

預估值的設計

A* 算法的花費為 f(n) = g(n) + h(n)，其中 g(n) 為搜索深度，定義為狀態單元 state 的成員變量，在每次生成子節點時將其加一。h(n) 為不對位的將牌數，將該部分的計算重載于 state 的小于運算符中，并將 f(n) = g(n) + h(n) 的值作為狀態單元的比較值。

數據結構設計

• 每個狀態用一個結構體表示，其中 depth 為狀態深度，str 為該狀態字符串，并重載小于運算符用于計算最優。
• open 表使用優先隊列 priority_queue，實現在 O(logn) 的時間復雜度內獲取最優值。
• close 表使用哈希集合 unordered_set，實現在 O(1) 時間復雜度內判斷某狀態是否已位于 close 表中。
• 而為了得到最優搜索路徑，還需要將每個狀態的前驅加以保存，前驅表 pre 我使用了哈希表 unordered_map，模板類型為 pair<string, string>，表示 key 的前驅為 value。

代碼

#include<iostream> #include<string> #include<vector> #include<queue> #include<unordered_map> #include<unordered_set> #include<stack> using namespace std;class Solution { private:static string targetStr;const vector<vector<int>> dirs = { {-1,0},{1,0},{0,-1},{0,1} }; // 四個移動方向struct state{string str;int depth;state(string s, int d) : str(s), depth(d) {}bool operator < (const state& s) const {int cnt1 = 0, cnt2 = 0;for (int i = 0; i < 9; ++i) {if (s.str[i] != targetStr[i])++cnt1;if (this->str[i] != targetStr[i])++cnt2;}return cnt1 + this->depth < cnt2 + s.depth; // f(n) = g(n) + h(n) }};inline void swapChr(string& child, int iniInd, int childInd) { // 交換字符，完成移動child[iniInd] = child[childInd];child[childInd] = '0';}void printPath(unordered_map<string, string>& pre, string path) { // 輸出路徑stack<string> st;while (path != "None") {st.emplace(path);path = pre[path];}int cnt = 0;while (++cnt && !st.empty()) {string str = st.top();st.pop();cout << "step" << cnt << ": " << str.substr(0, 3) << endl<< " " << str.substr(3, 3) << endl << " " <<str.substr(6, 3) << endl << string(15, '-') << endl;}} public:void eightDigitalQues(const string& ini, const string& target) {targetStr = target;priority_queue<state> open;unordered_set<string> close;unordered_map<string, string> pre;open.emplace(ini, 0);pre[ini] = "None";while (!open.empty()) {string n = open.top().str;int d = open.top().depth;open.pop();close.emplace(n);if (n == target) {break;}int iniInd = n.find('0');int x = iniInd / 3, y = iniInd % 3;for (const auto& dir : dirs) { // 嘗試選擇四個方向int nx = x + dir[0], ny = y + dir[1];if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2) { // 滿足移動后下標滿足條件int childInd = nx * 3 + ny;state childState(n, d + 1);swapChr(childState.str, iniInd, childInd);if (close.count(childState.str)) // 如該狀態已加入close表，則跳過continue;open.emplace(childState); // 加入滿足條件的子狀態pre[childState.str] = n; // 更新前驅}}}printPath(pre, target); // 輸出流程return;} }; string Solution::targetStr; int main() {Solution S;string ini, target;cin >> ini >> target;S.eightDigitalQues(ini, target);cin.get(); }

運行結果

輸入

原狀態：283164705, 目標狀態：123804765

輸出

總結

以上是生活随笔為你收集整理的使用AStar算法解决八数码问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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