图搜索与问题求解(八数码)

图搜索与问题求解实验报告一实验题目图搜索与问题求解二实验目的1熟悉和掌握启发式搜索/A*搜索的定义、估价函数和算法过程；2理解和掌握搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3比较并分析图搜索策略的实质，通过实验理解启发式搜索/A*搜索的意义。三实验要求1以九宫问题/八数码问题为例，以某种启发式搜索/A*搜索策略编程演示其搜索过程；2定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；3对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。四数据结构typedefstructQnode{ //队列的节点类型定义 longa; //将8数码转化为长整型后入队列 intdnum; //与目标状态数码不同的位置的个数 Qnode*next;}*QueuePtr;typedefstruct{ QueuePtrfront; //队头指针 QueuePtrrear; //队尾指针}LinkQueue; //链式队列五实验算法1说明有解和无解如何判定；intNiXu(inta[][3]) //求出所给状态的逆序数{ inti,j,k=0,sum=0; intb[8]; for(i=0;i<3;i++) for(j=0;j<3;j++) if(a[i][j]) //空格用0代替，逆序不计空格 b[k++]=a[i][j]; for(i=1;i<8;i++) for(j=0;j<i;j++) if(b[i]<b[j]) sum++; returnsum;}if(NiXu(start)%2!=NiXu(end)%2) printf("无法到达！\n"); else { printf("广度优先搜索如下：\n\n"); search();}2说明启发式函数如何设定；inth(longx){ intsum=0; intb[3][3]; u_trans(x,b); for(inti=0;i<3;i++) for(intj=0;j<3;j++) if(end[i][j]!=b[i][j]) sum++; returnsum;}3说明实验中采用的搜索算法。用启发式函数，选择的是全局择优搜索算法。voidsearch(){ inti,k=0; introw,col,r,c,b[3][3]; longu; longt; while(!QueueEmpty(Q)) //队列非空 { DeQueue(Q,u); //出队列 t=u; if(!k) store[k++]=u;//初始状态存入路径 u_trans(u,b); for(i=0;i<4;i++) { u=t; foundZero(u,row,col,r,c); if(canMove(i,row,col,r,c)) { temp(b[row][col],b[r][c]); u=trans(b); if(isAim(u)) { store[k++]=u; print(store); return; } if(!used(u)) { EnQueue(Q,u); store[k++]=u; } temp(b[row][col],b[r][c]); } } }}六