实验四 回溯法的应用------跳马算法

《实验四 回溯法的应用------跳马算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、时间就是金钱，效率就是生命！实验四回溯法的应用------跳马算法学号：012124345姓名：梁文耀一、实验目的掌握使用回溯法求解问题的基本思路；理解其特点。二、实验思想算法的基本思路是：定义结构体：structPLACE{intx,inty}表示棋盘上的位置。依题意，马每跳一步之后都可以从七个不同的方向选择下一步的跳马，当然，前提是跳的这一步在棋盘内且它前面的任何一步都没跳到这一格子上（限界），就可以认为这一步跳成功，否则跳马不成功。若跳马不成功，则找下一个方向尝试跳马，若七个方向都跳马不成功，则回溯。假设棋盘的行（列）数为n。在本算法中设置这样一个全局数组：c[8][2]={{2,1},

2、{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};来记录跳马的八个方向。三、程序分析（主要算法）intmap[12][12],status[12][12],kp;intstart,finsh;intc[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};唯有惜时才能成功，唯有努力方可成就！时间就是金钱，效率就是生命！intflag=0;voidprt(inta[][12])/*打印棋盘状态*/{inti,j;printf("");for(i=2;i<=9;i++)

3、{for(j=2;j<=9;j++)printf("%4d",a[i][j]);printf("");}}voidstatus2(void)/*计算棋盘各点条件数*/{inti,j,k,i2,j2,kz;for(i=0;i<12;i++)for(j=0;j<12;j++)status[i][j]=100;for(i=2;i<=9;i++)for(j=2;j<=9;j++){kz=0;唯有惜时才能成功，唯有努力方可成就！时间就是金钱，效率就是生命！for(k=0;k<=7;k++){i2=i+c[k][0];j2=j+c[k][1];if(map[i2][j2]<50)kz++;}statu

4、s[i][j]=kz;}//prt(status);}voidsort1(intb1[],intb2[])/*对8个可能的方向按条件数排序*/{inti,j,mini,t;/*b1[]记录状态值（升序），b2[]记录排序后的下标*/for(i=0;i<=7;i++){mini=i;for(j=i+1;j<=7;j++)if(b1[j]

5、d)/*初始化*/{inti,j;for(i=0;i<12;i++)for(j=0;j<12;j++)map[i][j]=100;for(i=2;i<=9;i++)for(j=2;j<=9;j++)map[i][j]=0;status2();}voidsearch(inti2,intj2)/*利用递归回溯进行搜索*/{if(flag==1)return;intb1[8],b2[8],i,i3,j3;kp++;for(i=0;i<=7;i++)//8个方向{唯有惜时才能成功，唯有努力方可成就！时间就是金钱，效率就是生命！b2[i]=i;b1[i]=status[i2+c[i][0]][j2+c[

6、i][1]];}//forsort1(b1,b2);for(i=0;i<=7;i++)//检查是否可以走{i3=i2+c[b2[i]][0];//按照排序中的方向查找j3=j2+c[b2[i]][1];if(map[i3][j3]==1&&kp==65){prt(map);flag=1;}if(map[i3][j3]==0)//若有路可以走，则执行下面操作{map[i3][j3]=kp;search(i3,j3);//递归调用map[i3][j3]=0;//若还没有走完并且已经没有路走则恢复0状态}//if}//forkp--;//回朔唯有惜时才能成功，唯有努力方可成就！时间就是金钱，效率就是

7、生命！}//searchintmain(){introw,column;charch;//intstart,finsh;while(true){//打印提示信息cout<<"1:开始程序"<