七彩迷宮實驗報告

PAGE 本科學(xué)生設(shè)計性實驗報告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計項目組長學(xué)號專業(yè)軟件工程班級軟件125班成員實驗項目名稱七彩迷宮指導(dǎo)教師涂保東開課學(xué)期2013至2014學(xué)年第二學(xué)期實驗設(shè)計方案實驗名稱：七彩迷宮實驗時間：3月24號至4月14號實驗場地：W202軟件環(huán)境：Java實驗任務(wù)與目的（簡單介紹實驗內(nèi)容，說明實驗任務(wù)和目的）1.1性能需求隨著社會經(jīng)濟和人們物質(zhì)生活的不斷提高，人們對精神生活的需求也越來越高，在現(xiàn)今社會里，人們對諸如智商、情商等的重視無疑反映了對精神生活的態(tài)度。當(dāng)然具體到我們每個人來說，想必大多數(shù)人小時候都曾玩過魔方、迷宮吧。作為這種智力游戲，人們是百玩不厭的。正是鑒于這種需求，本設(shè)計應(yīng)用計算機語言及其算法，將人的意志賦予機器實現(xiàn)，使人們不必再陷于枯燥的重復(fù)勞動，從而將更多的精力投入到對未知領(lǐng)域的探索上。1.2功能需求本設(shè)計的關(guān)鍵在于將人的想法自能化，由所編軟件自動的搜索可行路徑。因此，軟件必須擁有自動搜索并記錄可行路徑的功能，除此之外，軟件需要有自動生成迷宮的功能；當(dāng)然對于迷宮問題還有很多要考慮的地方，比如由用戶自己來探索可行路徑，但由于本設(shè)計側(cè)重于迷宮求解的算法設(shè)計，并非以游戲的形式為初衷，定有不全之處。1.3實驗內(nèi)容隨機生成一個可以出去的迷宮，老鼠的入口在左上頂點，出口在右下頂點。老鼠走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、北、南、西的方向順序試探下一個位置；如果某方向可以通過，則前進一步，在新的位置上繼續(xù)進行搜索，直到走出迷宮。1.4實驗任務(wù)自動生成一個n*n的二維數(shù)組，作為迷宮，并顯示生成迷宮耗時；保證迷宮是否存在一條從入口到出口的通路（用深度優(yōu)先搜索方法實現(xiàn)）。如果通路不存在，就重新生成一個迷宮，直到通路存在為止；在迷宮內(nèi)部的每一格都有四個方向可以走。如果某格的三個方向都走不通，則返回上一格（回溯），選取另一個能走通的方向進行移動；顯示老鼠走出迷宮所用時間。1.5實驗?zāi)康氖炀氄莆针S機生成的方法。熟練掌握J(rèn)ava面向?qū)ο蟪绦蛟O(shè)計的方法，以及類模板的應(yīng)用。用深度優(yōu)先搜索算法生成一個有通路的迷宮。1算法背景1：深度優(yōu)先搜索算法：是搜索算法的一種，是沿著樹的深度遍歷的節(jié)點，盡可能深的搜索樹的分支，當(dāng)節(jié)點V的所有邊都已經(jīng)被探尋過，搜索講回溯到發(fā)現(xiàn)節(jié)點v的那條邊的起始節(jié)點，這一過程一直進行到已發(fā)現(xiàn)從源節(jié)點可到達的所有節(jié)點為止，如果還存在為發(fā)現(xiàn)的節(jié)點，則選擇其他一個作為源節(jié)點并重復(fù)以上過程，整個過程反復(fù)進行止到所有節(jié)點都被訪問為止。2：回溯法生成迷宮算法：1.以一個M*N的長方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通過的結(jié)論2.根據(jù)二位數(shù)組，輸出迷宮的圖形。3.探索迷宮的四個方向：RIGHT為向右，DOWN為向下，LEFT向左，UP為上，輸出從入口到出口的行走路徑。3：調(diào)用java中的time類：直接調(diào)用time()函數(shù)，計算實現(xiàn)通路的時間。4：棧：棧是一種可以實現(xiàn)“先進后出”的存儲結(jié)構(gòu)。是一種特殊的線性表，而其特殊性在于限定插入和刪除數(shù)據(jù)元素只能在線性表的一端進行。用回溯方法解決問題的一般步驟：1針對所給問題，定義問題的解空間，它至少包含問題的一個（最優(yōu)）解。2確定易于搜索的解空間結(jié)構(gòu),使得能用回溯法方便地搜索整個解空間。3以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。問題的解空間通常是在搜索問題解的過程中動態(tài)產(chǎn)生的，這是回溯算法的一個重要特性。確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根結(jié)點）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點時為止。實驗思路（詳細(xì)描述解決問題的整體思路、涉及的算法思想及數(shù)據(jù)結(jié)構(gòu)等）首先隨機生成迷宮，設(shè)計好模板。進入迷宮，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換一個方向再繼續(xù)探索，直到所有肯呢過的通路都探索到為止。采用的是回溯算法找到出口因為沒有實現(xiàn)吃豆子的功能，我們的實驗結(jié)果沒有七彩豆子，能力有限，還請見諒。二、實驗結(jié)果與分析1、程序結(jié)構(gòu)（程序結(jié)構(gòu)圖，主要函數(shù)的功能描述，算法實現(xiàn)的細(xì)節(jié)等）1．程序流程圖：2：程序主要代碼：privateJPanelpanel;privateJPanelsouthPanel;privateJPanelcenterPanel;privateMazeGridgrid[][];privateJButtonrestart;privateJButtondostart;privateintrows;//rows和cols目前暫定只能是奇數(shù)privateintcols;privateList<String>willVisit;privateList<String>visited;privateLinkedList<String>comed;privatelongstartTime;privatelongendTime;//生成迷宮publicMazeGrid[][]createMap(MazeGridmazeGrid[][],intx,inty){intvisitX=0;intvisitY=0;if(x-2>=0){if(!mazeGrid[x-2][y].isVisited()){willVisit.add((x-2)+"#"+y);}}if(x+2<cols){if(!mazeGrid[x+2][y].isVisited()){willVisit.add((x+2)+"#"+y);}}if(y-2>=0){if(!mazeGrid[x][y-2].isVisited()){willVisit.add(x+"#"+(y-2));}}if(y+2<rows){if(!mazeGrid[x][y+2].isVisited()){willVisit.add(x+"#"+(y+2));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[(visitX+x)/2][(visitY+y)/2].setMark(true);mazeGrid[visitX][visitY].setVisited(true);if(!visited.contains(id)){//將這個點加到已訪問中去visited.add(id);}willVisit.clear();createMap(mazeGrid,visitX,visitY);}else{if(!visited.isEmpty()){Stringid=visited.remove(visited.size()-1);//取出最后一個元素visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[visitX][visitY].setVisited(true);createMap(mazeGrid,visitX,visitY);}}returnmazeGrid;}//走迷宮publicStringgoMaze(MazeGridmazeGrid[][],intx,inty){intcomeX=0;intcomeY=0;//leftif(x-1>=0){if(mazeGrid[x-1][y].isMark()){if(!comed.contains((x-1)+"#"+y))willVisit.add((x-1)+"#"+y);}}//rightif(x+1<cols){if(mazeGrid[x+1][y].isMark()){if(!comed.contains((x+1)+"#"+y))willVisit.add((x+1)+"#"+y);}}//upif(y-1>=0){if(mazeGrid[x][y-1].isMark()){if(!comed.contains(x+"#"+(y-1)))willVisit.add(x+"#"+(y-1));}}//downif(y+1<rows){if(mazeGrid[x][y+1].isMark()){if(!comed.contains(x+"#"+(y+1)))willVisit.add(x+"#"+(y+1));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();willVisit.clear();comed.add(x+"#"+y);}else{if(!comed.isEmpty()){Stringid=comed.removeLast();comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();comed.addFirst(x+"#"+y);}}returncomeX+"#"+comeY;}——————————————————————————————————————測試設(shè)計與數(shù)據(jù)（設(shè)計充足合理的測試用例，說明測試策略）1.迷宮的初始狀態(tài)：迷宮你尚未添加任何東西。2.在迷宮的墻還沒隨機生成時的狀態(tài)：這時的迷宮已經(jīng)基本有了一個雛形，接下來就是隨機的將墻刪去，改為路。迷宮生成的最后狀態(tài)。在迷宮的生成中需要滿足每一行至少有一個通路，每一列中也要有一個通路?！獙嶒灛F(xiàn)象及結(jié)果（應(yīng)用文字和程序運行的截圖說明測試現(xiàn)象，并解釋結(jié)果）點擊生成迷宮可以隨機生成一個新迷宮。點擊開始，老鼠開始走迷宮。在走完迷宮后會提示所花費的時間?！獙嶒灧治雠c探討（對測試現(xiàn)象和觀察結(jié)果進行分析，探討算法，提出見解）對于老鼠走迷宮來看，走迷宮的方法很笨，即使在終點前有一個叉路口，有時它也不會走向終點，所以本方法不是最有方法，對于最短的路徑不會有判斷。這也就是本次使用的算法的不足的地方，回溯法無法最好的找出最短路徑?！獙嶒灲Y(jié)論（算法設(shè)計是否得到實現(xiàn)，測試結(jié)果表明程序是否成功解決問題等）在老鼠走迷宮程序中，迷宮的生成使用的是回溯法，走迷宮也使用的回溯法，程序可以運行，但是程序中沒有魔法豆，無法實現(xiàn)穿墻?！?、實驗總結(jié)（成敗得失，實驗關(guān)鍵，算法改進，程序改善，自我評價）在這次實驗中，我們還有沒有完善的地方，有些要求還沒有達到，但是也做的還不錯。只差一個吃魔法豆穿墻的要求沒有達到。本次實驗指導(dǎo)老師評語：小組成員共同努力，完成了大部分實驗的要求，鍛煉了實際操作的能力，有了一定的進步。驗報告格式正確，文檔規(guī)范，描述清楚，風(fēng)格統(tǒng)一。通過試驗鞏固了所學(xué)的知識，能夠?qū)⒁恍┧惴`活運用，有一定的進步。但程序還是略有不足，希望能好好改進。爭取達到實驗的所有要求，并加以拓展。得分：簽名：年月日importjava.awt.Canvas;importjava.awt.Color;importjava.awt.Graphics;publicclassMazeGridextendsCanvas{privatebooleanmark;//標(biāo)記是否是通路，TRUE為通路，F(xiàn)ALSE為不通privatebooleanisVisited;//標(biāo)記是否是訪問過的,這是在生成迷宮的時候判斷的。privatebooleanisPersonCome;//標(biāo)記是否已經(jīng)走過privatebooleanisStart;//判斷是否為入口privatebooleanisEnd;//判斷是否為出口publicMazeGrid(){this.setBackground(newColor(112,128,144));this.setSize(25,25);}publicMazeGrid(booleanmark,intwidth,intheight){ this.mark=mark;this.setSize(width,height);if(mark==true){this.setBackground(newColor(255,255,255));}else{this.setBackground(newColor(112,128,144));}}publicbooleanisMark(){returnmark;}publicvoidsetMark(booleanmark){this.mark=mark;}publicvoidpaint(Graphicsg){ Colorc[]={Color.RED,Color.blue,Color.GRAY};if(this.mark){if(this.isStart||this.isEnd){this.setBackground(newColor(218,112,214));//入口出口顏色}elsethis.setBackground(newColor(255,255,255));//路的顏色}else{this.setBackground(c[(int)(Math.random()*3)]);//墻的顏色}if(this.isPersonCome){g.setColor(Color.ORANGE);//老鼠顏色g.fillOval(2,2,40,40);//位置大小}}publicbooleanisVisited(){returnisVisited;}publicvoidsetVisited(booleanisVisited){this.isVisited=isVisited;}publicbooleanisPersonCome(){returnisPersonCome;}publicvoidsetPersonCome(booleanisPersonCome){this.isPersonCome=isPersonCome;}publicbooleanisStart(){returnisStart;}publicvoidsetStart(booleanisStart){this.isStart=isStart;}publicbooleanisEnd(){returnisEnd;}publicvoidsetEnd(booleanisEnd){this.isEnd=isEnd;}}importjava.awt.BorderLayout;importjava.awt.Color;importjava.awt.GridLayout;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.TimerTask;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JOptionPane;importjavax.swing.JPanel;//迷宮publicclassMazeextendsJFrameimplementsActionListener{privateJPanelpanel;privateJPanelsouthPanel;privateJPanelcenterPanel;privateMazeGridgrid[][];privateJButtonrestart;privateJButtondostart;privateintrows;//rows和cols目前暫定只能是奇數(shù)privateintcols;privateList<String>willVisit;privateList<String>visited;privateLinkedList<String>comed;privatelongstartTime;privatelongendTime;publicMaze(){ rows=15;cols=15;willVisit=newArrayList<String>();visited=newArrayList<String>();comed=newLinkedList<String>();init();this.setTitle("老鼠走迷宮");this.add(panel);this.pack();this.setVisible(true);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);}publicvoidinit(){panel=newJPanel();southPanel=newJPanel();centerPanel=newJPanel();panel.setLayout(newBorderLayout());grid=newMazeGrid[rows][cols];restart=newJButton("生成迷宮");dostart=newJButton("開始");centerPanel.setLayout(newGridLayout(rows,cols,1,1));//邊框粗細(xì)centerPanel.setBackground(newColor(0,0,0));//邊框顏色southPanel.add(restart);southPanel.add(dostart);dostart.addActionListener(this);restart.addActionListener(this);for(inti=0;i<grid.length;i++)for(intj=0;j<grid[i].length;j++){if(j%2==0&&i%2==0)grid[i][j]=newMazeGrid(true,40,40);//true為路elsegrid[i][j]=newMazeGrid(false,40,40);//false為墻}grid[0][0].setVisited(true);grid[0][0].setPersonCome(true);grid[0][0].setStart(true);visited.add("0#0");grid[rows-1][cols-1].setEnd(true);//出口grid=createMap(grid,0,0);for(inti=0;i<grid.length;i++)for(intj=0;j<grid[i].length;j++){grid[i][j].repaint();//重繪centerPanel.add(grid[i][j]);}panel.add(southPanel,BorderLayout.SOUTH);panel.add(centerPanel,BorderLayout.CENTER);}//生成迷宮publicMazeGrid[][]createMap(MazeGridmazeGrid[][],intx,inty){intvisitX=0;intvisitY=0;if(x-2>=0){if(!mazeGrid[x-2][y].isVisited()){willVisit.add((x-2)+"#"+y);}}if(x+2<cols){if(!mazeGrid[x+2][y].isVisited()){willVisit.add((x+2)+"#"+y);}}if(y-2>=0){if(!mazeGrid[x][y-2].isVisited()){willVisit.add(x+"#"+(y-2));}}if(y+2<rows){if(!mazeGrid[x][y+2].isVisited()){willVisit.add(x+"#"+(y+2));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[(visitX+x)/2][(visitY+y)/2].setMark(true);mazeGrid[visitX][visitY].setVisited(true);if(!visited.contains(id)){//將這個點加到已訪問中去visited.add(id);}willVisit.clear();createMap(mazeGrid,visitX,visitY);}else{if(!visited.isEmpty()){Stringid=visited.remove(visited.size()-1);//取出最后一個元素visitX=Integer.parseInt(id.split("#")[0]);visitY=Integer.parseInt(id.split("#")[1]);mazeGrid[visitX][visitY].setVisited(true);createMap(mazeGrid,visitX,visitY);}}returnmazeGrid;}//走迷宮publicStringgoMaze(MazeGridmazeGrid[][],intx,inty){intcomeX=0;intcomeY=0;//rightif(x+1<cols){if(mazeGrid[x+1][y].isMark()){if(!comed.contains((x+1)+"#"+y))willVisit.add((x+1)+"#"+y);}}//downif(y+1<rows){if(mazeGrid[x][y+1].isMark()){if(!comed.contains(x+"#"+(y+1)))willVisit.add(x+"#"+(y+1));}}//leftif(x-1>=0){if(mazeGrid[x-1][y].isMark()){if(!comed.contains((x-1)+"#"+y))willVisit.add((x-1)+"#"+y);}}//upif(y-1>=0){if(mazeGrid[x][y-1].isMark()){if(!comed.contains(x+"#"+(y-1)))willVisit.add(x+"#"+(y-1));}}if(!willVisit.isEmpty()){intvisit=(int)(Math.random()*willVisit.size());Stringid=willVisit.get(visit);comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();willVisit.clear();comed.add(x+"#"+y);}else{if(!comed.isEmpty()){Stringid=comed.removeLast();comeX=Integer.parseInt(id.split("#")[0]);comeY=Integer.parseInt(id.split("#")[1]);mazeGrid[x][y].setPersonCome(false);mazeGrid[comeX][comeY].setPersonCome(true);mazeGrid[x][y].repaint();mazeGrid[comeX][comeY].repaint();comed.addFirst(x+"#"+y);}}returncomeX+"#"+comeY;}intcomeX=0;intcomeY=0;publicvoidactionPerformed(ActionEvente){if(e