人工智能8位数码难题的问题求解

PAGEPAGE1实验报告实验名称：8位数码难题的问题求解实验目的和要求：目的：1.理解和掌握解决实际问题的搜索算法或策略；2.能够用选定的编程语言实现搜索算法；要求：1.随机输入1-8数字；2.采用所学过的搜索算法（算法不限，但需要有注释，采用算法之一，或几种算法实现）；3.要求输出算法执行的过程结果；4.按顺序输出1-8数字；实验软硬件要求：网络计算机，c++编程环境实验内容、方法和步骤（可附页）我们将八数码难题分布在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态如图所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。我们将是用广度优先搜索算法来解决这一问题。我们先拟定初始数列为035214876（0表示空位）算法流程图：初始状态3521487612384765结果数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。代码如下：#include<stdio.h>#include<stdlib.h>#include<windows.h>#include<queue>#include<stack>usingnamespacestd;#defineHashTableSize362881#defineNOT!#defineUP0#defineDOWN1#defineLEFT2#defineRIGHT3#defineBitchartypedefstructmaps{Bitdetail[9];intmyindex;//记录自己节点在hash表中的位置Bitposition;//记录空格（0）在序列中的位置}Map,*PMap;Maporg;//初始状态intEndIndex;//目标,上移，下移，左移，右移intconstderection[4]={-3,3,-1,1};//可移动的四个方向intconstFactorial[9]={40320,5040,720,120,24,6,2,1,1};intHashTable[HashTableSize]={0};//hash表,其中记录的是上一个父节点对应的位置/****八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）***/voidinput(){inti,j;intsum,count,index;printf("输入九个数：\n");//必须输入一个0作为空值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?161328:322561;//目标状态的hash值return;}/***hash值的计算*Parent:父状态的hash值*direct:移动的方向**/inlineintHashValue(Map&Parent,int&direct){inti=Parent.position;intnewindex=Parent.myindex;Bit*p=Parent.detail;switch(direct){caseUP:{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;}caseDOWN:{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;}caseLEFT:returnnewindex-40320;break;caseRIGHT:returnnewindex+40320;break;}returnnewindex;}/****广度优先搜索***/voidBfs(){queue<Map>Queue;Queue.push(org);HashTable[org.myindex]=-1;while(NOTQueue.empty()){Mapnode=Queue.front();Queue.pop();for(intk=0;k<4;k++){Maptmp=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表中记录的进行查找路径***/voidFindPath(){intnowindex;intcount=0;intnixu[9],result[9];inti,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(NOTStack.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("\nFinish!\n");return;}intmain(){inp