下载文档原格式
a算法八数码问题例题八数码问题是一个经典的搜索问题，其中有一个3×3的格子，其中包含了一些数字（通常是1到8），以及一个空白格。
目标是使用最少的步骤将格子中的数字排列成给定的目标顺序。
每个步骤可以是以下三种操作之一：1. 上下移动（将行中的某个数字上移或下移）2. 左右移动（将列中的某个数字左移或右移）3. 旋转（以中心为中心旋转整个格子）下面是一个使用A算法解决八数码问题的例子：假设初始状态如下：```markdown4 1 2 756 3 8 05 0 3 2 4 167 86 7 5 8 3 4 2 1 0```目标状态如下：```markdown1 2 3 4 5 6 7 8 00 3 6 7 4 5 8 1 27 8 5 6 1 2 3 4 0```下面是使用A算法解决这个问题的步骤：1. 首先，我们需要构建一个优先级队列（例如最小堆），用于存储所有可能的移动。
在这个例子中，每个移动都有一个成本和优先级。
成本是从当前状态到目标状态的最短路径长度，优先级是当前状态到目标状态的H启发式估计。
H启发式估计通常是当前状态和目标状态之间的曼哈顿距离。
2. 从队列中取出优先级最高（即成本最低）的移动。
在这个例子中，初始状态的移动是"上下移动"。
3. 应用这个移动，并更新所有相关状态的成本和优先级。
在这个例子中，我们将第一行向下移动一格。
然后，我们需要重新评估所有可能的状态，并更新优先级队列。
4. 在更新优先级队列后，我们需要检查是否已经达到目标状态。
如果已经达到目标状态，则算法结束。
否则，我们重复步骤2和步骤3，直到达到目标状态。
5. 在这个例子中，我们需要进行多次上下移动、左右移动和旋转，才能将数字排列成目标顺序。
每次应用移动后，都需要重新评估所有可能的状态，并更新优先级队列。
八数码问题解释8数码问题又称9宫问题，源于一个古老的智力游戏。
说白了就是我们小时候玩的“华容道”。
意在给定的9格棋盘的8个格子内分别放一个符号，符号之间互不相同，剩下一格做为“出口”。
我们把8个符号在棋盘上的排列顺序称作8数码的状态，游戏要求给定一个初始的状态与一个终止状态，符号要经过若干次移动后由初态变成终态，这个过程中只有“出口”附近的符号可以朝“出口”的方向移动，且每次只能移动一个符号。
如下图所示，（其中我们用0表示出口，=》表示移动一次，=》*表示移动0-n次）：初态终态1 2 3 1 2 3 0 1 24 5 6 =》 4 5 6 =》* 3 4 57 8 0 7 0 8 6 7 82 解决方案通过观察我们可以发现每一次8数码的状态都可以通过移动字符变成有限的几种其他状态，比如上图中我们可以知道初态“出口”附近有8和6可以移动，那么这个初态可以经过移动得到两个新的状态。
我们人在玩这个游戏的时候，总是要做下面几个步骤：1．看看哪个符号可以移动。
2．判断一下哪个符号的移动最有利于到达终态。
3．选定一个符号并移动它。
4．判断是否到达终态，是则结束，否则就回到第一步。
而现在我们要使用机器来模拟这一过程，其步骤与人类类似，但不同的是，人在执行第二部的时候总是能预先判断未来好几步的局势，从而选出最有利的一步，而机器则不行，它要先得到一个状态才能知道这个状态下一步将会到哪些状态而无法像我们一样一次就看到后面几步的状态。
那么基本思想就是让机器穷尽由初态出发到达所有可能状态的路径，并从中找到有终态的路径作为问题的解。
2.1 A*算法就如我们上面说到的让机器找出所有的可能来得到问题的解，看起来似乎很简单，但问题在于一旦8数问题的解达到一定规模，机器所要穷尽的路径数量将变得极为庞大，无疑会消耗大量的时间和空间。
那么如何让机器像人一样在选择移动符号的时候总是能选择最有利的那一个呢？下面就要介绍启发式搜索中的一个算法A*算法来解决这个问题。
⼋数码难题（8puzzle）深度优先和深度优先算法1 搜索策略搜索策略是指在搜索过程中如何选择扩展节点的次序问题。
⼀般来说，搜索策略就是采⽤试探的⽅法。
它有两种类型：⼀类是回溯搜索，另⼀类是图搜索策略。
2 盲⽬的图搜索策略图搜索策略⼜可分为两种：⼀种称为盲⽬的图搜索策略，或称⽆信息图搜索策略；⽽另⼀种称为启发式搜索策略，⼜称为有信息的图搜索策略。
最常⽤的两种⽆信息图搜索策略是宽度优先搜索和深度优先搜索。
2.1 宽度优先搜索它是从根节点（起始节点）开始，按层进⾏搜索，也就是按层来扩展节点。
所谓按层扩展，就是前⼀层的节点扩展完毕后才进⾏下⼀层节点的扩展，直到得到⽬标节点为⽌。
这种搜索⽅式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到⽬标节点的最短路径的解，但它的缺点是往往搜索过程很长。
2.2 深度优先搜索它是从根节点开始，⾸先扩展最新产⽣的节点，即沿着搜索树的深度发展下去，⼀直到没有后继结点处时再返回，换⼀条路径⾛下去。
就是在搜索树的每⼀层始终先只扩展⼀个⼦节点，不断地向纵深前进直到不能再前进（到达叶⼦节点或受到深度限制）时，才从当前节点返回到上⼀级节点，沿另⼀⽅向⼜继续前进。
这种⽅法的搜索树是从树根开始⼀枝⼀枝逐渐形成的。
由于⼀个有解的问题树可能含有⽆穷分枝，深度优先搜索如果误⼊⽆穷分枝（即深度⽆限），则不可能找到⽬标节点。
为了避免这种情况的出现，在实施这⼀⽅法时，定出⼀个深度界限，在搜索达到这⼀深度界限⽽且尚未找到⽬标时，即返回重找，所以，深度优先搜索策略是不完备的。
另外，应⽤此策略得到的解不⼀定是最佳解（最短路径）。
3 “⼋”数码难题的宽度优先搜索与深度优先搜索3.1“⼋”数码难题的宽度优先搜索步骤如下：1、判断初始节点是否为⽬标节点，若初始节点是⽬标节点则搜索过程结束；若不是则转到第2步；2、由初始节点向第1层扩展，得到3个节点：2、3、4；得到⼀个节点即判断该节点是否为⽬标节点，若是则搜索过程结束；若2、3、4节点均不是⽬标节点则转到第3步；3、从第1层的第1个节点向第2层扩展，得到节点5；从第1层的第2个节点向第2层扩展，得到3个节点：6、7、8；从第1层的第3个节点向第2层扩展得到节点9；得到⼀个节点即判断该节点是否为⽬标节点，若是则搜索过程结束；若6、7、8、9节点均不是⽬标节点则转到第4步；4、按照上述⽅法对下⼀层的节点进⾏扩展，搜索⽬标节点；直⾄搜索到⽬标节点为⽌。
广度优先搜索实例【例题】八数码难题(Eight-puzzle)。
在3X3的棋盘上，摆有 8个棋子，在每个棋子上标有1～8中的某一数字。
棋盘中留有一个空格。
空格周围的棋子可以移到空格中。
要求解的问题是，给出一种初始布局(初始状态)和目标布局(目标状态)，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
初始状态和目标状态如下：初始状态目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5求解本题我们可以分3步进行。
问题分析：由的解于题目要找是达到目标的最少步骤，因此可以这样来设计解题的方法：初始状态为搜索的出发点，把移动一步后的布局全部找到，检查是否有达到目标的布局，如果没有，再从这些移动一步的布局出发，找出移动两步后的所有布局，再判断是否有达到目标的。
依此类推，一直到某布局为目标状态为止，输出结果。
由于是按移动步数从少到多产生新布局的，所以找到的第一个目标一定是移动步数最少的一个，也就是最优解。
建立产生式系统：(1) 综合数据库。
用3X3的二维数组来表示棋盘的布局比较直观。
我们用Ch[i,j]表示第i 行第j列格子上放的棋子数字，空格则用0来表示。
为了编程方便，还需存储下面3个数据：该布局的空格位置(Si，Sj)；初始布局到该布局的步数，即深度dep；以及该布局的上一布局，即父结点的位置(pnt)。
这样数据库每一个元素应该是由上述几个数据组成的记录。
在程序中，定义组成数据库元素的记录型为：Typenode＝recordch：array[1..3，1..3] of byte；{存放某种棋盘布局}si,sj:byte； {记录此布局中空格位置}dep,pnt：byte；end；因为新产生的结点深度(从初始布局到该结点的步数)一般要比数据库中原有的结点深度大(或相等)。
按广度优先搜索的算法，深度大(步数多)的结点后扩展，所以新产生的结点应放在数据库的后面。
而当前扩展的结点从数据库前面选取，即处理时是按结点产生的先后次序进行扩展。
课程论文摘要八数码问题也称为九宫问题。
在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。
棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。
棋子移动后，状态就会发生改变。
解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
八数码问题一般使用搜索法来解。
搜索法有广度优先搜索法、深度优先搜索法、A*算法等。
这里详细讲述A*算法。
关键词:八数码问题；空间状态；搜索法；A*算法一、实验目的理解并熟悉掌握A*算法。
二、实验内容九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数三、问题的搜索形式描述（4要素）初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。
其中，状态空间中的任一种状态都可以作为初始状态。
后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。
目标测试：比较当前状态和目标状态的格局是否一致。
路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。
四、解决方案介绍（原理）常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。
广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。
这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。
由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。
八数码——深度优先搜索八数码难题(Eight-puzzle)。
在3X3的棋盘上，摆有8个棋子，在每个棋子上标有1～8中的某一数字。
棋盘中留有一个空格。
空格周围的棋子可以移到空格中。
要求解的问题是，给出一种初始布局(初始状态)和目标布局(目标状态)，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
初始状态和目标状态如下：初始状态目标状态2 83 1 2 31 6 4 8 47 5 7 6 5看到题目，我想到用0表示空格。
然后用深度优先搜索解决问题。
程序如下：typear=array[1..3,1..3]of integer;consts:ar=((2,8,3),(1,6,4),(7,0,5));z:ar=((1,2,3),(8,0,4),(7,6,5));fx:array[1..4,1..2]of integer=((-1,0),(1,0),(0,-1),(0,1));vara:array[1..100]of recordb:ar;end;function dd(a:ar):boolean;vari,j:integer;begindd:=true;for i:=1 to 3 dofor j:=1 to 3 doif a[i,j]<>z[i,j] thenexit(false);end;function pd(h,l,i:integer):boolean;beginpd:=true;if h+fx[i,1]=4 thenexit(false);if h+fx[i,1]=0 thenexit(false);if l+fx[i,2]=0 thenexit(false);if l+fx[i,2]=4 thenexit(false);end;function fan(n:integer):integer;begincase n of1:exit(2);2:exit(1);3:exit(4);4:exit(3);end;end;procedure p(n:integer);vari,j,k:integer;beginfor i:=1 to n dobeginfor j:=1 to 3 dobeginfor k:=1 to 3 dowrite(a[i].b[j,k],' ');writeln;end;writeln;end;end;procedure dfs(dep,h,l,f:integer);varj,x,y:integer;beginif dd(a[dep].b) thenbeginp(dep);close(output);halt;end;for j:=1 to 4 doif pd(h,l,j)and(j<>f) thenbeginx:=h+fx[j,1];y:=l+fx[j,2];a[dep+1]:=a[dep];a[dep+1].b[h,l]:=a[dep].b[x,y];a[dep+1].b[x,y]:=0;if dep<6 thendfs(dep+1,x,y,fan(j));end;end;beginassign(output,'bsm.out');rewrite(output);a[1].b:=s;dfs(1,3,2,0);end.运行程序，输出：2 8 31 6 47 0 52 8 31 0 47 6 52 0 31 8 47 6 50 2 31 8 47 6 51 2 30 8 47 6 51 2 38 0 47 6 5这个程序对是对了。
人工智能实验报告学院：信息科学与工程学院班级：自动化0901班学号：姓名：孙锦岗指导老师：刘丽珏日期：2011年12月20日一、实验名称、目的及内容实验名称：八数码难题的搜索求解演示实验目的：加深对图搜索策略概念的理解，掌握搜索算法。
实验内容要求：以八数码难题为例演示广度优先或深度优先搜索、A算法（本实验使用的是广度优先搜索）的搜索过程，争取做到直观、清晰地演示算法。
八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。
试编一程序实现这一搜索过程。
二、实验原理及基本技术路线图实验原理：八数码问题中，程序产生的随机排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。
我们可以把一个随机排列的数组从左到右从上到下用一个数组表示，例如｛８，７，１，５，２，６，３，４，０｝其中０代表空格。
它在奇序列位置上。
在这个数组中我们首先计算它能够重排列出来的结果，公式就是：∑（Ｆ（Ｘ））＝Ｙ，其中Ｆ（Ｘ），就是一个数他前面比这个数小的数的个数，Ｙ为奇数和偶数个有一种解法。
那么上面的数组我们就可以解出它的结果。
数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。
首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。
否则如果队列头的结点可以扩展，直接返回第二步。
否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。
算法分析：九宫问题的求解方法就是交换空格（０）位置，直至到达目标位置为止。
如图所示：因此可知：九宫的所以排列有９！种，也就是种排法，数据量是非常大的，我使用广度搜索，需要记住每一个结点的排列形式，要是用数组记录的话会占用很多的内存，我们把数据进行适当的压缩。
使用ＤＷＯＲＤ形式保存，压缩形式是每个数字用３位表示，这样就是３×９＝２７个字节，由于８的二进制表示形式１０００，不能用３位表示，我使用了一个小技巧就是将８表示位０００，然后用多出来的５个字表示８所在的位置，就可以用ＤＷＯＲＤ表示了。
用移位和或操作将数据逐个移入，比乘法速度要快点。
定义了几个结果来存储遍历到了结果和搜索完成后保存最优路径。
算法描述：过程 BREADTH-SEARCH(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);(7)结点放在OPEN表的后面，使深度浅的结点可优先扩展。
广度优先搜索的源代码如下：void Bfs(){queue<Map> Queue;Queue.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 + derection[k];if(tmp.position < 0 || tmp.position > 8 || ( k > 1 && tmp.position / 3 != node.position /3 ) )continue;tmp.myindex = HashValue( node , k );if(0 != HashTable[tmp.myindex] ) continue;tmp.detail[ node.position ] = tmp.detail[ tmp.position ] ;// 移动空格tmp.detail[ tmp.position ] = 0 ;HashTable[tmp.myindex] = node.myindex; // 状态记录到hashtable中if( node.myindex == EndIndex ) return ;Queue.push( tmp );}}return ; }实验流程图：三、所用仪器、材料（设备名称、型号、规格等或使用软件）硬件:个人计算机软件: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>using namespace std;#define HashTableSize#define NOT !#define UP 0#define DOWN 1#define LEFT 2#define RIGHT 3#define Bit chartypedef struct maps{Bit detail[9];int myindex; // 记录自己节点在hash表中的位置Bit position; // 记录空格（0）在序列中的位置}Map,*PMap;Map org; // 初始状态int EndIndex; //目标,上移，下移，左移，右移int const derection[4] ={ -3 , 3 , -1 , 1 } ;// 可移动的四个方向int const Factorial[9] = {40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 };int HashTable[HashTableSize]={0};//hash表,其中记录的是上一个父节点对应的位置/****八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）***/void input(){int i,j;int sum , count ,index ;for(i = 0 ; i < 9 ; i ++ ){scanf("%1d", &org.detail[ i ] );org.detail[ i ] || (org.position = i) ;}for(i = 0 ; i < 9 ; i ++ ) //计算逆序{if( 0 == org.detail[ i ] )continue;for(j = 0 ; j < i; j ++ )sum += ( 0 != org.detail[ j ] && org.detail[ j ] < org.detail[ i ] );}for( i = 0 , index = 0 ; i < 9 ; i ++ )// 计算初始状态的hash值{for(j = 0 , count = 0 ; j < i ; j ++)count += org.detail[ 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 = Parent.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 ]) ? ( 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.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 + derection[k]; if(tmp.position < 0 || tmp.position > 8 || ( k > 1 && tmp.position / 3 != node.position /3 ) )continue;tmp.myindex = HashValue( node , k );if(0 != HashTable[tmp.myindex] ) continue;tmp.detail[ node.position ] = tmp.detail[ tmp.position ] ; // 移动空格tmp.detail[ tmp.position ] = 0 ;HashTable[tmp.myindex] = node.myindex;// 状态记录到hashtable中if( node.myindex == EndIndex ) return ;Queue.push( tmp );}}return ;}/**** 通过hash表中记录的进行查找路径***/void FindPath(){int nowindex;int count =0 ;int nixu[9], result[9];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);getchar();while( NOT Stack.empty()){nowindex = Stack.top() - 1 ;Stack.pop();for( i = 0 ; i < 9; i ++ ) // 计算出逆序 {nixu[i] = nowindex / Factorial[ i ] ;nowindex %= Factorial[ i ];}memset( result , -1 , 9 *sizeof(int));for( i =0 ; i < 9 ; i ++ ) // 根据逆序计算排列 {for( j = 0 , k = nixu[i] ; j < 9 ; j ++ ){if(result[j] == -1 ) k --;if( k < 0 ) break;}result[j] = i ;}for( i =0 ; i < 9 ; i ++ ){printf("%3d",result[i]);if( 2 == i % 3 ) printf("\n");}if(0 != Stack.size() ){printf("\n ↓第%d步\n",++count);getchar();}}printf("\nThe End!\n");return ;}int main(){input(); //输入要排序的序列0--8long time =GetTickCount();Bfs();printf("计算用时：%dMS\n",GetTickCount()-time); FindPath();return 0; //返回结果}五、实验过程原始记录( 测试数据、图表、计算等)结果一：分析：此测试数据中的0位于奇序列中，故结果执行后为图示的结果。
