留言 | 关于 | 联系
基础数学 语言相关算法实现 其它知识
返回首页
当前位置: 首页 > 程序设计 > 算法实现 > 迷宫问题算法(优于递归,深度优先,广度优先)

迷宫问题算法(优于递归,深度优先,广度优先)

时间:2010-03-26 20:50来源:网络 作者:天地之灵 点击:
作者提出的迷宫问题的新算法,并认为该算法优于递归、深度优先和广度优先搜索算法。

 

在一个n*m的迷宫里,每一个坐标点有两种可能:0或1,0表示该位置允许通过,1表示该位置不允许通过.
如地图:
0 0 0 0 0
1 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 0 0 1 0
最短路径应该是
AB000
1C101
ED111
F1JKL
GHI1M
即:
(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)
由input.txt中输入一个迷宫,以坐标的方式输出从左上角到右下角的最短路径.
如:
input(from input.txt):

5 5
0 0 0 0 0
1 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 0 0 1 0

output (to screen):

(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)

input:
5 5
0 0 0 0 0
1 1 1 0 1
0 0 1 1 1
0 1 0 0 0
0 0 0 1 0

output:

There is no way to leave!

算法分析:
如示例地图:
00000
10101
00111
01000
00010
我们可知,点[5,5]到点[5,5]的距离为0(废话)
因此,我们把该位置标志为0,
点[4,5]到点[5,5]的距离为点[5,5]到点[5,5]的距离+1,也即1.
点[4,4]到点[4,5]的距离至多为点[4,5]到点[5,5]的距离+1,因为点[4,4]可以直接到达点[4,5],所以点[4,4]到点[5,5]的距离为2;
.
.
.
.
点[1,1]到点[5,5]的距离为12,并且可以证明是最短距离.
此时,由于点[1,1]到点[5,5]的距离为12,且点[1,2]到点[5,5]的距离为11,我们便可以知道,从点[1,1]到点[1,2],一定是更接近点[5,5]而不是更远离,接下去我们找点[1,2]周围距离为10的,[1,3]周围距离为9的......直到找到[5,5],我们找到的就是最短路径.

算法用C语言表示大致如下:

 

  1. main() 
  2.     int a[100][100],b[100][100]; 
  3.     int n,m,i,j,x,y; 
  4.     int bo; file://标志每一次操作对数组B是否有改动,如果没有改动说明搜索完毕. 
  5.     //file://读入 N,M,A; 
  6.     //file://将B[N,M]记为0;将bo记为1; 
  7.     while (bo==1) 
  8.     { 
  9.         bo=0; 
  10.         for (i=1;i<=n;i++) 
  11.             for (j=1;j<=n;j++) 
  12.             { 
  13.                 if ((b[i][j]>-1)) 
  14.                 { 
  15.                     //file://搜寻[i,j]的上下左右四个方向,
                        //检查是否存在仍为-1或者大于b[i][j]+1的项,
     
  16.                     if (存在) 
  17.                     { 
  18.                         b[i+dx][j+dy]=b[i][j]+1;//dx,dy∈{-1,0,1}且dx*dy=0 
  19.                         bo=1; 
  20.                     } 
  21.                 } 
  22.                 if (b[1][1]==-1) 
  23.                 { 
  24.                     //表示没有结果,退出程序. 
  25.                 } 
  26.                 j=b[1][1];x=1;y=1;//x和y表示当前的坐标. 
  27.                 printf("(1,1)"); 
  28.                 for (i=1;i<=j;i++) 
  29.                 { 
  30.                     //搜索[x,y]周围[x+dx][y+dy]使得p[x+dx][y+dy]=p[x][y]-1; 
  31.                     x=x+dx;y=y+dy; 
  32.                     printf("-(%d,%d)",x,y); 
  33.                 } 
  34.             } 
  35.     } 
 

 

 

顶一下
(13)
92.9%
踩一下
(1)
7.1%
发表评论
评价:
验证码:点击我更换图片
推荐内容