回溯算法解迷宫问题（c语言）

《回溯算法解迷宫问题（c语言）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯算法解迷宫问题(C语言)回溯法也称为试探法,该方法首放弃关于问题规模大小的限制,并将问题的候选解按某一顺序逐一枚举和试验.当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探.如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解.在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯.扩大当前候选解的规模,并继续试探的过程成为向前试探.为了确保程序能够终止,调整时,必须保证曾被放弃过的填

2、数序列不被再次试验,即要求按某种有序模型生成填数序列.给解的候选者设定一个被检验的顺序,按这个顺序逐一生成候选者并检验.对于迷宫问题,我想用回溯法的难点就在如何为解空间排序,以确保曾被放弃过的填数序列不被再次试验.在二维迷宫里面,从出发点开始,每个点按四邻域算,按照右,上,左,下的顺序搜索下一落脚点,有路则进,无路即退,前点再从下一个方向搜索,即可构成一有序模型.下表即迷宫{ 1,1,1,1,1,1,1,1,1,1,   0,0,0,1,0,0,0,1,0,1,   1,1,0,1,0,0,0,1,0,1, 

3、  1,0,0,0,0,1,1,0,0,1,   1,0,1,1,1,0,0,0,0,1,   1,0,0,0,1,0,0,0,0,0,   1,0,1,0,0,0,1,0,0,1,   1,0,1,1,1,0,1,1,0,1,   1,1,0,0,0,0,0,0,0,1,   1,1,1,1,1,1,1,1,1,1}从出发点开始,按序查找下一点所选点列构成有序数列,如果4个方向都搜遍都无路走,就回退,并置前点的方向加1,依此类推....... 1 2 3 4 5 6 7 8 9 10 x 1 1 1 2 3

4、 3 3 2 ... y 0 1 2 2 2 3 4 4 ... c 1 1 3 3 1 1 2 1 ...#include#include#definen110#definen210typedefstructnode{intx;//存x坐标inty;//存Y坐标intc; //存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右}linkstack;linkstacktop[100];//迷宫矩阵intmaze[n1][n2]={1,1,1,1,1,1,1,1

5、,1,1,   0,0,0,1,0,0,0,1,0,1,   1,1,0,1,0,0,0,1,0,1,   1,0,0,0,0,1,1,0,0,1,   1,0,1,1,1,0,0,0,0,1,   1,0,0,0,1,0,0,0,0,0,   1,0,1,0,0,0,1,0,0,1,   1,0,1,1,1,0,1,1,0,1,   1,1,0,0,0,0,0,0,0,1,   1,1,1,1,1,1,1,1,1,1,};inti,j,k,m=0;main(){//初始化top[],置所有方向数为左for(

6、i=0;i

7、组合  {   //打印路径   printf("Theway%dis:",m++);   for(j=0;j<=i;j++)   {    printf("(%d,%d)-->",top[j].x,top[j].y);   }   printf("");   //打印选出路径的迷宫   for(j=0;j

8、 printf("O");     elseprintf("*");    }    printf("");   }   maze[top[i].x][top[i].y]=0;   top[i].c=1;   i--;   top[i].c+=1;   continue;  }  switch(top[i].c)  //向前试探  {   case1:    {     if(maze[top[