欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

启发式搜索A* 算法

最编程 2024-03-22 09:39:01
...
class Solution { public: int slidingPuzzle(vector<vector<int>>& board) { string start = zip(board); string target = zip({{1, 2, 3}, {4, 5, 0}}); //q.push(start); q.push({-evaluate(start), start}); depth[start] = 0; while (!q.empty()) { string s = q.top().second; q.pop(); int pos = findZeroIndex(s); if (pos >= 3) expand(s, pos, pos - 3); if (pos <= 2) expand(s, pos, pos + 3); if (pos % 3 != 0) expand(s, pos, pos - 1); if (pos % 3 != 2) expand(s, pos, pos + 1); if (depth.find(target) != depth.end()) return depth[target]; } return -1; } private: int evaluate(string &s) { int now[6]; for (int i = 0; i < 6; i++) { if (s[i] != '0') now[s[i] - '0'] = i; } int target[6] = {0 ,0 ,1, 2, 3, 4}; int ans = 0; for (int digit = 1; digit <= 5; digit++) { int nowx = now[digit] / 3; int nowy = now[digit] % 3; int targetx = target[digit] / 3; int targety = target[digit] % 3; ans += abs(nowx - targetx) + abs(nowy - targety); } return ans; } void expand(string& s, int pos, int other) { string ns = s; swap(ns[pos] , ns[other]); if (depth.find(ns) != depth.end()) return; depth[ns] = depth[s] + 1; q.push({ - depth[ns] - evaluate(ns), ns}); //q.push(ns); } string zip(const vector<vector<int>>& board) { string res; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { res += '0' + board[i][j]; } } return res; } int findZeroIndex(string& s) { for (int i = 0; i < 6; i++) if (s[i] == '0') return i; return -1; } //queue<string> q; priority_queue<pair<int, string>> q; unordered_map<string, int> depth; };

上一篇： 非梯度类启发式搜索算法内尔德-米德

下一篇： 横批：网络行为管理系统启发式算法应用研究、实用性分析及实施难点探讨

推荐阅读