數(shù)據(jù)結(jié)構(gòu)課程設(shè)計java求解迷宮-回溯法-A算法

算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課題：求解迷宮通路的圖形界面演示程序作者：吳昊QQ：328035823目錄1.題目及需求分析········································42.概要設(shè)計··············································43.詳細設(shè)計·············································104.調(diào)試分析·············································395.課程設(shè)計總結(jié)·········································421．題目及需求分析1.1題目編制一個求解迷宮通路的圖形界面演示程序。1.2需求分析輸入一個任意大小的迷宮，任設(shè)起點、終點、障礙，用棧求出一條走出迷宮的路徑，并顯示在屏幕上；根據(jù)用戶界面提示，用鍵盤輸入，Home鍵設(shè)置迷宮起點，End鍵設(shè)終點，上下左右箭頭鍵移動，Enter鍵添加墻，Del鍵刪除墻，完成后按F9鍵演示，演示完畢后可F5刷新題圖，重新對地圖的起點、終點、障礙進行設(shè)置，Esc鍵退出；本程序要求至少得出一條成功的通路，也可求得全部路徑。此外，也可嘗試保存或載入測試文件（此功能不做強行要求）。當未輸入起點時，消息顯示“Error：YoumustsettheSTART.”；未輸入終點時，顯示“Error：YoumustsettheEND.”；找到路徑時，屏幕顯示足跡，并在消息框出現(xiàn)Pathfound，否則消去足跡，顯示Pathnotfound。用戶可以通過界面上提供的菜單選項，選擇“幫助”查看操作說明。（算法選優(yōu)）用戶可以通過界面上提供的菜單選項，選擇“A*算法求最短路徑”演示求解迷宮最短路徑。2.概要設(shè)計根據(jù)需求分析的用戶界面的設(shè)計要求，考慮到我們在Java課程中學習過GUI設(shè)計，對Java的GUI的比較熟悉，所以我們用Java語言來開發(fā)本項目。在設(shè)計求解迷宮的程序時，要求編寫8個Java源文件：Dialog.java、Maze.java、MazeGUI.java、Position.java、Rollback.java、stack.java、Astar.java和Aposition.java。該程序除了上述6個Java源文件所給出的類以外，還需呀Java系統(tǒng)提供的一些重要的類，如java.awt包中的容器類、畫圖類、事件類及監(jiān)聽器接口、javax.swing包中的各種輕量組件類和java.lang包中線程類等。2.1UML類圖程序的所用到的一些重要的類以及之間的關(guān)聯(lián)關(guān)系如圖2-1所示。圖2-1UML類圖2.2Dialog.java(主類)Dialog.java(主類)是JDialog類的一個子類。該類負責創(chuàng)建提示用戶輸入迷宮大小的對話框，通過用戶輸入的參數(shù)來確定所要創(chuàng)建的迷宮圖形界面的窗口的大小。該類含有main方法，程序從該類開始執(zhí)行。Begin類的成員變量有JTextField、JButton、JFrame。Begin類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.3Maze.javaMaze類創(chuàng)建的對象是MazeGUI類和Rollback類最重要的成員之一，代表迷宮。該類負責接收在迷宮窗口所設(shè)置起點、終點、障礙的位置參數(shù)來繪制迷宮圖像并存儲迷宮結(jié)構(gòu)的信息。該類的主要成員變量有3種類型的對象：Position、Image以及存放整型數(shù)的二維數(shù)組。Maze類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.4MazeGUI.javaMazeGUI類是Frame類的一個子類，創(chuàng)建的對象是Rollback類最重要的成員之一。該類負責創(chuàng)建迷宮圖形窗口界面，方便用戶在界面上設(shè)置起點、終點、障礙等并展現(xiàn)求解迷宮的過程。該類的主要成員變量有4種類型的對象：Maze、Rollback、Position和Thread。該類還包含一個內(nèi)部類SolveThread，該內(nèi)部類實現(xiàn)了runnable接口。MazeGUI類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.5Position.java（圖形界面坐標的存儲結(jié)構(gòu)） Position類創(chuàng)建的對象是Maze類、MazeGUI類和Rollback類最重要的成員之一。該類負責在Maze類、MazeGUI類和Rollback類之間傳遞消息，其對象存有當前位置的坐標信息。該類包含兩個整型的成員變量x和y，記錄當前位置在迷宮圖形界面的橫、縱坐標。Position類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.6Stack.java（數(shù)據(jù)類型結(jié)構(gòu)）為了體現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)的課程特點，我們并沒有用Java系統(tǒng)類庫中java.Util.Stack類，而是編寫了一個通用的Stack存儲結(jié)構(gòu)。Stack類創(chuàng)建的對象是Rollback類的最重要的成員之一。該類負責保存在求解迷宮過程中所走過的路徑信息。該類包含一個內(nèi)部類Node，定義了棧中存儲的節(jié)點元素的類型。另外還含有一個整型成員變量n和一個Node類型的成員變量top，分別記錄棧中元素的個數(shù)以及棧頂元素的信息。而Node類定義的是棧中節(jié)點的類型，包含當前節(jié)點的信息info（Object類型）和以及棧中下一個元素的引用next（相當在C語言中的指針）。Stack類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.7Rollback.java（核心算法—回溯算法）Rollback類創(chuàng)建的對象是是MazeGUI類最重要的成員之一。該類負責根據(jù)Maze類中的迷宮數(shù)組的信息采用回溯算法，控制并繪制人物在迷宮圖形界面窗口中的位置。該類的主要成員變量有4種類型的對象：Maze、MazeGUI、Position和Stack。Rollback類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.8Astar.java（核心算法—A*算法）Astar類創(chuàng)建的對象是是MazeGUI類最重要的成員之一。該類負責根據(jù)Maze類中的迷宮數(shù)組的信息采用A*算法，找到起點到終點的最短路徑并打印出來。該類的主要成員變量有4種類型的對象：Maze、APosition、Stack和LinkedList。Astar類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.9Aposition（A*算法的存儲結(jié)構(gòu)）Aposition類是Position類的派生類，APosition類創(chuàng)建的對象是Astar類、MazeGUI類和Rollback類最重要的成員之一。該類負責在Astar類、MazeGUI類和Rollback類之間傳遞消息，其對象存有當前位置的坐標信息、A*算法的評估函數(shù)值、開關(guān)標記和父節(jié)點等。APosition類的主要成員和成員方法的作用將在后面的詳細設(shè)計中闡述。2.9事件跟蹤圖2.9.1用戶啟動迷宮圖形界面圖2-2用戶啟動迷宮圖形界面2.9.2用戶設(shè)置迷宮參數(shù)圖2-3用戶設(shè)置迷宮參數(shù)2.9.3回溯法求解迷宮圖2-4回溯法求解迷宮3.詳細設(shè)計3.1工程文件視圖3.2Dialog.java(主類)3.2.1效果圖Dialog創(chuàng)建的對話框效果如圖1所示。圖1Dialog創(chuàng)建的對話框?qū)ο?.2.2UML圖Dialog類是javax.swing包中JDialog的一個子類，標明該類的主要成員變量和方法的UML圖如圖2所示。圖2Dialog類的UMl圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。成員變量tf1、tf2是JTextField類創(chuàng)建的文本框。用來接收用戶輸入的設(shè)置迷宮的大小參數(shù)，即行和列的數(shù)目。當用戶沒有輸入時，tf1、tf2的默認文本內(nèi)容為10。b是JButton類創(chuàng)建的按鈕，名字為“生成迷宮”。b被放置在對話框的右下角。b還為自己注冊了ActionEvent的事件監(jiān)聽器。當點擊按鈕時，根據(jù)tf1、tf2的文本內(nèi)容創(chuàng)建一個MazeGUI的對象，生成迷宮圖形界面窗口。2）成員方法Dialog()是構(gòu)造方法，負責完成對話框的初始化操作。初始化操作包括：將內(nèi)容為"列數(shù)："的JLabel對象、內(nèi)容為"列數(shù)："的JLabel對象、tf1、tf2、b添加到對話框中，并設(shè)置對話框的布局，設(shè)置背景顏色，設(shè)置對話框的標題為“課程設(shè)計--求解迷宮”。另外還為對話框注冊了WindowEvent的事件監(jiān)聽器。main(Stringsrgd[])方法是程序運行的入口方法。3.2.3代碼（Dialog.java）packagemaze;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;/***啟動窗口**/@SuppressWarnings("serial")publicclassDialogextendsJDialog{ privateJTextFieldtf1=newJTextField("10",10); privateJTextFieldtf2=newJTextField("10",10); privateJButtonb=newJButton("生成迷宮"); publicstaticvoidmain(Stringsrgd[]){ try{ Thread.sleep(300); }catch(Exceptione){ e.printStackTrace(); } newDialog(); } publicDialog(){ setTitle("課程設(shè)計--求解迷宮"); setLayout(newBorderLayout()); JPanelp=newJPanel(newGridLayout(4,1)); FlowLayoutflowLayout=newFlowLayout(); flowLayout.setAlignment(FlowLayout.LEFT); flowLayout.setHgap(10); FlowLayoutflowLayout1=newFlowLayout(); flowLayout1.setAlignment(FlowLayout.RIGHT); JPanelp1=newJPanel(flowLayout); JPanelp2=newJPanel(flowLayout); JPanelp3=newJPanel(); JPanelp4=newJPanel(); JPanelp5=newJPanel(flowLayout1); p1.add(newJLabel("行數(shù)：")); p1.add(tf1); p2.add(newJLabel("列數(shù)：")); p2.add(tf2); p1.setBackground(newColor(226,244,255)); p2.setBackground(newColor(226,244,255)); p3.setBackground(newColor(226,244,255)); p4.setBackground(newColor(226,244,255)); p.add(p3); p.add(p1); p.add(p2); p.add(p4); p5.add(b); p5.setBackground(newColor(196,227,248)); add(newJLabel(newImageIcon("maze.jpg")),BorderLayout.NORTH); add(p,BorderLayout.CENTER); add(p5,BorderLayout.SOUTH); setSize(345,250); setLocation(400,100); setVisible(true); b.addActionListener(newActionListener(){ publicvoidactionPerformed(ActionEvente){ newMazeGUI(Integer.parseInt(tf1.getText()),Integer.parseInt(tf2.getText())); setVisible(false); } }); addWindowListener(newWindowAdapter(){ publicvoidwindowClosing(WindowEvente){ System.exit(0); } }); }}3.3Maze.java3.3.1效果圖Maze類繪制的墻、通路、路徑、起點和終點的效果圖如圖3所示。圖3墻、通路、路徑、起點和終點3.3.2UML圖Maze類創(chuàng)建的對象是MazeGUI類和Rollback類最重要的成員之一，代表迷宮。標明Maze類的主要成員變量、成員方法的UMl圖如圖4所示。圖4Maze類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。成員變量mazeMap是int類型的二維數(shù)組，數(shù)組的元素的值表示迷宮對應(yīng)位置的內(nèi)容。若元素的值為0表示迷宮對應(yīng)位置可通過，即為通路；若元素的值為1表示迷宮對應(yīng)位置為墻；若元素的值為2表示迷宮對應(yīng)位置為已經(jīng)走過的足跡；若元素的值為3，表示迷宮對應(yīng)位置是從棧中彈出的點，并且不能再次通過；若元素的值為4，表示迷宮對應(yīng)位置為起點，保證起點不可通過。begin和end是Position類創(chuàng)建的對象，其存儲了起點和終點在迷宮圖形界面上的坐標信息。drawPos是Position類創(chuàng)建的對象，在迷宮圖形界面上表現(xiàn)為一個方框，起到定位的作用，其存儲了在設(shè)置起點、終點、障礙在迷宮圖形界面的位置時當前的坐標信息。wallPic、roadPic、goPic、beginPic和endPic是Image類創(chuàng)建的對象，其內(nèi)容分別為墻、通路、路徑、起點和終點的圖片。row和col是int類型的變量，其值分別表示迷宮數(shù)組的行數(shù)和列數(shù)。成員方法Maze(introw,intcol)是Maze類的構(gòu)造方法，通過調(diào)用setMaze方法來創(chuàng)建maze對象，其參數(shù)row，col是從MazeGUI類中傳來的參數(shù)。setMaze(introw,intcol)方法，maze對象可調(diào)用該方法完成迷宮數(shù)組的初始化操作：創(chuàng)建指定行數(shù)和列數(shù)的迷宮數(shù)組，將迷宮圖形界面外圍位置對應(yīng)迷宮數(shù)組的元素的值設(shè)為1，將其余元素的值設(shè)為0。isPass(Positionp)方法，maze對象可調(diào)用該方法判斷傳入的參數(shù)p點周圍的四個方向是否能通過，并返回一個整型數(shù)。根據(jù)p點坐標，確定該點在迷宮數(shù)組中的元素位置，然后再根據(jù)該位置四個方向上相鄰位置元素的值判斷該p點周圍的四個方向是否能通過。若元素的值為0表示可以通過。對于返回值，若返回-1，表示p點四周沒有通路（包括從棧中彈出的點）；若返回0，表示p點東方向有通路；若返回1，表示p點南方向有通路；若返回2，表示p點西方向有通路；若返回3，表示p點北方向有通路。mark(Positionp,intm)方法，maze對象可調(diào)用該方法將傳入的參數(shù)p點在迷宮數(shù)組的對應(yīng)位置的元素設(shè)為m。draw(Graphicsg)方法，maze對象可調(diào)用該方法根據(jù)迷宮數(shù)組元素的值來繪制墻、通路、路徑圖像和用于在迷宮圖形界面定位的方框，此外該方法還根據(jù)begin和end中存儲的坐標信息來繪制對應(yīng)位置的起點和終點圖像。setBegin(intx,inty)和setEnd(intx,inty)方法，maze對象可調(diào)用該方法根據(jù)傳入的參數(shù)x，y來創(chuàng)建Position類的對象begin和end。3.3.3代碼（Maze.java）packagemaze;importjava.awt.*;importjavax.swing.*;/***迷宮參數(shù)**/publicclassMaze{ int[][]mazeMap;//地圖數(shù)據(jù) Positionbegin;//起始坐標 Positionend;//結(jié)束坐標 PositiondrawPos=newPosition(1,1); ImagewallPic=newImageIcon("wall.jpg").getImage(); ImageroadPic=newImageIcon("road.jpg").getImage(); Imagea=newImageIcon("a.jpg").getImage(); ImagegoPic=newImageIcon("go.jpg").getImage(); ImageendPic=newImageIcon("end.jpg").getImage(); ImagebeginPic=newImageIcon("begin.jpg").getImage(); introw=0,col=0; publicMaze(introw,intcol){ this.row=row; this.col=col; mazeMap=newint[row][col]; for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(i==0||j==0||j==col-1||i==row-1){//迷宮最外層設(shè)為墻 this.mazeMap[i][j]=1; }else{ this.mazeMap[i][j]=0; } } } } publicMaze(){ } publicvoidmark(Positionp,intm){//標記位置已走過 this.mazeMap[p.y][p.x]=m; } publicvoiddraw(Graphicsg){//繪制地圖圖片 for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(begin!=null&&i==begin.y&&j==begin.x){//起點 g.drawImage(beginPic,j*50,24+i*50,50,50,null); }elseif(end!=null&&i==end.y&&j==end.x){//終點 g.drawImage(endPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==1){//墻壁 g.drawImage(wallPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==2){//已走過的路徑 g.drawImage(goPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==3){//已走過的路徑，消除腳印 g.drawImage(roadPic,j*50,24+i*50,50,50,null); }elseif(this.mazeMap[i][j]==5){//A*方法路徑 g.drawImage(a,j*50,24+i*50,50,50,null); } else{//通道 g.drawImage(roadPic,j*50,24+i*50,50,50,null); } } } g.drawRect(drawPos.x*50,24+drawPos.y*50,50,50); } publicvoidresume(){//恢復(fù)迷宮 for(inti=0;i<row;i++){ for(intj=0;j<col;j++){ if(this.mazeMap[i][j]==2||this.mazeMap[i][j]==3){ this.mazeMap[i][j]=0; } } } } publicvoidsetEnd(intx,inty){ end=newPosition(x,y); } publicvoidsetBegin(intx,inty){ begin=newPosition(x,y); }}3．4MazeGUI.java3.4.1效果圖MazeGUI類創(chuàng)建的迷宮圖形界面窗口的效果圖如圖5所示。圖5MazeGUI類創(chuàng)建的迷宮圖形界面窗口的效果圖3.4.2UML圖MazeGUI類是Frame類的一個子類，創(chuàng)建的對象是Rollback類最重要的成員之一。該類負責創(chuàng)建迷宮圖形窗口界面，方便用戶在界面上設(shè)置起點、終點、障礙等并展現(xiàn)求解迷宮的過程。該類還包含兩個內(nèi)部類SolveThead、AThread，該內(nèi)部類實現(xiàn)了runnable接口。標明Maze類的主要成員變量、成員方法的UMl圖如圖6所示。圖6MazeGUI類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。成員變量obj是Object類型的對象，該對象用于充當線程問題中的同步鎖。row、col是int類型的變量，用來設(shè)置值迷宮圖形界面的大?。ú皇侵搁L度和寬度）。offScreen是Image類的對象，用于雙緩沖技術(shù)防止屏幕閃爍。maze是Maze類的對象。該對象是在MazeGUI類的構(gòu)造方法中根據(jù)row和col的值來創(chuàng)建的。rollback是Rollback類的對象，該對象負責求解迷宮，并繪制人物在迷宮圖形界面中的位置。t1、t2是Thread線程類的對象，該對象負責控制求解迷宮的線程，便于展現(xiàn)求解迷宮的過程。成員方法paint(Graphicsg)方法，該方法調(diào)用了maze對象的draw（Graphicsg）和rollback對象的draw（Graphicsg），分別繪制迷宮內(nèi)容圖像和人物圖像。update(Graphicsg)MazeGUI(introw,intcol)是MazeGUI類的構(gòu)造方法，負責完成創(chuàng)建迷宮圖形界面窗口的初始化操作。初始化操作包括：根據(jù)row和col創(chuàng)建maze對象，并根據(jù)創(chuàng)建的maze對象和MazeGUI自身的一個引用來創(chuàng)建rollback對象；為迷宮圖形窗口注冊KeyEvent的事件監(jiān)聽器；設(shè)置窗口的大小，以及窗口在屏幕上顯示的位置，設(shè)置菜單欄和菜單選項的內(nèi)容，放入窗口中，并為菜單選項注冊ActionEvent的事件監(jiān)聽器。threadSleep（）方法，在求解迷宮的過程結(jié)束時，MazeGUI類的對象可調(diào)用該方法暫停求解迷宮線程，使求解迷宮線程等待。具體來說是，求解迷宮線程擁有MazeGUI類的對象的監(jiān)視器，當對象調(diào)用該方法時，放棄對此監(jiān)視器的所有權(quán)并等待，直到其他線程通過調(diào)用notify方法，或notifyAll方法通知在此對象的監(jiān)視器上等待的線程醒來。然后該線程將等到重新獲得對監(jiān)視器的所有權(quán)后才能繼續(xù)執(zhí)行。keyTyped(KeyEvente)方法為KeyListener接口中的抽象方法，必須要實現(xiàn)，但在本程序中沒有實際用處，故在MazeGUI類中該方法為空方法；keyReleased(KeyEvente)方法為KeyListener接口中的抽象方法，必須要實現(xiàn)，但在本程序中沒有實際用處，故在MazeGUI類中該方法為空方法；keyPressed（KeyEvente）方法為KeyListener接口中的抽象方法，必須要實現(xiàn)。該方法的操作如下：當按下鍵盤上的按鍵時，將會調(diào)用repaint（）方法。根據(jù)所按下鍵的鍵值分成一下幾種情況：若按下鍵盤的Enter鍵，將會把迷宮圖形界面中定位方框位置對應(yīng)的迷宮數(shù)組的元素值改為1，maze對象將在該位置繪制墻的圖像；若按下鍵盤的Delete鍵，將會把迷宮圖形界面中定位方框位置對應(yīng)的迷宮數(shù)組的元素值改為0，maze對象將在該位置繪制通路的圖像；若按下鍵盤方向鍵的上鍵，將會把迷宮圖形界面中定位方框上移一個單位；若按下鍵盤方向鍵的下鍵，將會把迷宮圖形界面中定位方框下移一個單位；若按下鍵盤方向鍵的左鍵，將會把迷宮圖形界面中定位方框左移一個單位；若按下鍵盤方向鍵的右鍵，將會把迷宮圖形界面中定位方框右移一個單位；若按下鍵盤的Home鍵，將會調(diào)用maze對象的setBegin(intx,inty)方法，把當前定位方框所在位置的坐標傳給setBegin(intx,inty)方法，創(chuàng)建Maze類中的begin對象，并且maze對象將在該位置繪制起點圖像；若按下鍵盤的End鍵，將會調(diào)用maze對象的setEnd(intx,inty)方法，把當前定位方框所在位置的坐標傳給setEnd(intx,inty)方法，創(chuàng)建Maze類中的end對象，并且maze對象將在該位置繪制終點圖像；若按下鍵盤的F9鍵，如果迷宮圖形界面沒有設(shè)置起點或終點，將會提示設(shè)置起點或終點，否則不能演示求解迷宮，如果迷宮設(shè)置完畢，將啟動求解迷宮線程，演示求解迷宮的過程；actionPerformed(ActionEvente)方法，當鼠標點擊菜單選項時將把產(chǎn)生的事件傳給該方法，鼠標點擊菜單選項“退出”時，將會關(guān)閉窗口并退出程序；鼠標點擊刷新地圖時，將會清空迷宮里內(nèi)容，讓用戶重新設(shè)置。3）內(nèi)部類SolveThread內(nèi)部類SolveThread實現(xiàn)了runnable接口，是在MazeGUI內(nèi)部定義的一個線程類。該線程根據(jù)rollback.isOver()返回的值判斷求解迷宮過程是否結(jié)束，若沒有結(jié)束，則不斷在求解過程中不斷地使線程睡眠200毫秒，可使求解迷宮的過程能清楚地展現(xiàn)給用戶，此外還調(diào)用rollback.forward()、rollback.back()等求解迷宮的核心算法，并調(diào)用repaint（）重繪。3.4.3代碼（MazeGUI.java）packagemaze;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;/***迷宮圖形界面**/@SuppressWarnings("serial")publicclassMazeGUIextendsFrameimplementsKeyListener,ActionListener{//迷宮GUI finalObjectobj=newObject();//鎖對象 introw=0,col=0; ImageoffScreen=null; Mazemaze;//構(gòu)建迷宮參數(shù) Rollbackrollback; Astarastar; Threadt1=newThread(newSolveThread(),"SolveThread");//尋路進程，在初始化Thread類時，把目標對象傳遞給這個線程實例 Threadt2=newThread(newAThread(),"AThread"); publicvoidpaint(Graphicsg){//調(diào)用繪制地圖的draw()方法和繪制人物位置的draw()方法 maze.draw(g); rollback.draw(g); } publicvoidupdate(Graphicsg){//雙緩沖防止屏幕閃爍 if(offScreen==null){ offScreen=this.createImage(col*50,row*50); } Graphicsoffg=offScreen.getGraphics(); Colorc=offg.getColor(); offg.setColor(Color.BLUE); offg.fillRect(0,0,col*50,row*50); offg.setColor(c); paint(offg); g.drawImage(offScreen,0,0,null); } publicMazeGUI() { } publicMazeGUI(introw,intcol){//初始化窗體 this.setTitle("算法課程設(shè)計-求解迷宮問題"); this.setSize(col*50,row*50); this.setLocation(200,80); this.setResizable(false); this.addWindowListener(newWindowAdapter(){ publicvoidwindowClosing(WindowEvente){ System.exit(0); } }); this.row=row; this.col=col; maze=newMaze(row,col);//構(gòu)建迷宮參數(shù) rollback=newRollback(maze,this); this.setVisible(true); MenuBarmenuBar=newMenuBar(); MenufileMenu=newMenu("文件"); MenusettingMenu=newMenu("操作"); MenuItemexitItem=newMenuItem("退出"); MenuItemmapItem=newMenuItem("刷新地圖"); MenuItemaItem=newMenuItem("A*算法尋找最短路徑"); MenuItemhelpItem=newMenuItem("幫助"); fileMenu.add(exitItem); settingMenu.add(mapItem); settingMenu.add(aItem); settingMenu.add(helpItem); menuBar.add(fileMenu); menuBar.add(settingMenu); setMenuBar(menuBar); addKeyListener(this); exitItem.addActionListener(this); mapItem.addActionListener(this); aItem.addActionListener(this); helpItem.addActionListener(this); } privateclassSolveThreadimplementsRunnable{//提供一個實現(xiàn)借口Runnable接口的類的實例，作為一個線程的目標對象 publicvoidrun(){ while(!rollback.isOver()){//尋路結(jié)束后，線程結(jié)束 synchronized(obj){ try{ Thread.sleep(200); }catch(InterruptedExceptione){ e.printStackTrace(); } if(!rollback.forward()){ rollback.back(); } repaint(); } } } } privateclassAThreadimplementsRunnable{//展示用A*算法求解迷宮過程的線程 publicvoidrun(){ while(!astar.as.isEmpty()){ synchronized(obj){ try{ Thread.sleep(200); }catch(InterruptedExceptione){ e.printStackTrace(); } Apositiontemp=(Aposition)astar.as.top(); astar.as.pop(); maze.mazeMap[temp.y][temp.x]=5; rollback.curPos.x=temp.x; rollback.curPos.y=temp.y; } repaint(); if(astar.as.isEmpty())JOptionPane.showMessageDialog(null,"找到最短路徑最短路徑！"); } } } publicvoidkeyTyped(KeyEvente){ } publicvoidkeyReleased(KeyEvente){ } publicvoidkeyPressed(KeyEvente){ if(e.getKeyCode()==KeyEvent.VK_DELETE){ maze.mark(maze.drawPos,0); } elseif(e.getKeyCode()==KeyEvent.VK_ENTER){ maze.mark(maze.drawPos,1); } elseif(e.getKeyCode()==KeyEvent.VK_F9){ if(maze.begin==null){ JOptionPane.showMessageDialog(null,"起點沒有設(shè)置"); }elseif(maze.end==null){ JOptionPane.showMessageDialog(null,"終點沒有設(shè)置"); }elseif(t1.getState().equals(Thread.State.NEW)){//當沒有線程處于運行態(tài)時 t1.start();//啟動尋路線程 System.out.print("new"); }elseif(t1.getState().equals(Thread.State.TERMINATED)){//當該線程處于終止態(tài)時，又點擊了F9，即重新演示 t1=newThread(newSolveThread(),"SolveThread");//新建線程 rollback.flush();//刷新 maze.resume();//恢復(fù)迷宮到初始狀態(tài) t1.start(); } else{//在尋路過程中，如果點擊了“F9”按鍵 System.out.print("repeat"); rollback.flush();//清空棧，并把sprite中的curPos對象恢復(fù)到初試位置 maze.resume();//恢復(fù)迷宮到初始狀態(tài) repaint(); } } elseif(e.getKeyCode()==KeyEvent.VK_DOWN){ if(maze.drawPos.y+1>0&&maze.drawPos.y+1<row-1)//禁止定位方框移動到最外圍的“墻”上 maze.drawPos.y=maze.drawPos.y+1; } elseif(e.getKeyCode()==KeyEvent.VK_UP){ if(maze.drawPos.y-1>0&&maze.drawPos.y-1<row-1) maze.drawPos.y=maze.drawPos.y-1; } elseif(e.getKeyCode()==KeyEvent.VK_RIGHT){ if(maze.drawPos.x+1>0&&maze.drawPos.x+1<col-1) maze.drawPos.x=maze.drawPos.x+1; } elseif(e.getKeyCode()==KeyEvent.VK_LEFT){ if(maze.drawPos.x-1>0&&maze.drawPos.x-1<col-1) maze.drawPos.x=maze.drawPos.x-1; } elseif(e.getKeyCode()==KeyEvent.VK_END){ maze.setEnd(maze.drawPos.x,maze.drawPos.y); } elseif(e.getKeyCode()==KeyEvent.VK_HOME){ maze.setBegin(maze.drawPos.x,maze.drawPos.y);//起點坐標 rollback.setCurPos(maze.drawPos.x,maze.drawPos.y);//設(shè)置回溯算法中的當前點 rollback.remember(rollback.curPos); } repaint(); } publicvoidactionPerformed(ActionEvente){ Stringes=e.getActionCommand(); if(es.equals("退出")){ System.exit(0); }elseif(es.equals("刷新地圖")){ maze=newMaze(row,col); rollback=newRollback(maze,this); t2=newThread(newAThread(),"AThread"); repaint(); }elseif(es.equals("A*算法尋找最短路徑")){ if(maze.end==null||maze.begin==null){ JOptionPane.showMessageDialog(null,"終點或終點沒有設(shè)置！"); return; }elseif(t2.getState().equals(Thread.State.TERMINATED)){ JOptionPane.showMessageDialog(null,"最短路徑已找到，請刷新地圖！"); return; }elseif(t2.getState().equals(Thread.State.NEW)){ astar=newAstar(maze); astar.solve(); t2.start(); } }elseif(es.equals("幫助")){ JOptionPane.showMessageDialog(null,"Home：設(shè)置起點\nEnd：設(shè)置終點\nEnter：設(shè)置墻\nDelete：刪除墻\nF9：演示\n"); } }} 3.5Position.java（圖形界面坐標的存儲結(jié)構(gòu)）3.5.1UML圖Position類創(chuàng)建的對象是Maze類、MazeGUI類和Rollback類最重要的成員之一。該類負責在Maze類、MazeGUI類和Rollback類之間傳遞消息，其對象存有當前位置的坐標信息。該類包含兩個整型的成員變量x和y，記錄當前位置在迷宮圖形界面的橫、縱坐標。標明Position類的主要成員變量、成員方法的UMl圖如圖7所示。圖7Position類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。成員變量x、y是int類型的變量，標志迷宮圖形界面的坐標。x代表圖形界面的橫坐標，但對應(yīng)到迷宮數(shù)組中的是列，y代表圖形界面的縱坐標，但對應(yīng)到迷宮數(shù)組中的是行。2）成員方法Position(intx,inty)方法是Position類的構(gòu)造方法。equals(Objecto)方法用于判斷當前位置的o對象是否和調(diào)用該方法的Position類對象的內(nèi)容相等。方法先判斷o是否為Position類的實例，若是先強制轉(zhuǎn)換則返回ture，否則返回false。3.5.2代碼（Position.java）packagemaze;/***點坐標類**/publicclassPosition{ publicintx,y; publicPosition(intx,inty){ this.x=x; this.y=y; }publicPosition(){ } publicbooleanequals(Objecto){ if(o==null){ returnfalse; } if(!(oinstanceofPosition)){ returnfalse; } Positionp=(Position)o; returnthis.x==p.x&&this.y==p.y; }}3.6Stack.java(數(shù)據(jù)結(jié)構(gòu)類型)3.6.1UML圖Stack類創(chuàng)建的對象是Sprite類的最重要的成員之一。該類負責保存在求解迷宮過程中所走過的路徑信息。該類包含一個內(nèi)部類Node，定義了棧中存儲的節(jié)點元素的類型。另外還含有一個整型成員變量n和一個Node類型的成員變量top，分別記錄棧中元素的個數(shù)以及棧頂元素的信息。而Node類定義的是棧中節(jié)點的類型，包含當前節(jié)點的信息info（Object類型）和以及棧中下一個元素的引用next（相當在C語言中的指針，這兒類似與鏈式存儲的棧）。標明Stack類的主要成員變量、成員方法的UMl圖如圖8所示。圖8Stack類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。成員變量top是Node類的對象，表示棧定元素。n是int類型的變量，表示棧中元素的個數(shù)。成員方法push(Objecto)方法，Stack類對象可調(diào)用該方法，根據(jù)o對象和當前的top對象創(chuàng)建一個新的top變量，然后n自加。top()方法，將top對象的info作為返回值返回。pop()方法，當棧不為空時，將當前棧頂元素的info返回，并把next賦給top對象，n自減。isEmpty()方法，負責判斷棧是否為空。3）內(nèi)部類Node內(nèi)部類Node代表棧中節(jié)點元素的類型，包含一個構(gòu)造方法和兩個成員變量info和是Object類型的變量，可轉(zhuǎn)換為Position類型的變量；next是Node類型的變量，是棧頂元素的下一個元素的引用（相當于指針）。3.6.2代碼（Stack.java）packagemaze;/***棧類**/publicclassStack{ privateNodetop;//節(jié)點為Node類型 privateintsize;//棧中節(jié)點數(shù) publicStack(){//構(gòu)造方法 top=null; size=0; } publicvoidpush(Objecto){ top=newNode(o,top); size++; } publicObjecttop(){ if(isEmpty())returnnull; Objecto=; returno; } publicvoidpop(){ if(isEmpty())return; else{ top=top.next; size--; return; } } publicbooleanisEmpty(){ returnsize==0; } privateclassNode{ publicObjectinfo; publicNodenext; publicNode(Objecto,Noden){//Node類構(gòu)造方法 info=o; next=n; } }}3.7Rollback.java（核心算法——回溯法）3.7.1效果圖Rollback類繪制人物的效果圖如圖9所示。圖9人物圖3.7.2UML圖Rollback類創(chuàng)建的對象是是MazeGUI類最重要的成員之一。該類負責根據(jù)Maze類中的迷宮數(shù)組的信息采用回溯算法，控制并繪制人物在迷宮圖形界面窗口中的位置。標明Rollback類的主要成員變量、成員方法的UMl圖如圖10所示。圖10Rollback類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。1）成員變量curPos是Position類型的對象，該對象表示在求解迷宮過程中人物位置的點，同時也是棧頂元素。memory是Stack類型的對象，表示一個棧，而元素采用鏈式存儲的結(jié)構(gòu)。maze是Maze類型的對象，是MazeGUI類中maze對象的一個引用。mt是MazeGUI類型的對象，在Rollback類中是通過該變量來控制線程的。person是Image類型的對象，是所要繪制的人物圖像。2）成員方法Rollback(Mazem,MazeGUImt)方法是Rollback類的構(gòu)造方法。forward()方法，該方法根據(jù)maze對象的isPass（）方法的返回值來判斷curPos周圍是否有通路。若有，將curPos壓入棧中，并把下一個通路的坐標賦給curPos的坐標，并標記該通路已走過。back（）方法，當curPos周圍沒有通路時，調(diào)用此方法獲取棧頂元素中info域，若不空，則將curPos標記為從棧中彈出的點，并彈出棧頂元素，把info域賦給curPos，實現(xiàn)回溯。若為空，則表示棧中沒有元素，此時已經(jīng)回溯到起點，迷宮不存在可通的路徑，使求解迷宮線程等待。isOver（）方法,該方法負責判斷是否找到了終點。若curPos的坐標和maze.end的坐標相同則找到了終點，返回true，否則返回false。remember（Positionp）方法，該方法調(diào)用memory的push（）方法，將引用p壓入棧中。draw(Graphicsg)方法，該方法負責在curPos點處繪制人物圖像。setCurPos(intx,inty)方法，該方法根據(jù)x，y來設(shè)置curPos的坐標。3.7.3算法偽代碼rollback對象back()方法rollback對象back()方法rollback對象forward()方法先將curPos（初始值為begin）壓入stack中do｛mark()，即標記當前位置已走過，使對應(yīng)位置的mazeMap[][]值為2；if（curPos周圍有通路，即對應(yīng)位置的mazeMap[][]值為0）｛選擇一個有通路方向，修改curPos的坐標；將curPos壓入棧中；If（curPos的坐標和end的坐標相同）結(jié)束；｝else｛stack.pop()，出棧；stack.top()取棧頂元素；If（該元素不為null）｛將curPos的坐標修改為該位置的坐標；｝else｛stack已空，為找到end；｝｝while（當stack不為null）3.7.4代碼（Rollback.java）packagemaze;importjava.awt.*;importjavax.swing.*;/***回溯算法實現(xiàn)**/publicclassRollback{ PositioncurPos;//當前位置 Stackmemory;//路徑堆棧 Mazemaze; MazeGUImt; Imageperson=newImageIcon("1.gif").getImage(); publicRollback(Mazem,MazeGUImt){ this.maze=m; this.mt=mt; this.memory=newStack(); } publicintisPass(Positionp){//判斷周圍的通道那些沒走過（東南西北） intj=p.x; inti=p.y; if(maze.mazeMap[i][j+1]==0){ return0; } if(maze.mazeMap[i+1][j]==0){ return1; } if(maze.mazeMap[i][j-1]==0){ return2; } if(maze.mazeMap[i-1][j]==0){ return3; } return-1;//周圍都無法通過 } publicbooleanforward(){//前進 this.maze.mark(this.curPos,2);//標記為已走過 intdirection=this.isPass(this.curPos); if(direction==-1){ returnfalse;//周圍都無法通過時返回false } intx=this.curPos.x+(1-direction)%2; inty=this.curPos.y+(2-direction)%2; this.curPos.x=x; this.curPos.y=y; remember(this.curPos); returntrue; } publicvoidback(){//forward()返回false時執(zhí)行該方法 this.maze.mark(this.curPos,3);//取消腳印 this.memory.pop();//出棧 Positionp=(Position)this.memory.top();//獲取前一個位置 if(p!=null){ this.curPos.x=p.x;//將前一個位置設(shè)為當前位置 this.curPos.y=p.y; } elsereturn; } publicbooleanisOver(){//判斷是否結(jié)束,包括找到終點和沒找到終點兩種情況 if(this.curPos.x==maze.end.x&&this.curPos.y==maze.end.y){ JOptionPane.showMessageDialog(null,"Congratulation,Pathfound!"); while(!this.memory.isEmpty()){//找到后，將棧清空 this.maze.mark((Position)this.memory.top(),2); this.memory.pop(); } returntrue; } elseif(this.memory.isEmpty()){//棧已為空，找不到出路 JOptionPane.showMessageDialog(null,"Sorry,Pathnotfound!"); returntrue; } returnfalse; } publicvoidremember(Positionp){//保存當前路徑 this.memory.push(newPosition(p.x,p.y)); } publicvoiddraw(Graphicsg){//繪制人物的位置 if(curPos!=null){ g.drawImage(person,this.curPos.x*50,24+this.curPos.y*50,50,50,null); } } publicvoidflush(){//刷新，清空棧，并把sprite中的curPos對象恢復(fù)到初試位置 while(!this.memory.isEmpty()){ this.memory.pop(); } this.curPos.x=maze.begin.x; this.curPos.y=maze.begin.y; remember(this.curPos); } publicvoidsetCurPos(intx,inty){ this.curPos=newPosition(x,y); }}3.8Astar.java（核心算法——A*算法）3.8.1A*算法簡介A*算法在人工智能中是一種典型的啟發(fā)式搜索算法。啟發(fā)式即啟發(fā)式。對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。A*算法估價函數(shù)：f(n)=g(n)+h(n)g(n)——在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價h(n)——從n到目標節(jié)點最佳路徑的估計代價特殊地，當h(n)=0時，只需求出g(n)，即求出起點到任意節(jié)點n的最短路徑，即Dijkstra算法。在求解迷宮問題中，用兩個列表來保存探索過的解。開啟列表——保存已經(jīng)評估過，但沒有走過的點關(guān)閉列表——保存已經(jīng)走過的點3.8.2效果圖Maze類繪制腳印的效果圖如圖11所示。圖11腳印圖3.8.3UML圖Astar類創(chuàng)建的對象是是MazeGUI類最重要的成員之一。該類負責根據(jù)Maze類中的迷宮數(shù)組的信息采用A*算法，找到起點到終點的最短路徑并打印出來。標明Astar類的主要成員變量、成員方法的UMl圖如圖12所示。圖12Astar類的UML圖以下是UML圖中有關(guān)數(shù)據(jù)和方法的詳細說明。1）成員變量maze是Maze類型的對象，是MazeGUI類中maze對象的一個引用。A*算法中要根據(jù)maze對象的mazeMap域中相關(guān)位置的值，來判斷該點。as是Stack類型的對象，表示一個棧，而元素采用鏈式存儲的結(jié)構(gòu)。aMap是APosition類型的二維數(shù)組cur是APosition類型的對象，該對象表示用A*算法求解迷宮過程中當前探索的點。begin是APosition類型的對象，該對象表示A*算法中的起點，存有相關(guān)信息。end是APosition類型的對象，該對象表示A*算法中的終點，存有相關(guān)信息。open是一個LinkedList類型的列表，是java類庫中常用的容器，用來存放Aposition類型的元素，相關(guān)的操作。close是一個LinkedList類型的列表，是java類庫中常用的容器，用來存放Aposition類型的元素，相關(guān)的操作。direct是整型二維數(shù)組，存放二維單位方向向量。2）成員方法Astar(Mazem)方法是Astar類的構(gòu)造方法。probe(APositioncur)方法是探索當期位置的點，根據(jù)maze.mazeMap[][]中的值探索cur周圍方向的點，并計算這些點的相關(guān)信息保存起來。sort（）方法是將open表中的元素按F值從小到大排序。solve（）方法反映了A*算法的基本步驟，其中會調(diào)用probe方法。setH(APositionp)方法是求出p點的h值，采用哈曼頓方法，從當前點到終點之間水平和垂直的方格的數(shù)量總和。setG(APositionp)方法是求出p點的G值，向某個方向移動一格，累計G值加一。setF(APositionp)方法是求出p點的F值，F(xiàn)=H+G。3.8.4算法偽代碼astar對象solve()方法astar對象solve()方法astar對象probe()方法while(open!=NULL)｛從open表中刪除估價值f最小的節(jié)點，并賦給curPos；將curPos加入close表中；探索curPos周圍的點aMap[][]；If（aMap[][]為通路）｛計算aMap[][]的估價值；將aMap[][]的前驅(qū)節(jié)點賦為curPos；將aMap[][]加入到open表中；｝elseif（aMap[][]為end）｛加end加入關(guān)閉列表中；跳出循環(huán)；｝elseif（aMap[][]已在關(guān)閉列表中）｛｝else｛if（curPos.g+1<aMap[][].g）將aMap[][]的父節(jié)點pre賦為curPos；｝sort()，將開啟列表中各點按f值從小到大排序；｝3.8.4代碼（Astar.java）packagemaze;importjava.util.*;importjavax.swing.JOptionPane;/***A*算法實現(xiàn)**/publicclassAstar{ Mazemaze; Stackas=newStack(); Aposition[][]aMap; Apositioncur;//當前點 Apositionbegin; Apositionend; LinkedList<Aposition>open=newLinkedList<Aposition>();//開啟列表 LinkedList<Aposition>close=newLinkedList<Aposition>();//關(guān)閉列表 int[][]direction={{1,0},{0,1},{-1,0},{0,-1}};//方向數(shù)組，右下左上 publicAstar(Mazemaze){//構(gòu)造方法 this.maze=maze; aMap=newAposition[maze.row][maze.col];//該二維數(shù)組的元素都為null this.begin=newAposition(maze.begin.x,maze.begin.y,null,0);//1:close,0:open this.end=newAposition(maze.end.x,maze.end.y,null,-1);//-1isend aMap[this.begin.y][this.begin.x]=this.begin; aMap[this.end.y][this.end.x]=this.end; open.add(this.begin);//將起點放入關(guān)閉列表 } publicvoidprobe(Apositioncur){//試探方法 for(inti=0;i<4;i++){ inttx=cur.x+direction[i][0]; intty=cur.y+direction[i][1]; if(maze.mazeMap[ty][tx]==0&&this.aMap[ty][tx]==null){//是通路，并且還不存在，引用為null aMap[ty][tx]=newAposition(tx,ty,cur,0);//使引用明確,并開啟 setH(aMap[ty][tx]); setG(aMap[ty][tx]); setF(aMap[ty][tx]); open.add(aMap[ty][tx]);//加入到開啟列表中 }elseif(aMap[ty][tx]!=null){//已存在的 if(close.contains(aMap[ty][tx])){}//已在關(guān)閉列表中則不處理 elseif(aMap[ty][tx].equals(this.end)){//若找到終點，將終點加入到關(guān)閉列表中 this.end.pre=cur; close.add(this.end); }else{ if(aMap[ty][tx].g>cur.g+1){//已在開啟列表中，比較是否更優(yōu) aMap[ty][tx].pre=cur; setG(aMap[ty][tx]); setF(aMap[ty][tx]); } } } } sort(); //將開啟列表排序 } publicvoidsort(){//根據(jù)F值從小到大排序 Apositiontemp; for(inti=0;i<open.size()-1;i++){ for(intj=i+1;j<open.size();j++){ if(open.get(i).f>open.get(j).f){ temp=open.get(i); open.set(i,open.get(j)); open.set(j,temp); } } } } publicvoidsolve(){//求解 Apositiontemp;//設(shè)置回滾對象 while(open.size()!=0){//當開啟列表不為空時，循環(huán) this.cur=(Aposition)open.poll();//取開啟列表中F值最小的,并從開啟列表中刪除 close.add(this.cur);//加入到關(guān)閉列表中 this.cur.flag=1;//標記為關(guān)閉 probe(this.cur);//探索啟發(fā) if(close.contains(this.end)){ temp=this.end; while(temp!=null){ as.push(temp); temp=temp.pre; } return; } } JOptionPane.showMessageDialog(null,"Sorry,Pathnotfound!"); return; } publicvoidsetH(Apositionp){//求H值 p.h=Math.abs(this.end.x-p.x)+Math.abs(this.begin.y-p.y); } publicvoidsetG(Apositionp){//求G值 p.g=p.pre.g+1; } publicvoidsetF(Apositionp){//求F值 p.f=p.g+p.h; }}astar對象probe()方法astar對象probe()方法astar對象probe()方法3.9Aposition.java（A*算法存儲結(jié)構(gòu)）3.9.1UML圖Aposition類是Position類的派生類，APosition類創(chuàng)建的對象是Astar類、MazeGUI類和Rollback類最重要的成員之一。該類負責在Astar類、MazeGUI類和Rollback類之間傳遞消息，其對象存有當前位置的坐標信息、A*算法的評估函數(shù)值、開關(guān)標記和父節(jié)點等。標明Astar類的主要成員變量、成員方法的UMl圖如圖13所示。圖9-13Aposition類的UML圖3.9.2代碼（Aposition.java）packagemaze;/***A*算法點坐標類**/publicclassApositionextendsPosition{//繼承了Position類 intf=0,g=0,h=0; intflag;//標記是否開啟 Apositionpre; publicAposition(intx,inty,Apositionp,intflag){ super(x,y); this.pre=p;//前驅(qū)節(jié)點 this.flag=flag; }}4程序測試調(diào)試程序編碼的過程中，我們遇到過各種問題，有的是編譯時錯誤，還有的是運行時的異常。編譯時錯誤主要是，對象未初始化。運行時異常主要包括空指針、數(shù)組越界等。在程序編碼完成后，由