迷宫问题求解Word文件下载.docx
《迷宫问题求解Word文件下载.docx》由会员分享，可在线阅读，更多相关《迷宫问题求解Word文件下载.docx（18页珍藏版）》请在冰点文库上搜索。
指导教师签名：
2010年7月4日
系主任（或责任教师）签名：
摘要：
该程序主要由以下几部分构成：
1、用户输入迷宫的高度和宽度。
2、根据用户输入显示生成的迷宫或者错误提示信息。
3、求出从迷宫出口到入口的最短路径。
4、显示该路径，或者无解信息。
关键字：
迷宫、最短路径、动态规划、Dijkstra算法
引言：
寻径问题（最短路径）是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成）中两结点之间的最短路径。
该问题不论是在现实（比如火星探测）还是在网络中（比如各种游戏），都具有重大意义。
需求分析：
1、用户输入迷宫的高度和宽度。
2、根据用户输入显示生成的迷宫或者错误提示信息。
3、求出从迷宫出口到入口的最短路径。
4、显示该路径，或者无解信息。
数据结构设计：
char**maze;
//迷宫，0表示障碍，非0表示可通过。
char***path;
//存储每个点到入口的路径。
char**toBeChoosed;
//待选择的结点。
int**weight;
//搜索到的已知的每个点到入口最短距离的记录。
int*record;
//已知最佳结点的记录。
intcount;
//已知最佳结点个数。
算法设计：
#include<
stdio.h>
stdlib.h>
time.h>
conio.h>
string.h>
#defineSTART_X1
#defineSTART_Ywidth/2//入口横纵坐标。
。
#defineEND_Xheight
#defineEND_Ywidth/2//出口横纵坐标。
#defineMAX_W32767//权值上限。
intwidth,height;
//迷宫的宽和高。
charico[10][3]={"
■"
"
─"
│"
┌"
┐"
┘"
└"
□"
入"
出"
};
//各个符号。
inticoIndex[4][4]={1,4,0,5,6,2,5,0,0,3,1,6,3,0,4,2};
//对应方向的路标。
//获取二维数组下标偏移量。
voidGetDxDy（inti,int*dx,int*dy）
{
switch（i）
{
case0:
//左。
*dx=0;
*dy=1;
break;
case1:
//下。
*dx=1;
*dy=0;
case2:
//右。
*dy=-1;
case3:
//上。
*dx=-1;
default:
}
}
//判断该点是否是合法的，不越界。
intIsInMaze（intx,inty）
if（（x<
0）||（x>
=height）||（y<
0）||（y>
=width））
return（0）;
return
（1）;
}
//一维转为二维。
voidConvertToXY（intindex,int*x,int*y）
*x=index/width;
*y=index%width;
//二维转为一维。
intConvertToIndex（intx,inty）
return（x*width+y）;
//求绝对值。
intAbs（inta）
return（（a>
=0）?
a:
-a）;
intmain（void）
//迷宫，0表示障碍，非0表示可通过。
//存储每个点到入口的路径。
//待选择的结点。
//搜索到的已知的每个点到入口最短距离的记录。
int*record;
//已知最佳结点的记录。
intcount;
//已知最佳结点个数。
intx,y,dx,dy,x1,y1;
intindex;
intbestPoint,bestWeight,bestValue;
//在未选择的节点中所选择的最佳节点。
charagain;
inti,j;
again='
y'
;
while（again=='
）//用户选择继续。
system（"
cls"
）;
//清屏。
printf（"
Height="
scanf（"
%d"
&
height）;
//输入迷宫高度。
Width="
width）;
//输入迷宫宽度。
if（（height<
=0）||（width<
=0）||（height*width>
40000））
[Height>
0]&
&
[Width>
[Height*Width<
=40000]\n"
Pleaseinputagain..\n"
/**********************分配相应内存空间**********************/
maze=（char**）malloc（sizeof（char*）*height）;
toBeChoosed=（char**）malloc（sizeof（char*）*height）;
for（i=0;
i<
height;
i++）
maze[i]=（char*）malloc（sizeof（char）*width）;
toBeChoosed[i]=（char*）malloc（sizeof（char）*width）;
weight=（int**）malloc（sizeof（int）*height）;
weight[i]=（int*）malloc（sizeof（int）*width）;
path=（char***）malloc（sizeof（char**）*height）;
path[i]=（char**）malloc（sizeof（char*）*width）;
for（j=0;
j<
width;
j++）
path[i][j]=（char*）malloc（sizeof（char）*height*width）;
path[i][j][0]='
\0'
}
record=（int*）malloc（sizeof（int）*height*width）;
/**********************随机生成迷宫，并显示**********************/
srand（（unsigned）time（NULL））;
//设置随机数种子。
maze[i][j]=rand（）%3;
//0表示障碍，非0表示可通过，通路:
障碍=2:
1。
maze[i][j]=（maze[i][j]）?
7:
0;
//障碍物与通路的图标。
toBeChoosed[i][j]=maze[i][j];
weight[i][j]=MAX_W;
maze[START_X-1][START_Y-1]=8;
//起点图标。
toBeChoosed[START_X-1][START_Y-1]=maze[START_X-1][START_Y-1];
maze[END_X-1][END_Y-1]=9;
//终点图标。
toBeChoosed[END_X-1][END_Y-1]=maze[END_X-1][END_Y-1];
%s"
ico[maze[i][j]]）;
//输出原始迷宫。
\n"
Pressanykeytocontinue..\n"
getch（）;
/**********************搜索路径**********************/
count=0;
bestPoint=ConvertToIndex（START_X-1,START_Y-1）;
//起点设为最佳节点。
weight[START_X-1][START_Y-1]=0;
//起点权值为0。
do
ConvertToXY（bestPoint,&
x1,&
y1）;
toBeChoosed[x1][y1]=0;
record[count]=bestPoint;
//将最佳节点记录下来。
count++;
4;
i++）//更新最佳节点周围4个点的权值大小。
GetDxDy（i,&
dx,&
dy）;
x=x1+dx;
y=y1+dy;
if（IsInMaze（x,y）&
toBeChoosed[x][y]）//如果是合法的点，而且是待选择的点。
if（weight[x][y]>
weight[x1][y1]+1）//权值变小。
weight[x][y]=weight[x1][y1]+1;
//更新权值。
strcpy（path[x][y],path[x1][y1]）;
//更新路径。
path[x][y][strlen（path[x1][y1]）]=i+48;
//添加路径。
path[x][y][strlen（path[x1][y1]）+1]='
if（bestPoint==ConvertToIndex（END_X-1,END_Y-1））//如果到出口就退出。
bestPoint=-1;
bestWeight=MAX_W;
count;
i++）//在所有最佳节点的周围选择一个新的最佳节点。
index=record[i];
ConvertToXY（index,&
GetDxDy（j,&
toBeChoosed[x][y]）
index=ConvertToIndex（x,y）;
if（（weight[x][y]<
bestWeight）||（weight[x][y]==bestWeight&
bestValue>
Abs（x-END_X）+Abs（y-END_Y）））
bestPoint=index;
bestWeight=weight[x][y];
bestValue=Abs（x-END_X）+Abs（y-END_Y）;
}while（bestPoint!
=-1）;
//如果不存在可选的点，说明不通路。
/**********************输出结果**********************/
if（path[END_X-1][END_Y-1][0]!
='
）
x=START_X-1;
y=START_Y-1;
x1=END_X-1;
y1=END_Y-1;
（signed）strlen（path[x1][y1]）-1;
GetDxDy（path[x1][y1][i]-48,&
x+=dx;
y+=dy;
//为相应的通路设置图标。
maze[x][y]=icoIndex[path[x1][y1][i]-48][path[x1][y1][i+1]-48];
Theshortestpathexists..\n"
//输出带路径的迷宫图。
else
Noavailablepathexists..\n"
/**********************释放空间**********************/
free（maze[i]）;
free（maze）;
free（path[i][j]）;
free（path[i]）;
free（path）;
free（weight）;
free（record）;
/**********************是否继续**********************/
TryAgain?
（Y/N）"
again=getch（）;
while（（again!
）&
（again!
n'
））
\nTryAgain?
程序实现及测试：
不足之处：
1、对于大规模数据无法求解。
比如Height=10000，Width=10000。
2、寻径效率有待改进。
设计体会：
通过此次课程设计，我学会了很多东西。
对程序设计有了进一步的理解。
结束语：
本程序是用C语言编写的控制台应用程序，可以实现以下功能：
参考文献：
【1】严蔚敏吴伟民编著《数据结构》清华大学出版社2001年1月
【2】谭浩强著《C程序设计（第三版）》清华大学出版社2005年7月
【3】陈平褚华主编《软件设计师教程》清华大学出版社2004年7月
本科生课程设计成绩评定表
班级：
姓名李志斌 学号：
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
6
设计验收
总得分/等级
评语：
注：
最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
2010年7月9日
升级会员 