Poj 1077 Eight 八数码问题 (搜索)

爱被打了一巴掌 2023-05-22 06:46 4阅读 0赞

搜索会用的方法太少了，于是最近被搜索虐爆了。。。

最近看了A\*，IDA\*和双向BFS，只有双向BFS基本掌握，另外连个都不明觉厉……现在我对A\*的理解还停留在求次短路时的写法……

认识启发式搜索A\*和迭代加深的A\*算法：IDA\*算法可以看这个：

[\[搜索\]A\*和IDA\*\_c++吧\_百度贴吧][A_IDA_c]

这个题学到了一个处理排列的小技巧：

[康托展开\_百度百科][Link 1]

双向BFS解法：http://blog.csdn.net/dizem/article/details/4436663

代码基本上参考这里写的：

[八数码 poj 1077 广搜 A\* IDA\* - yongmou- - 博客园][poj 1077 _ A_ IDA_ - yongmou- -]

纯BFS代码,Poj单Case能过，其他OJ多Case肯定超时：

#include <cstdio>
    #include <queue>
    using namespace std;
    
    const int N = 362880;
    
    bool visit[N];
    int pre[N];
    char move[N];   //需要记录的数值不多,定义成char型比int省空间
    int step[4][2] = {
       {-1,0}, {1,0}, {0,-1}, {0,1}};//u, d, l, r
    
    struct Node
    {
        char graph[9];
        char space;//空格所在位置
    };
    
    /* 把1..n的排列映射为数字 0..(n!-1) */
    int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };//...
    
    int order (const char *s)
    {//康托展开
    	int num=0;
    	for (int i=0;i<8;i++)
    	{
    		int temp=0;
    		for (int j=i+1;j<9;j++)
    			if (s[j]<s[i])
    				temp++;
    		num+=fac[s[i]-1]*temp;
    	}
    	return num;
    }
    
    /* 整数映射成排列 */
    void get_node (int num, Node &tmp) 
    {//康托展开逆变换
    	int i,a[9]; //求逆序数
    	for (i=2;i<=9;i++)
    	{
    		a[i-1]=num%i;
    		num = num / i;
    		tmp.graph[i-1] = 0;//初始化
    	}
    	tmp.graph[0]=0;
    	for (int k=9;k>=2;k--)
    	{
    		int t=0;
    		for (i=8;i>=0;i--)
    		{
    			if (tmp.graph[i] != 0) continue;
    			if (t == a[k-1]) break;
    			t++;
    		}
    		tmp.graph[i] = k;
    	}
    	for (i=0;i<9;i++)
    		if (tmp.graph[i] == 0)
    		{
    			tmp.graph[i] = 1;
    			break;
    		}
    	tmp.space=8-a[8];
    }
    
    void BFS (const Node & start)
    {
    	memset(visit,false,sizeof(visit));
    	int u=order(start.graph);
    	pre[u] = -1;
    	visit[u] = 1;
    
    	queue<int> que;
    	que.push(u);
    
    	Node tmp,cur;
    	while (!que.empty())
    	{
    		u=que.front();
    		que.pop();
    		get_node(u,cur);
    
    		int k = cur.space;
    		int x = k / 3;
    		int y = k % 3;
    		for (int i=0;i<4;i++)
    		{
    			int a = x + step[i][0];
    			int b = y + step[i][1];
    			if (a>=0 && a<=2 && b>=0 && b<=2)
    			{
    				tmp = cur;
    				tmp.space = a*3+b;
    				swap(tmp.graph[k], tmp.graph[tmp.space]);
    				int v = order(tmp.graph);
    				if (visit[v] != 1)
    				{
    					move[v] = i;
    					visit[v]=true;
    					pre[v] = u;
    					if (v == 0) //目标结点hash值为0
    						return;
    					que.push(v);
    				}
    			}
    		}
    	}
    }
    
    void print_path ()
    {
    	int n=1,u;
    	char path[1000];
    	path[0] = move[0];
    	u = pre[0];
    	while (pre[u] != -1)
    	{
    		path[n] = move[u];
    		n++;
    		u = pre[u];
    	}
    	for (int i=n-1;i>=0;i--)
    	{
    		switch (path[i])
    		{
    		case 0: printf("u");break;
    		case 1: printf("d");break;
    		case 2: printf("l");break;
    		default:printf("r");
    		}
    	}
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	Node start;
    	char str[4];
    	for (int i=0;i<9;i++)
    	{
    		scanf("%s",str);
    		if (str[0]=='x')
    		{
    			start.graph[i]=9;
    			start.space=i;
    		}
    		else
    			start.graph[i]=str[0]-'0';
    	}
    	BFS (start);
    	if (visit[0])
    		print_path ();
    	else
    		printf("unsolvable\n");
    	return 0;
    }

双向BFS，参考了上面提到的博客：

#include <iostream>
    #include <queue>
    using namespace std;
    
    const int N = 362882;//最大状态9!
    
    int frc[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    int n1,n2;
    int hash1[N], hash2[N];//标记走过的结点，同时记录结点序号 
    int dir[][2] = {1,0,-1,0,0,-1,0,1};
    char f1[] = "dulr", f2[] = "udrl";//正搜和反搜的方向
    
    struct Node
    {
    	char graph[3][3];
    	int x, y, n;
    }s, t, top,cur;
    
    struct path
    {
    	int pre, dir;
    }path1[N/2], path2[N/2];//记录双向路径 
    
    bool Judge (int x,int y)
    {
    	return (x>=0 && x<3 && y>=0 && y<3);
    }
    
    int value (char m[][3])//计算Hash值 
    {
    	int v=0;
    	for (int i=0;i<9;i++)
    	{
    		int a = m[i/3][i%3]-'0';
    		int cnt = 0;
    		for (int j=i+1;j<9;j++)
    		{
    			int b = m[j/3][j%3]-'0';
    			if (b<a) cnt++;
    		}
    		v += cnt*frc[a-1];
    	}
    	return v;
    }
    
    bool BFS ()
    {
    	queue<Node>P, Q;
    	s.n = t.n = 0;
    	P.push(t), Q.push(s);
    	hash1[value(t.graph)] = hash2[value(s.graph)] = 1;
    	int i,v;
    	while (!P.empty() && !Q.empty())
    	{
    		if (!P.empty())
    		{
    			top = P.front();
    			P.pop();
    			for (i=0; i<4; i++)
    			{
    				cur=top;
    				cur.x=top.x+dir[i][0];
    				cur.y=top.y+dir[i][1];
    				if (Judge(cur.x,cur.y))
    				{
    					swap(cur.graph[top.x][top.y],cur.graph[cur.x][cur.y]);
    					v = value(cur.graph);
    					if (hash2[v])   //与反搜相遇
    					{
    						path1[++n1].pre = cur.n;
    						path1[n1].dir = i;
    						n2 = hash2[v]-1;
    						return true;
    					}
    					if (!hash1[v])
    					{
    						cur.n = ++n1;
    						path1[n1].pre = top.n;
    						path1[n1].dir = i;
    						hash1[v] = n1+1;
    						P.push(cur);
    					}
    				}
    			}
    		}
    		if (!Q.empty())
    		{
    			top = Q.front();
    			Q.pop();
    			for (i=0; i<4; i++)
    			{
    				cur=top;
    				cur.x=top.x+dir[i][0];
    				cur.y=top.y+dir[i][1];
    				if (Judge(cur.x,cur.y))
    				{
    					swap(cur.graph[top.x][top.y],cur.graph[cur.x][cur.y]);
    					v = value(cur.graph);
    					if(hash1[v])
    					{
    						path2[++n2].pre = cur.n;
    						path2[n2].dir = i;
    						n1 = hash1[v]-1;
    						return true;
    					}
    					if(!hash2[v])
    					{
    						cur.n = ++n2;
    						path2[n2].pre = top.n;
    						path2[n2].dir = i;
    						hash2[v] = n2+1;
    						Q.push(cur);
    					}
    				}
    			}
    		}
    	}
    	return false;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int i,j;
    	char str[4];
    	n1=n2=0;
    	for (i=0;i<3;i++) for(j=0; j<3; j++)  //初始化目标节点
    		t.graph[i][j] = i*3+j+1+'0';
    	t.x = t.y = 2;
    	for (i=0;i<3;i++) for(j=0;j<3;j++)
    	{
    		scanf("%s",str);
    		if (str[0]=='x')
    		{
    			s.x = i;s.y = j;
    			s.graph[i][j] = '9';
    		}
    		else
    			s.graph[i][j] = str[0];
    	}
    	if (value(s.graph) == value(t.graph)); 
    	else if (BFS())
    	{
    		int m=0, i, d[1000];
    		while (n2>0)
    		{
    			d[m++] = path2[n2].dir;
    			n2 = path2[n2].pre;
    		}
    		for (i=m-1;i>=0;i--)
    			printf("%c",f1[d[i]]);
    		while (n1>0)
    		{
    			printf("%c",f2[path1[n1].dir]);
    			n1 = path1[n1].pre;
    		}
    		printf("\n");
    	}
    	else
    		printf("unsolvable\n");
    	return 0;
    }

A\*

#include <cstdio>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int N = 362880;
    /* 把1..n的排列映射为数字 0..(n!-1) */
    int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    
    struct node
    {
        char graph[9];
        char space;//空格所在位置
    };
    
    int order (const char *s)
    {//康托展开
    	int num=0;
    	for (int i=0;i<8;i++)
    	{
    		int temp=0;
    		for (int j=i+1;j<9;j++)
    			if (s[j]<s[i])
    				temp++;
    		num+=fac[s[i]-1]*temp;
    	}
    	return num;
    }
    
    /* 整数映射成排列 */
    void get_node (int num, node &tmp) 
    {//康托展开逆变换
    	int i,a[9]; //求逆序数
    	for (i=2;i<=9;i++)
    	{
    		a[i-1]=num%i;
    		num = num / i;
    		tmp.graph[i-1] = 0;//初始化
    	}
    	tmp.graph[0]=0;
    	for (int k=9;k>=2;k--)
    	{
    		int t=0;
    		for (i=8;i>=0;i--)
    		{
    			if (tmp.graph[i] != 0) continue;
    			if (t == a[k-1]) break;
    			t++;
    		}
    		tmp.graph[i] = k;
    	}
    	for (i=0;i<9;i++)
    		if (tmp.graph[i] == 0)
    		{
    			tmp.graph[i] = 1;
    			break;
    		}
    	tmp.space=8-a[8];
    }
    
    //启发函数: 除去x之外到目标的网格距离和
    int goal_state[9][2] = {
       {0,0}, {0,1}, {0,2},
            {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}};
    
    int h (const char *board)
    {
    	int k,hv = 0;
    	for (int i=0;i<3;i++) for (int j=0;j<3;j++)
    	{
    		k = i*3+j;
    		if (board[k] != 9)
    			hv += abs(i - goal_state[board[k]-1][0]) +
    			abs(j - goal_state[board[k] -1][1]);
    	}
    	return hv;
    }
    
    int f[N], d[N];//估计函数和深度
    
    
    //优先队列的比较对象
    struct cmp
    {
    	bool operator () (int u, int v)
    	{
    		return f[u] > f[v];
    	}
    };
    char color[N];//0, 未访问；1, 在队列中，2, closed
    int pre[N];
    char move[N];
    int step[4][2] = {
       {-1, 0},{1, 0}, {0, -1}, {0, 1}};//u, d, l, r
    
    void A_star (const node & start)
    {
    	int x, y, k, a, b;
    	int u, v;
    	priority_queue<int, vector<int>, cmp> open;
    	memset(color,0, sizeof(color));
    	
    	u = order(start.graph);
    	pre[u] = -1;
    	d[u] = 0;
    	f[u] = h(start.graph);
    	open.push(u);
    	color[u] = 1;
    	
    	node tmp, cur;
    	while (!open.empty())
    	{
    		u = open.top();
    		if (u == 0) return;
    		open.pop();
    		
    		get_node(u, cur);
    		k = cur.space;
    		x = k / 3;
    		y = k % 3;
    		for (int i=0;i<4;i++)
    		{
    			a = x + step[i][0];
    			b = y + step[i][1];
    			if (a>=0 && a<=2 && b>=0 && b<=2)
    			{
    				tmp = cur;
    				tmp.space = a*3 + b;
    				swap(tmp.graph[k], tmp.graph[tmp.space]);
    				v = order(tmp.graph);
    				if (color[v] == 1 && (d[u] + 1) < d[v])
    				{//v in open
    					move[v] = i;
    					f[v] = f[v] - d[v] + d[u] + 1;//h[v]已经求过
    					d[v] = d[u] + 1;
    					pre[v] = u;
    					//直接插入新值, 有冗余，但不会错
    					open.push(v);
    				}
    				else if (color[v] == 2 && (d[u]+1)<d[v])
    				{//v in closed
    					move[v] = i;
    					f[v] = f[v] - d[v] + d[u] + 1;//h[v]已经求过
    					d[v] = d[u] + 1;
    					pre[v] = u;
    					open.push(v);
    					color[v] = 1;
    				}
    				else if (color[v] == 0)
    				{
    					move[v] = i;
    					d[v] = d[u] + 1;
    					f[v] = d[v] + h(tmp.graph);
    					pre[v] = u;
    					open.push(v);
    					color[v] = 1;
    				}
    			}
    		}
    		color[u] = 2; //
    	}
    }
    
    void print_path ()
    {
    	int n=1,u;
    	char path[1000];
    	path[0] = move[0];
    	u = pre[0];
    	while (pre[u] != -1)
    	{
    		path[n] = move[u];
    		n++;
    		u = pre[u];
    	}
    	for (int i=n-1;i>=0;i--)
    	{
    		switch (path[i])
    		{
    		case 0: printf("u");break;
    		case 1: printf("d");break;
    		case 2: printf("l");break;
    		default:printf("r");
    		}
    	}
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	node start;
    	char str[4];
    	for (int i=0;i<9;i++)
    	{
    		scanf("%s",str);
    		if (str[0]=='x')
    		{
    			start.graph[i]=9;
    			start.space=i;
    		}
    		else
    			start.graph[i]=str[0]-'0';
    	}
    	A_star (start);
    	if (color[0] != 0)
    		print_path ();
    	else
    		printf("unsolvable\n");
    	return 0;
    }

IDA\*：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    
    char board[3][3];
    
    //启发函数: 除去x之外到目标的网格距离和
    int goal_state[9][2] = {
       {0,0}, {0,1}, {0,2},
            {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}};
    
    int h (char board[][3])
    {
    	int cost = 0;
    	for (int i=0;i<3;i++) for (int j=0;j<3;j++)
    		if (board[i][j] != 3*3)
    			cost += abs(i - goal_state[board[i][j]-1][0]) +
    			        abs(j - goal_state[board[i][j]-1][1]);
    		return cost;
    }
    
    int step[4][2] = {
       {-1, 0}, {0, -1}, {0, 1}, {1, 0}};//u, l, r, d
    char op[4] = {'u', 'l', 'r', 'd'};
    
    char solution[1000];
    int bound;    //上界
    bool ans;    //是否找到答案
    
    int DFS (int x, int y, int dv, char pre_move)
    {// 返回next_bound
    	int hv = h(board);
    	if (hv + dv > bound)
    		return dv + hv;
    	if (hv == 0)
    	{
            ans = true;
            return dv;
        }
    	
    	int next_bound = 1e9;
    	for (int i=0;i<4;i++)
    	{
    		if (i + pre_move == 3)//与上一步相反的移动
    			continue;
    		int nx = x + step[i][0];
    		int ny = y + step[i][1];
    		if (nx>=0 && nx<3 && ny>=0 && ny<3)
    		{
    			solution[dv] = i;
    			swap(board[x][y], board[nx][ny]);
    			
    			int new_bound = DFS(nx, ny, dv+1, i);
    			if (ans)
    				return new_bound;
    			next_bound = min(next_bound, new_bound);
    			swap(board[x][y], board[nx][ny]);
    		}
    	}
    	return next_bound;
    }
    
    void IDA_star (int sx,int sy)
    {
    	ans = false;
    	bound = h(board);//初始代价
    	while (ans==false && bound <= 100)//上限
    		bound = DFS(sx, sy, 0, -10);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int sx,sy,i;
    	char str[4];
    	for (i=0;i<3;i++)
            for (int j=0;j<3;j++)
    		{
    			scanf("%s",str);
    			if (str[0]=='x')
    			{
    				board[i][j]=3*3;
                    sx=i,sy=j;
    			}
    			else
    				board[i][j]=str[0]-'0';
    		}
    	IDA_star(sx, sy);
    	if (ans)
    		for (i=0;i<bound;i++)
    			cout<<op[solution[i]];
    	else
    		printf("unsolvable\n");
    	return 0;
    }

[A_IDA_c]: http://tieba.baidu.com/p/1000086851
[Link 1]: http://baike.baidu.com/view/437641.htm
[poj 1077 _ A_ IDA_ - yongmou- -]: http://www.cnblogs.com/liyongmou/archive/2010/07/19/1780861.html