使用AStar算法解决八数码问题

八数码问题是一个经典的搜索问题，本文将介绍如何使用启发式搜索—— 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算法解决八数码问题的全部内容，希望文章能够帮你解决所遇到的问题。

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