八数码难题的搜索求解演示

1、人工智能实验报告学院：信息科学与工程学院班 级： 自动化 0901 班学号：姓名：孙锦岗指导老师：刘丽珏期： 2011 年 12 月 20 日实验名称、目的及内容实验名称：八数码难题的搜索求解演示实验目的：加深对图搜索策略概念的理解，掌握搜索算法。实验内容要求：以八数码难题为例演示广度优先或深度优先搜索、A 算法（本实验使用的是广度优先搜索）的搜索过程，争取做到直观、清晰地演示 算法。八数码难题：在 3X3方格棋盘上，分别放置了标有数字 1,2,3,4,5,6,7,8的八张牌，初始状态S0,目标状态如图所示，可以使用的操作有: 空格上移，空格左移，空格右移，空格下移。试编一程序实现这一搜索过程

2、。二、实验原理及基本技术路线图实验原理：八数码问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个数组表示，例如8,7, 1,5, 2, 6, 3, 4, 0 其中0代表空格。它在奇序列位置上。在这个数组中我们首先计算它能够重排列出来的结果，公式就是：E (F (X) ) =Y,其中F (X),就是一个数他前面比这个数小的 数的个数，Y为奇数和偶数个有一种解法。那么上面的数组我们就可 以解出它的结果。数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实 现对节点的保存和扩展。首先建立

3、一个队列，将初始结点入队，并设 置队列头和尾指，然后取出队列(头指针所指)的结点进行扩展，从 它扩展出子结点，并将这些结点按扩展的顺序加入队列， 然后判断扩 展出的新结点与队列中的结点是否重复， 如果重复则，否则记录其父 结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是 否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结 点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再 返回第二步，知道扩展出的结点是目标结点结束，并显示路径。算法分析：九宫问题的求解方法就是交换空格(0)位置，直至到达目标 位置为止。如图所示：2 831647一58715234468715 I

4、2I 634因此可知：九宫的所以排列有9!种，也就是种排法，数据量是 非常大的，我使用广度搜索，需要记住每一个结点的排列形式，要是 用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。使 用DWORD形式保存，压缩形式是每个数字用3位表示，这样就是 3X9 = 27个字节，由于8的二进制表示形式1 0 0 0,不能用3 位表示，我使用了一个小技巧就是将8表示位0 0 0,然后用多出来 的5个字表示8所在的位置，就可以用DWORD表示了。用移位和 或操作将数据逐个移入，比乘法速度要快点。定义了几个结果来存储 遍历到了结果和搜索完成后保存最优路径。算法描述：过程 BREADTH-SEARCH

5、(1) G:=G0(G0=s),OPEN:=(s),CLOSE:=( );(2) LOOP:IF OPEN=( ) THEN EXIT(FAIL);(3) N:=FIRST(OPEN);(4) IF GOAL(n) THEN EXIT(SUCCESS);(5) RENMOVE(n,OPEN),ADD(n,CLOSED);(6) EXPAND(n)>mi,G:=ADD(mi,G); 结点放在OPENft的后面，使深度浅的结点可优先扩展。广度优先搜索的源代码如下：void Bfs()queue<Map> Queue;Queue.push(org);HashTable org.my

6、index = -1;while( NOT Queue.empty() )Map node = Queue.front();Queue.pop();for(int k =0 ; k < 4; k + )Map tmp = node;tmp.position = node.position + derectionk;if(tmp.position< 0 | tmp.position > 8 | ( k > 1 &&tmp.position / 3 != node.position /3 ) )continue;tmp.myindex = HashValue

7、( node , k );if(0 != HashTabletmp.myindex ) continue;tmp.detail node.position = tmp.detail tmp.position ;/ 移动空格tmp.detail tmp.position = 0 ;HashTabletmp.myindex = node.myindex; / 状态记录到hashtable 中if( node.myindex = EndIndex ) return ;Queue.push( tmp );return ;实验流程图:开始#define DOWN 1三、所用仪器、材料（设备名称、型号、规

8、格等或使用软件）硬件: 个人计算机软件: Microsoft Visual C+ 6.0四、实验方法、步骤（或：程序代码或操作过程）1. 实验步骤（ 1）运行 Microsoft Visual C+ 6.0 软件，新建工作空间，得文档。（ 2）输入源程序代码，进行编译，调试运行。（ 3） 运行结果，按提示要求输入1 8 这八个数，进行程序测验。2. 实验源程序#include <stdio.h>#include <stdlib.h>#include <windows.h>#include <queue>#include <stack>

9、using namespace std;#define HashTableSize#define NOT !#define UP 0#define LEFT 2 #define RIGHT 3#define Bit chartypedef struct mapsBit detail9;int myindex;/ 记录自己节点在hash 表中的位置Bit position;/ 记录 空格（0）在序列中的位置Map,*PMap;Map org;/ 初始状态int EndIndex;/ 目标 , 上移 ， 下移 ， 左移 ， 右移int const derection4 = -3 , 3 , -1

10、, 1 ;/ 可移动的四个方向int const Factorial9 = 40320 , 5040 , 720 , 120 , 24 , 6 ,2 , 1 , 1 ;int HashTableHashTableSize=0;/hash 表 , 其中记录的是上一个父节点对应的位置/* 八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的 ） */void input（）int i,j;int sum , count ,index ;for(i = 0 ; i < 9 ; i + )scanf("%1d", &org.detail i );org.det

11、ail i | (org.position = i) ;/ 计算逆序&& org.detail j <for(i = 0 ; i < 9 ; i + )if( 0 = org.detail i )continue;for(j = 0 ; j < i; j + )sum += ( 0 != org.detail org.detail i );for( i = 0 , index = 0 ; i < 9 ; i + ) / 计算初始状态的hash 值for(j = 0 , count = 0 ; j < i ; j +)count += org.det

12、ail j > org.detail i ;index += Factorial org.detail i * count;org.myindex = index + 1 ;EndIndex = sum%2 ? :;/ 目标状态的hash 值return;/*hash 值的计算*Parent: 父状态的hash 值 *direct: 移动的方向*/inline int HashValue(Map& Parent , int& direct )int i = Parent.position ;int newindex = Parent.myindex ;Bit *p = P

13、arent.detail;switch(direct)case UP :newindex -= 3*40320 ;newindex += ( p i - 2 > p i - 3 ) ?( Factorial p i - 3 ) : ( - Factorial p i - 2 );newindex += ( p i- 1 > p i - 3 ) ?( Factorial p i - 3 ) : ( - Factorial p i - 1 );break;case DOWN :newindex += 3*40320 ;newindex -= ( p i + 2 > p i + 3

14、 ) ?( Factorial p i + 3 ) : ( - Factorial p i + 2 );newindex -= ( p i + 1 > p i + 3 ) ?( Factorial p i + 3 ) : ( - Factorial p i + 1 );break;case LEFT : return newindex - 40320; break;case RIGHT : return newindex + 40320; break;return newindex;/* * * 广度优先搜索*/void Bfs()queue<Map> Queue;Queue

15、.push(org);HashTable org.myindex = -1;while( NOT Queue.empty() )Map node = Queue.front();Queue.pop();for(int k =0 ; k < 4; k + )Map tmp = node;tmp.position = node.position + derectionk;if(tmp.position < 0 | tmp.position > 8 | ( k >1 && tmp.position / 3 != node.position /3 ) )cont

16、inue;tmp.myindex = HashValue( node , k );if(0 != HashTabletmp.myindex ) continue;tmp.detail node.position = tmp.detail tmp.position ;/ 移动空格tmp.detail tmp.position = 0 ;HashTabletmp.myindex = node.myindex;/ 状态记录到hashtable 中if( node.myindex = EndIndex ) return ;Queue.push( tmp );return ;'*通过 hash

17、表中记录的进行查找路径*/void FindPath()int nowindex;int count =0 ;int nixu9, result9;int i, j , k ;stack<int> Stack;Stack.push(EndIndex);nowindex = EndIndex;while( -1 != HashTable nowindex )Stack.push(HashTable nowindex );nowindex = HashTable nowindex ;printf(" 共需： %d 步 n",Stack.size()-1);getch

18、ar();while( NOT Stack.empty()nowindex = Stack.top() - 1 ;Stack.pop();for( i = 0 ; i < 9; i + )/ 计算出逆序nixui = nowindex / Factorial i ;nowindex %= Factorial i ;memset( result , -1 , 9 *sizeof(int);for( i =0 ; i < 9 ; i + )/ 根据逆序计算排列for( j = 0 , k = nixui ; j < 9 ; j + )if(resultj = -1 ) k -;if( k < 0 ) break;resultj = i ;for( i =0 ; i < 9 ; i + )printf("%3d",resulti);if( 2 = i % 3 ) printf("n");if(0 != Stack.size() )printf("nJ 第姓n",+count);getchar();printf("nThe E