迷宫问题实验报告.doc

数据结构课程设计报告姓名徐健学号540905052009 级5班组实验室：提交日期8.23成绩指导教师实验题目：迷宫问题以一个MN的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（1） 根据二维数组，输出迷宫的图形。（2） 探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。问题解析（对问题的分析、理解和解题方法）：迷宫问题是一类很经典的问题,可以通过深度优先和广度优先进行搜索,广度优先速度更快,处理节点更少,而广度优先中的A*算法更是加入成本判断使得搜索速度更快,而且得到的解往往很接近最优解.A*算法也是游戏中寻路的主要算法.由于的A*算法的诸多优势,我选择它作为这次课程的算法.数据结构选择、算法设计：( 1 ) 数据结构:1. 迷宫采用二维数组存储,里面的元素用1和0分别表示能通过和不能通过.2. 迷宫节点单独用类表示,类中含有坐标( i , j ),总成本( c ),实际成本( s ),估计成本( h ),父节点( parent ). 3. 已访问节点表和待访问节点表采用线性表储存( java的List容器,内部为封装过的数组 ).( 2 ) 算法:1. 初始化数据2. 进入主循环:while(没到达终点) if(相邻节点能通过 and 当前节点不在已访问节点表中 and 当前节点不在待访问节点表中 )将节点加入待访问节点表中,并计算成本; if(待访问节点表为空)表示已经没有路径,搜索失败,退出; 在待访问节点表中找到总成本最小的节点并设置为当前节点;当前节点加入到已访问节点表中,表示已经访问过.;重复循环步骤;3. 构建路径4. 输出任务分工及进度计划： 本次设计由本人一人完成,8月23日上午完成主要数据结构的设计和整体框架.下午完成具体算法的实现和用户界面的编写.用户手册 本软件采用全程可视化操作,界面简单易懂.1. 界面说明:左侧为地图编辑界面,通过鼠标点击改变地图或起始点终止点.右侧为控制区域,可以改变地图大小,查找路径,选择编辑地图或起始点终止点.测试结果 测试数据 测试结果程序清单 UI部分:UI.java public class UI extends JPanelprivate int mat;private List path;private final Astar a;/ 窗口控件private final JButton cSize = new JButton(改变大小);private final JTextField jt2 = new JTextField(10, 10);private final JTextField jt1 = new JTextField(10, 10);private final JButton jb = new JButton(查找路径);private final JLabel edit = new JLabel();private final JRadioButton RMatrix = new JRadioButton(编辑地图);private final JRadioButton RStart = new JRadioButton(设置起始点);private final JRadioButton REnd = new JRadioButton(设置终止点);private final ButtonGroup bg = new ButtonGroup();/ 控制图像int cellW = 600;int cellH = 600;int highX;int highY;private boolean show = false;private boolean isHigh = false;private byte setMode = 0;private static final byte Matrix = 0;private static final byte START = 1;private static final byte END = 2;public UI(int mat)protected void paintComponent(Graphics g) 算法部分:Astar.javapublic class Astarprivate List path = new ArrayList();private final List open = new ArrayList();private final List close = new ArrayList();private int mat;private Apoint curP;protected Apoint getStart()return start;protected Apoint getEnd()return end;protected void setStart(int i, int j)this.start = new Apoint(i, j);protected void setEnd(int i, int j)end = new Apoint(i, j);private Apoint start;private Apoint end;public class Apointpublic int i;public int j;private int s;private int h;private int c;private Apoint parent;public Apoint (int i, int j)this.i = i;this.j = j;public void score(int preS)this.h = Math.abs(end.i - i) + Math.abs(end.j - j);this.s = preS + 1;this.c = h + s;public int getS()return s;public int getC()return c;public Apoint getLeft()return new Apoint(i, j - 1);public Apoint getRight()return new Apoint(i, j + 1);public Apoint getUp()return new Apoint(i - 1, j);public Apoint getDown()return new Apoint(i + 1, j);public boolean equals(Apoint p)return (p.i = this.i & p.j = this.j);public Astar (int mat)this.mat = mat;start = new Apoint(0, 0);end = new Apoint(mat.length - 1, mat0.length - 1);curP = start;public void setMatrix(int mat)start.i = Math.min(mat.length - 1, start.i);start.j = Math.min(mat0.length - 1, start.j);end.i = Math.min(mat.length - 1, end.i);end.j = Math.min(mat0.length - 1, end.j);this.mat = mat;path.clear();curP = start;private boolean test(Apoint p)tryif (matp.ip.j = 1)return false;catch (Exception e)return false;for (int i = 0; i close.size(); i+)if (p.equals(close.get(i)return false;for (int i = 0; i open.size(); i+)if (p.equals(open.get(i)return false;return true;public List getPath()return path;public boolean findPath()open.clear();close.clear();path.clear();open.add(curP);while (!(curP.equals(end)Apoint p;if (test(curP.getLeft()p = curP.getLeft();p.score(curP.getS();p.parent = curP;open.add(p);if (test(curP.getDown()p = curP.getDown();p.score(curP.getS();p.parent = curP;open.add(p);if (test(curP.getUp()p = curP.getUp();p.score(curP.getS();p.parent = curP;open.add(p);if (test(curP.getRight()p = curP.getRight();p.score(curP.getS();p.parent = curP;open.add(p);close.add(curP);if (open.isEmpty()return false;int min = min(open);curP = open.get(min);open.remove(min);buildPath();return true;private void buildPath()path = new ArrayList();while (!(curP.parent = null)path.add(curP);curP = curP.parent;path.add(start);private int min(List p)int min = Integer.MAX_VALUE;