首页 > 代码库 > poj 1077 Eight（A*）
poj 1077 Eight（A*）
经典的八数码问题，用来练习各种搜索=_=。这题我用的A*做的，A*的主要思想就是在广搜的时候加了一个估价函数，用来评估此状态距离最终状态的大概距离。这样就可以省下很多状态不用搜索。对于每个状态设置一个函数 h(x)，这就是估价函数了（可能名词不太对请见谅），再设置一个函数 g(x)， 这存的是初始状态到当前状态所用步数（或距离，视估价函数而定），再设函数 f(x) = g(x) + h(x)，我们对每个状态的 f(x)的值进行排序， 然后从当前 f(x) 最小的状态继续搜索，直到搜索到最终状态或者没有后继状态。
上代码：
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#define N 10#define M 500000using namespace std;struct sss{ int state[N]; int num, place;};priority_queue<sss> q;int f[M], g[M] = {0}, fa[M] = {0}, move[M] = {0};sss begin, end;int step[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};int color[M] = {0};bool operator < (sss a, sss b) { return f[a.num] > f[b.num]; }bool operator == (sss a, sss b) { return a.num == b.num; }int h(sss a) // h(v) { int z = 0; for (int i = 1; i <= 3; ++i) for (int j = 1; j <= 3; ++j) { int x = (i-1)*3+j; z += abs(i-(a.state[x]-1)/3) + abs(j-(a.state[x]-(a.state[x]-1)/3*3)); } return z;}int jiecheng[N] = {0,1,2,6,24,120,720,5040,40320,362880};int make_num(sss a) // 康拓展开 { int ans = 0; bool xiao[N] = {0}; for (int i = 1; i <= 9; ++i) { int count = 0; xiao[a.state[i]] = 1; for (int j = 1; j < a.state[i]; ++j) if (!xiao[j]) count++; ans += count * jiecheng[N-i-1]; } return ans;}bool in(sss now, int mo) // 移动可行 { int x = (now.place-1)/3+1, y = now.place-(x-1)*3; x += step[mo-1][0]; y += step[mo-1][1]; if (x < 1 || x > 3 || y < 1 || y > 3) return false; else return true;}void A_star() // A* { q.push(begin); f[begin.num] = h(begin); while (!q.empty()) { sss u = q.top(); q.pop(); if (u == end) return; for (int i = -3; i <= 3; i+=2) { if (!in(u,(i+5)/2)) continue; sss v; v = u; swap(v.state[u.place+i], v.state[u.place]); v.place = u.place + i; v.num = make_num(v); if (color[v.num] == 1) { if (g[u.num] + 1 < g[v.num]) { f[v.num] = f[v.num] - g[v.num] + g[u.num] + 1; g[v.num] = g[u.num] + 1; move[v.num] = i; q.push(v); fa[v.num] = u.num; } } else if (color[v.num] == 2) { if (g[u.num] + 1 < g[v.num]) { f[v.num] = f[v.num] - g[v.num] + g[u.num] + 1; g[v.num] = g[u.num] + 1; fa[v.num] = u.num; q.push(v); color[v.num] = 1; move[v.num] = i; } } else { g[v.num] = g[u.num] + 1; f[v.num] = h(v) + g[v.num]; color[v.num] = 1; fa[v.num] = u.num; q.push(v); move[v.num] = i; } } color[u.num] = 2; }}char change(int x){ if (x == -1) return ‘l‘; else if (x == -3) return ‘u‘; else if (x == 1) return ‘r‘; else return ‘d‘;}void print() // 输出 { char s[M], snum = 0; int k = fa[end.num]; s[++snum] = change(move[end.num]); while (k != begin.num) { s[++snum] = change(move[k]); k = fa[k]; } for (int i = snum; i > 0; --i) printf("%c", s[i]); printf("\n");}int main(){ char s[2]; for (int i = 1; i <= 9; ++i) { scanf("%s", s); if (s[0] != ‘x‘) begin.state[i] = s[0] - ‘0‘; else { begin.state[i] = 9; begin.place = i; } end.state[i] = i; } begin.num = make_num(begin); end.num = make_num(end); A_star(); print();}
poj 1077 Eight（A*）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。