如图,有如此的一个迷宫,要从起点到终点,紫色方格是障碍物方格,不可通行。
求:
找出一条从起点到终点的道路,在到达终点之前,必须走遍所有可通行的方格一次,而且到达终点的
转弯次数要最少,每改变一次前进方向算作转弯一次。

经典的回溯法解题思路:
 1 //方格m*n,k个障碍物
 2 int m,n,k;
 3 //目标方格
 4 int dx,dy;
 5 //当前拐弯数,最右拐弯数
 6 int dirs,best;
 7 //总共找到几条路线
 8 int count;
 9 
10 void search(int depth,int x,int y,int di)
11 {
12     if(depth==m*n-&& dx==&& dy==&& )
13     {        
14         //找到一条路线
15         count++;
16 
17         if(dirs<best)
18         {
19             best=dirs;
20             //保存最优路径,即标记不为0的方格
21             save();
22         }
23         else
24         {
25             return;
26         }
27     }
28     else
29     {
30         for(int i=1;i<=8;i++)
31         {
32             if(没有出边界 && 该方格未行走过)
33             {
34                 board[x+dx[i]][y+dy[i]]=depth+1;
35                 if(di!=i) dirs++;
36                 search(depth+1,x+dx[i],y+dy[i],i);
37                 //恢复转弯次数
38                 if(di!=i) dirs--;
39                 //恢复未行走标记
40                 board[x+dx[i]][y+dy[i]]=0;
41             }
42         }
43     }
44 
45 }

看上去挺复杂的问题,用回溯法可以很好地解决,还可以加入剪枝函数,即检测当前dirs是否已经大于best,如果
是的话,直接返回。

posted on 2010-08-12 16:07 野猪红 阅读(700) 评论(0)  编辑 收藏 引用 所属分类: 算法Show Demo

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理