迷宫最短路径问题的计算机解法_求迷宫的最短路径

迷宫最短路径问题的计算机解法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“求迷宫的最短路径”。

文章编号:10060042(14)111;

/ / 假设迷宫入口的出发点存于seat [thepath(int m ,int n)/ / 0

2{/ / 变量声明部分———对所用其它变量完成变

量声明

i = 0;/ / 此处开始给迷宫设置围墙 while(i

{maze[0 ] [i ] = 1;maze[m + 1 ] [i ] = 1;i = i + 1;} i = 1;

while(i

{maze[i ] [0 ] = 1;maze [i ] [ n + 1 ] = 1;i = i + 1;} i = 1;

/ / 此处开始建立迷宫;并对标志数组初始化 while(i

{maze [i ] [j ] = random(1);

/ / 随机函数产生0 或1 并赋予迷宫 / / 可用Pat 值调整0 与1 的比例,然后打印迷

宫相应位置(略)

status [i ] [j ] = 0;j = j + 1;} i = i + 1;}

/ / 读入dire 数组;按顺时针建立八个方向上的位移(略);

/ / 寻找最短路径

if(maze [1 ] [1 ] = = 0 & & maze [m] [ n ] = = 0)/ / 出入口都可通行

top = 1;

/ / top 指向seat 数组中最新记入迷宫通行点的位置 f = 1;

/ / f 指向seat 数组中存放即将作为新出发点的位置 j = 0;/ / j = 0 ,表示找不到最短路径;j = 1 ,表示

成功找到最短路径

while(f

{/ / 从f 所指的出发点出发,对八个方向搜索可

通行的位置

x = seat [f ] [0 ] + dire[i ] [1 ];y = seat [f ] [1 ] + dire[i ] [2 ];if(x = = m & & y = = n){/ / 找到最短路径,打印输出 printf(“%d , %d n”,m ,n);while(f!=thepath

6.算法分析 6.1 时间复杂性

这里选用渐进时间复杂度(Asymptotic

Time Complexity)。作为问题的基本操作的 原操作,应是其重复执行次数和算法的执行 时间成正比的原操作,多数情况下它是最深 层循环内的语句中的原操作,它的执行次数 和包含它的语句的频度(Frequency Count)相 同。因此,建立迷宫需要的时间为O(m 3 n)。在最坏情况下有m 3 n-1 个位置要进 入seat 数组,所以寻找路径也需要O(m 3 n),总的时间复杂性为O(m 3 n)。6.2 空间复杂性

本问题的空间复杂度(Space Complexi2

ty)与算法密切相关,它不仅需要存储空间来 寄存迷宫本身所用的信息,还需要一些对数 据进行操作的工作单元和存储一些实现计算

所需信息的辅助空间。

其中,数组maze、status、seat 所需要的空 间都与m 3 n 成正比,其余都是常数。所以, 总的空间复杂性为O(m 3 n)。

此外,尚需说明的是,所谓当前位置“可 通”,指的是未曾走到过的通道,即要求该位 置不仅是通道,而且既不在当前路径上(否则 所求路径就不是简单路径),也不是曾经纳入 过路径的通道(否则只能在死胡同内转圈)。一个迷宫的最短路径可能不止一条,本 算法只给出首先找到的一条。首先找到哪一条最短路径,与在任一位置上对八个方向的 搜索次序有关,即与dire 数组元素值的排列 次序有关(如图1 所示),调整dire 数组元素

值的排列次序,就可得到其它的最短路径。

参考文献

[1 ]严蔚敏、吴伟民.数据结构[M].北京:清华大学

出版社,2002.[2 ]郭洁志.计算机软件实践[M].陕西:西北电讯出

版社,1985.[3 ]黄刘生、唐策善.数据结构[M].安徽:中国科学

技术大学出版社,2002.[4 ]王立柱.C/ C + + 与数据结构[M].北京:清华大

学出版社,2002.45

第17 卷第1 期

2004 年2 月

高等函授学报(自然科学版)

Journal of Higher Correspondence Education(Natural Sciences)Vol.17 No.1 February 2004__