人工智能—采用状态空间法求解八数码问题
八数码难题也称九宫问题，它是在3×3的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，要求程序能输入任意的初始状态和目标状态，要求通过空格来移动八张牌使得棋盘由初始状态到达目标状态。移动规则为：每次只能将与空格（上下左右）相邻的一个数字平移到空格中。如下图所示，左侧为初始状态，右侧为目标状态在开始求解之前，我们先判断该八数码问题是否有解，判断方法如下：八数码问题的一个状态实际上是0~9的一个排列，空格用0表示，对于任意给定的初始状态和目标状态，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，排列只能在同类排列之间转化，而从奇排列不能转化成偶排列或相反。如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。例：871526340这个排列的Y=0+0+0+1+1+3+2+3+0=10，10是偶数，所以是偶排列。871625340，Y=0+0+0+1+1+2+2+3+0=9，9是奇数，所以是奇排列。因此，可以在运行程序前检查初始状态和目标状态的排列是否相同，相同则问题可解，接着采用搜索算法求解，否则无解。我们可以采用广度优先算法来进行求解，大致流程如下附上一部分代码，有兴趣的同学可以自己尝试%查询是否找到目标节点
functiona=getit(close,dis)globali;forj=1:iifclose(j).con==disa=1;break;elsea=0;endendend上下左右移动模块
functionopen=opera(op,cl,f,dis)globali;[x,y]=find(f.con==0);ifx==1&&y==1open=rt(f,op,cl,dis);open=dn(f,open,cl,dis);elseifx==1&&y==2open=lt(f,op,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);elseifx==1&&y==3open=lt(f,op,cl,dis);open=dn(f,open,cl,dis);elseifx==2&&y==1open=up(f,op,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);elseifx==2&&y==2open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=rt(f,open,cl,dis);open=dn(f,open,cl,dis);elseifx==2&&y==3open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=dn(f,open,cl,dis);elseifx==3&&y==1open=up(f,op,cl,dis);open=rt(f,open,cl,dis);elseifx==3&&y==2open=lt(f,op,cl,dis);open=up(f,open,cl,dis);open=rt(f,open,cl,dis);elseifx==3&&y==3open=lt(f,op,cl,dis);open=up(f,open,cl,dis);endend查询重复操作模块
function[]=search(f,op,cl)globale;globali;%e%open(e-1).conforj=1:e-1ifop(j).con==f.cone=e-1;breakendendforj=1:i-1ifcl(j).con==f.cone=e-1;break;endendend最后附上不完全效果图