回溯法解决八数码问题python
这次人工智能的作业就是用回溯法解决八数码问题，经过一天多的功夫，终于写出来了。下面是正题
回溯法是人工智能领域的一种重要的盲目搜索算法，何为盲目算法，即是基于规则，不断的尝试可能的路径，直到到达目的的解为止。回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法一般需要三张表ps表：用于保存当前路径的状态，如果找到目标状态，ps就是解题路径上的状态有序集。nps表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到即未生成扩展。nss表：不可解状态集，列出了找不到解题路径的状态，如果在搜索中扩展出的状态是该表的元素，则将该状态排除。此外，八数码还有一个书否有解的条件，即初始状态和目标状态的逆序数奇偶性相同。逆序数：一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，也就是每个数字前面比它大的数字的个数的和，称为这个状态的逆序。回溯法搜索过程示意图如下所示：其搜索起点为A初始值：ps=[A],nps=[A],nss=[]，目标点为G
0搜索点psnpsnss1A[A][A][]2B[BA][BCDA][]3E[EBA][EFBCDA][]4I[IJEBA][IJEFBCD][]5J[JEBA][JEFBCDA][I]6F[FBA][FBCDA][EJI]7K[KFBA][KFBCDA][EJI]8C[CA][CDA][BFKEJI]9G[GCA][GHCDA][BFKEJI]在搜索过程中，先进行深度搜索，直到到达指点深度，或者不可解点返回，并将该状态置为不可解点，然后回到上一节点进行扩展。直到找到结果或者搜完所有深度为止。回溯法实现八数码思路亦是如此初始状态:283164705
目标状态:123804765
下面是python代码,数码的状态用一维数组表示节点状态类Node.py
#encoding:utf-8fromNodeimport*classback:def__init__(self,orignate,target,length):self.origate=orignate#初始状态self.target=target#目标状态self.ps=[]#PS表，用于保存当前搜索路径的状态self.nps=[]#nps表，用于保存等待搜索的状态self.nss=[]#nss表，用于保存不可到达目的地的状态集self.spce=[-3,3,-1,1]#上下左右四个移动方向self.length=lengthself.MaxDegree=5#深度限制，到达此深度回溯defissolve(self):#判断到目标状态是否有解targetVer=self.getreVersNum(self.target.state)orinateVer=self.getreVersNum(self.origate.state)if(targetVer%2!=orinateVer%2):returnFalseelse:returnTruedefgetreVersNum(self,state):#获取逆序数sum=0foriinrange(0,len(state)):if(state[i]==0):continueelse:forjinrange(0,i):if(state[j]>state[i]):sum+=1returnsum#defgetspaceIndex(self):#获得空格所在的位置#foriinrange(len(self.origate)-1):#if(self.origate[i]==0):#returnidefcopyArray(self,state):arr=[]returnarr+state#判断状态数码是否存在defisexit(self,node,table):foriintable:if(i.state==node.state):returnTruereturnFalse#主要算法，回溯过程defbackMainProcess(self):self.ps.append(self.origate)self.nps.append(self.origate)while(len(self.nps)):originateState=self.ps[-1]spacIndex=originateState.state.index(0)if(originateState.state==self.target.state):returnTrueelse:#到达指定深度，回溯if(originateState.degree>=self.MaxDegree):self.ps.pop()self.nps.pop()if(self.nps[-1]!=self.ps[-1]):self.ps.append(self.nps[-1])self.nss.insert(0,originateState)continueflag=Falseforiinrange(len(self.spce)):if((i==0and(spacIndex+self.spce[i])>=0)or(i==1and(spacIndex+self.spce[i]):(2,8,3)(1,0,4)(7,6,5)->:(2,0,3)(1,8,4)(7,6,5)->:(0,2,3)(1,8,4)(7,6,5)->:(1,2,3)(0,8,4)(7,6,5)->:(1,2,3)(8,0,4)(7,6,5)->:A和A*算法C实现【人工智能】8数码问题和15数码问题
实验目的和要求:
（1）熟悉掌握启发式搜索算法A*及其可采纳性
（2）编写程序实现8数码和15数码问题，采用至少两种估价函数
（3）分析估价函数求解问题时候的效率差别，分析估价函数对搜索算法的影响
实验思路：
（1）、用结构体变量存储每个结点的状态值（错位棋牌或者移动步骤）
定义两个队列CLOSE表和OPEN表用来记录和操作结点
（2）、初始化：建立只包含初始状态节点s的搜索图G:={s}
将s入OPEN表，CLOSE表为空
（3）、搜索循环：搜索结束条件为找到目标结点为止（可以定义一个target变量来记录状态）
首先取出OPEN表表首结点（队列出队PUSH）
将此节点入CLOSE表
按规定顺序（左、下、右、上）扩展结点并且入OPEN表
然后分别计算其f（n,ni）作为结点的状态值
利用归并排序排序OPEN表（依据状态值）
然后继续循环
实验代码：
#include#include#include#defineN3//#defineN4//记录层数的全局变量intlayer=0;//保存初始表盘的初态和末态staticintPstart[N][N]={1,0,3,7,2,4,6,8,5};staticintPend[N][N]={1,2,3,8,0,4,7,6,5};//staticintPstart[N][N]={1,3,0,4,5,2,7,8,9,6,11,12,13,10,14,15};//staticintPend[N][N]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};//定义每个结点数据类型typedefstructPNode{intstatus;//与末态表盘之间的错位个数intPpoint[N][N];//记录每个小格的数据}PNode;//定义open表和close表的结构(采用队列形式)//队列的定义typedefstructListNode{//定义链表结点PNode*pNode;//数据项structListNode*List_next;//指向下一结点的指针域}ListNode,*pListNode;typedefstructQueue{//定义队列相当于两个指针分别控制链表的头尾pListNodeqHead;//指向队列的头pListNodeqTail;//指向队列的尾}Queue;Queue*Open_List;//open表Queue*Close_List;//close表//ListNode*Lhead;//队列的操作//创建表盘结点PNode*CreatePNode(){PNode*p=(PNode*)malloc(sizeof(PNode));p->status=0;returnp;}//创建链表结点ListNode*CreatNode(PNode*p){//PNode*pp是指向数据结构体的指针ListNode*newNode=(ListNode*)malloc(sizeof(ListNode));if(!newNode){printf("分配内存空间失败");system("pause");exit(1);}newNode->List_next=NULL;newNode->pNode=p;returnnewNode;}//队列初始化,相当于创建首元结点voidQueueInit(Queue*q){//Queue*q是指向队列的指针assert(q);q->qHead=CreatNode(NULL);q->qTail=q->qHead;}//入队voidQueuePush(Queue*q,PNode*p){assert(q);q->qTail->List_next=CreatNode(p);q->qTail=q->qTail->List_next;}//出队,将首元结点后的一个结点指针出队并返回ListNode*QueuePop(Queue*q){pListNodedNode=q->qHead->List_next;//首元结点后的第一个结点if(dNode){//存在一个结点q->qHead->List_next=dNode->List_next;if(q->qHead->List_next==NULL){//队列只有一个结点q->qTail=q->qHead;}}returndNode;}//判断队列是否为空intQueueEmpty(Queue*q){returnNULL==q->qHead->List_next;}//计算表的结点个数intListLength(ListNode*l){intcount=0;//记录个数//首元结点不算一个结点l=l->List_next;while(l!=NULL){count++;l=l->List_next;}returncount;}//定义评价函数(错位棋牌个数)voidjudgefun1(PNode*p){p->status=0;for(intm=0;mPpoint[m][n]!=0){p->status++;}}}}p->status=p->status+layer;}//定义评价函数(错位棋牌数到达目标位置最少步数)*****************************????????????voidjudgefun2(PNode*p){p->status=0;inti=0;intj=0;do{if(p->Ppoint[i][j]==0){if(jstatus+abs(m-i)+abs(n-j);}}}if(jstatus+layer;}//判断是否生成目标结点booljudgeTarget(PNode*p){for(intm=0;mPpoint[m][n-1];ptmp[0]->Ppoint[m][n-1]=t;//judgefun1(ptmp[0]);judgefun2(ptmp[0]);QueuePush(Open_List,ptmp[0]);//扩展结点入队//判断扩展结点是否是目标结点if(judgeTarget(ptmp[0])){//将此结点入CLOSE表QueuePush(Close_List,ptmp[0]);return0;}}//下if(m!=N-1){//只要不在第N行ptmp[1]=CreatePNode();for(intj=0;jPpoint[j][k];}}t=ptmp[1]->Ppoint[m][n];ptmp[1]->Ppoint[m][n]=ptmp[1]->Ppoint[m+1][n];ptmp[1]->Ppoint[m+1][n]=t;//judgefun1(ptmp[1]);judgefun2(ptmp[1]);QueuePush(Open_List,ptmp[1]);if(judgeTarget(ptmp[1])){//将此结点入CLOSE表QueuePush(Close_List,ptmp[1]);return0;}}//右if(n!=N-1){//只要不在第N列ptmp[2]=CreatePNode();for(intj=0;jPpoint[j][k];}}t=ptmp[2]->Ppoint[m][n];ptmp[2]->Ppoint[m][n]=ptmp[2]->Ppoint[m][n+1];ptmp[2]->Ppoint[m][n+1]=t;//计算估计函数的值//judgefun1(ptmp[2]);judgefun2(ptmp[2]);QueuePush(Open_List,ptmp[2]);if(judgeTarget(ptmp[2])){//将此结点入CLOSE表QueuePush(Close_List,ptmp[2]);return0;}}//上if(m!=0){ptmp[3]=CreatePNode();for(intj=0;jPpoint[j][k];}}t=ptmp[3]->Ppoint[m][n];ptmp[3]->Ppoint[m][n]=ptmp[3]->Ppoint[m-1][n];ptmp[3]->Ppoint[m-1][n]=t;//judgefun1(ptmp[3]);judgefun2(ptmp[3]);QueuePush(Open_List,ptmp[3]);if(judgeTarget(ptmp[3])){//将此结点入CLOSE表QueuePush(Close_List,ptmp[3]);return0;}}return1;}//排序表：分治法实现ListNode*list_spilt(ListNode*head){//Queue*q//传入head->next分裂链表并且返回第二个子链表的首指针if(NULL==head){//没有元素可以分裂returnhead;}ListNode*tmp;//用于记录前一个表的表尾ListNode*slow=head;ListNode*fast=head;//一个快指针一个慢指针用于定位中间结点while(fast){fast=fast->List_next;if(fast){fast=fast->List_next;}//相当于fast移动两次slow移动一次if(NULL==fast){break;}slow=slow->List_next;}tmp=slow;slow=slow->List_next;//指向第二个子链表的首tmp->List_next=NULL;//断链returnslow;}ListNode*merge(ListNode*head1,ListNode*head2){//合并两个链表，并且返回排序完成之后的指针if(NULL==head1)returnhead1;if(NULL==head2)returnhead2;ListNodehead;//记录排序链表的首元节点ListNode*tail=&head;//尾插法实现while(head1&&head2){if(head1->pNode->statuspNode->status){tail->List_next=head1;head1=head1->List_next;}else{tail->List_next=head2;head2=head2->List_next;}tail=tail->List_next;}if(head1){tail->List_next=head1;}if(head2){tail->List_next=head2;}returnhead.List_next;}ListNode*merge_sort(ListNode*head){//传入head->nextif(head==NULL||head->List_next==NULL){//分裂到只包含一个结点returnhead;}ListNode*head1=head;ListNode*head2=list_spilt(head);//对链表分别进行分裂head1=merge_sort(head1);head2=merge_sort(head2);//对链表合并returnmerge(head1,head2);}intmain(){intsteps=1;inttarget=-1;//初始化/*建立只包含初始状态结点s的搜索图GOPEN={s}CLOSE={}*///先将两表（队列）初始化Open_List=(Queue*)malloc(sizeof(Queue));Close_List=(Queue*)malloc(sizeof(Queue));QueueInit(Open_List);QueueInit(Close_List);//将s插入open表PNode*s=(PNode*)malloc(sizeof(PNode));for(intj=0;jPpoint=Pstart;//存入数组QueuePush(Open_List,s);//入队//搜索循环（循环条件是扩展结点包含目标结点）while(target!=0){//当target=1时找到目标结点//取出OPEN表首结点作为扩展结点ListNode*extendNode=QueuePop(Open_List);//将其移入CLOSE表中QueuePush(Close_List,extendNode->pNode);//扩展结点插入OPEN表中target=move(Open_List,extendNode->pNode);//对每个子节点算其估计函数(在move函数中实现)//排序OPEN//ListNode*Lhead=Open_List->qHead->List_next;Open_List->qHead->List_next=merge_sort(Open_List->qHead->List_next);}printf("%d数码问题：空格移动位置步骤为： ",8);//找到目标结点之后输出CLOSE队列找到相应的路径Close_List->qHead=Close_List->qHead->List_next;while(Close_List->qHead!=NULL){printf("-----steps%d----- ",steps++);for(inti=0;ipNode->Ppoint[i][j]);}printf(" ");}Close_List->qHead=Close_List->qHead->List_next;printf("---------------");printf(" ");}system("pause");return0;}测试数据：（两组）
（1）对于8数码问题：1,0,3,7,2,4,6,8,5
对于15数码问题：1,3,0,4,5,2,7,8,9,6,11,12,13,10,14,15
（2）对于8数码问题：1,2,3,8,0,4,7,6,5
对于15数码问题：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0
实验结果：
（1）8数码问题：
（2）15数码问题：
深度优先搜索解决八数码难题
八数码问题以前用java写的通过深度优先瘦素解决八数码难题。
对于八数码难题来说，可以把9宫格看成一个[3][3]的二维数组，将空格位置看成0，将0可以移动的方向看成树的枝丫，分为上下左右4个方向。具体实现思路：
每调用一次深度+1，如果深度达到指定深度，结束找出0所在位置，对0的位置进行判断，判断是否能移动。判断顺序为左，上，右，下(列与行不能小于0，不能大于2)。为了避免出现先左移后右移等状况，需要设置一个变量，当变量为某个值时不能向某个方向移动。判断能否向左移动，如果能，对0进行移动，将移动后的数组与最终数组进行判断，如果正确，则输出right，停止程序。如果不是则再次调用移动函数（递归调用）。恢复原状态，写4个还原函数分别将数组还原到移动前的状态，将判断移动方向的变量还原到移动前的状态(回朔法)。判断能否向其他方向移动（之后流程与向左移动相同）。如果4个方向都判断完，结束packageaa;importjava.util.Scanner;publicclassAz{staticint[][]arr2=newint[3][3];//={{1,2,3},{8,0,4},{7,6,5}};staticintaaa;//用于记录移动步数staticintbbb=5;//用于记录深度publicstaticvoidmain(String[]args){int[][]arr1=newint[3][3];//定义二维数组System.out.println("请输入最终数组（空格用0代替）（按行输入）：");Scannerinput=newScanner(System.in);//创建键盘输入函数for(inti=0;iintss=input.nextInt();arr2[i][j]=ss;}}System.out.println("$$$$$$$$$$$$$$$$$$$$$$$");System.out.println("最终状态：");shuchu(arr2);System.out.println("$$$$$$$$$$$$$$$$$$$$$$$");System.out.println("请输入要判断的数组（空格用0代替）（按行输入）：");for(inti=0;iintss=input.nextInt();arr1[i][j]=ss;}}System.out.println("你输入的数组：");shuchu(arr1);System.out.println("");yidong(arr1,1,0);//调用移动函数System.out.println("..................................................");System.out.println("没有找到");input.close();}publicstaticvoidshuchu(inta[][]){//输出二维数组for(inti=0;iSystem.out.print(a[i][j]+"");}System.out.println();}}publicstaticbooleanpanduan(inta[][],intb[][]){//判断两个二维数组的内容是否相等booleanesta=true;for(inti=0;iif(a[i][j]!=b[i][j]){esta=false;}}}returnesta;}publicstaticvoidjieshu(){//结束函数aaa++;//移动步数System.out.println("jieshu");System.out.println("共用了"+aaa+"步");System.exit(0);}publicstaticint[][]zuoyi(inta2[][]){//还原左移函数int[][]a1=a2;intn1=0;intn2=0;for(inti=0;iif(a1[i][j]==0){n1=i;//移动格所在的行n2=j;//移动格所在的列}}}intt1=a1[n1][n2+1];a1[n1][n2+1]=a1[n1][n2];a1[n1][n2]=t1;returna1;}publicstaticint[][]shangyi(inta2[][]){//还原上移函数int[][]a1=a2;intn1=0;intn2=0;for(inti=0;iif(a1[i][j]==0){n1=i;//移动格所在的行n2=j;//移动格所在的列}}}intt1=a1[n1+1][n2];a1[n1+1][n2]=a1[n1][n2];a1[n1][n2]=t1;returna1;}publicstaticint[][]youyi(inta2[][]){//还原右移函数int[][]a1=a2;intn1=0;intn2=0;for(inti=0;iif(a1[i][j]==0){n1=i;//移动格所在的行n2=j;//移动格所在的列}}}intt1=a1[n1][n2-1];a1[n1][n2-1]=a1[n1][n2];a1[n1][n2]=t1;returna1;}publicstaticint[][]xiayi(inta2[][]){//还原下移函数int[][]a1=a2;intn1=0;intn2=0;for(inti=0;iif(a1[i][j]==0){n1=i;//移动格所在的行n2=j;//移动格所在的列}}}intt1=a1[n1-1][n2];a1[n1-1][n2]=a1[n1][n2];a1[n1][n2]=t1;returna1;}publicstaticvoidyidong(inta[][],ints,intx){aaa++;//移动步数int[][]ar2=a;//传过来的数组intq=s;//深度intc=x;//用来判断不能向哪个方向移动（1，不能右移2，不能下移3，不能左移4，不能上移）System.out.println("第"+aaa+"步"+":");System.out.println("深度："+q);shuchu(ar2);if(q==bbb){System.out.println("*********************************");System.out.println("到达设定的深度");System.out.println("*********************************");}else{intnum1=-1;intnum2=-1;for(inti=0;iif(a[i][j]==0){num1=i;//移动格所在的行num2=j;//移动格所在的列}}}intpan=c;into=num2-1;//System.out.println(o);if(oSystem.out.println("左移：");pan=3;intt1=ar2[num1][num2-1];ar2[num1][num2-1]=ar2[num1][num2];ar2[num1][num2]=t1;booleanaa=panduan(ar2,arr2);if(aa==true){System.out.println("right");jieshu();}else{yidong(ar2,q+1,pan);pan=c;ar2=zuoyi(ar2);//调用左移还原函数System.out.println("还原：");shuchu(ar2);System.out.println("");}}if(num1-1System.out.println("上移：");pan=4;intt1=ar2[num1-1][num2];ar2[num1-1][num2]=ar2[num1][num2];ar2[num1][num2]=t1;booleanaa=panduan(ar2,arr2);if(aa==true){System.out.println("right");jieshu();}else{yidong(ar2,q+1,pan);pan=c;ar2=shangyi(ar2);//调用上移还原函数System.out.println("还原：");shuchu(ar2);System.out.println("");}}if(num2+1>2||pan==3){//右移System.out.println("");}else{System.out.println("右移：");pan=1;intt1=ar2[num1][num2+1];ar2[num1][num2+1]=ar2[num1][num2];ar2[num1][num2]=t1;booleanaa=panduan(ar2,arr2);if(aa==true){System.out.println("right");jieshu();}else{yidong(ar2,q+1,pan);pan=c;ar2=youyi(ar2);//调用右移还原函数System.out.println("还原：");shuchu(ar2);System.out.println("");}}if(num1+1>2||pan==4){//下移System.out.println("");;}else{System.out.println("下移：");pan=2;intt1=ar2[num1+1][num2];ar2[num1+1][num2]=ar2[num1][num2];ar2[num1][num2]=t1;booleanaa=panduan(ar2,arr2);if(aa==true){System.out.println("right");jieshu();}else{yidong(ar2,q+1,pan);pan=c;ar2=xiayi(ar2);//调用下移还原函数System.out.println("还原：");shuchu(ar2);System.out.println("");}}}}}输入格式：深度需要在全局变量里修改，我设定的是5。