遞歸算法能夠解決很多計(jì)算機(jī)科學(xué)問題，迷宮問題就是其中一個(gè)典型案例。本篇教程我們將采用遞歸算法求解迷宮問題，輸出從入口到出口的所有迷宮路徑。

01

用遞歸算法解決迷宮問題

迷宮問題在《數(shù)據(jù)結(jié)構(gòu)教程》第3章介紹過，設(shè)mgpath(int xi，int yi，int xe，int ye，path)是求從(xi，yi)到(xe，ye)的迷宮路徑，用path變量保存一條迷宮路徑，它是元素為Box類型的ArrayList對(duì)象，其中Box類定義如下：

class?Box????????????????????????????????????????//方塊類
{????int?i;??????????????????????????????????????//方塊的行號(hào)int?j;??????????????????????????????????????//方塊的列號(hào)public?Box(int?i1,int?j1)??????//構(gòu)造方法{???i=i1;j=j1;}
}

當(dāng)從(xi，yi)方塊找到一個(gè)相鄰可走方塊(i，j)后，mgpath(i，j，xe，ye，path)表示求從(i，j)到出口(xe，ye)的迷宮路徑。顯然，mgpath(xi，yi，xe，ye，path)是“大問題”，而mgpath(i，j，xe，ye，path)是“小問題”(即大問題=試探一步+小問題)，如下圖所示。

▍大小問題的關(guān)系

求解上述迷宮問題的遞歸模型如下：

mgpath(xi,yi,xe,ye,path)?將(xi,yi)添加到path中;????????????????????若(xi,yi)=(xe,ye)即找到出口
置mg[xi][yi]=-1;
輸出path中的迷宮路徑;
恢復(fù)出口迷宮值為0即置mg[xe][ye]=0
mgpath(xi,yi,xe,ye,path)?將(xi,yi)添加到path中;????????????????????????若(xi,yi)不是出口
置mg[xi][yi]=-1;
對(duì)于(xi,yi)每個(gè)相鄰可走方塊(i,j)，調(diào)用mg(i,j,xe,ye,path);
path回退一步并置mg[xi][yi]=0;

上述遞歸模型中，對(duì)于方塊(xi，yi)，先添加到path末尾(所有path中的方塊都是通道，所以初始調(diào)用時(shí)入口必須是通道)，對(duì)于它的每一個(gè)相鄰可走方塊(i，j)都執(zhí)行“小問題”mgpath(i，j，xe，ye，path)，之后需要從(xi，yi)方塊回退(刪除path中的末尾方塊)并置mg[xi][yi]為0，其目的是恢復(fù)前面求迷宮路徑而改變的環(huán)境，以便找出所有的迷宮路徑。以下圖的迷宮為例：

▍迷宮示意圖

求入口(1，1)到出口(4，4)所有迷宮路徑的完整程序如下：

import?java.lang.*;
import?java.util.*;
class?Box????????????????????????????????????????????//方塊類
{????int?i;??????????????????????????????????????????//方塊的行號(hào)
????int?j;??????????????????????????????????????????//方塊的列號(hào)
????public?Box(int?i1,int?j1)???????????????????????????//構(gòu)造方法{???i=i1;j=j1;}
}
class?MazeClass????????????????????????????????????//求解迷宮路徑類
{????final?int?MaxSize=20;
????int?[][]?mg;????????????????????????????????????????//迷宮數(shù)組
????int?m,n;????????????????????????????????????????????//迷宮行列數(shù)
????int?cnt=0;??????????????????????????????????????//累計(jì)迷宮路徑數(shù)
????public?MazeClass(int?m1,int?n1)?????????????????//構(gòu)造方法{???m=m1;
????????n=n1;
????????mg=new?int[MaxSize][MaxSize];
????}
????public?void?Setmg(int?[][]?a)???????????????????????//設(shè)置迷宮數(shù)組{???for?(int?i=0;i????????????for?(int?j=0;j????????????????mg[i][j]=a[i][j];
????}
????void?mgpath(int?xi,intyi,intxe,intye,ArrayList?path)??//求解迷宮路徑為:(xi,yi)->(xe,ye){???Box?b;
????????int?di,i=0,j=0;
????????b=new?Box(xi,yi);
????????path.add(b);????????????????????????????????????//將(xi,yi)添加到path中
????????mg[xi][yi]=-1;??????????????????????????????//mg[xi][yi]=-1?????
????????if?(xi==xe&&yi==ye)?????????????????????//找到了出口,輸出一個(gè)迷宮路徑
????????{???System.out.printf("迷宮路徑%d:",++cnt);?//輸出path中的迷宮路徑
????????????for?(int?k=0;k????????????????System.out.printf("??(%d,%d)",path.get(k).i,path.get(k).j);
????????????System.out.println();
????????????mg[xi][yi]=0;???????????????????????????//恢復(fù)為0,否則別的路徑找不到出口
????????}
????????else????????????????????????????????????????????//(xi,yi)不是出口
????????{???di=0;
????????????while?(di<4)????????????????????????????????//處理(xi,yi)四周的每個(gè)相鄰方塊(i,j)
????????????{???switch(di)
????????????????{
????????????????case?0:i=xi-1;?j=yi;???break;
????????????????case?1:i=xi;???j=yi+1;?break;
????????????????case?2:i=xi+1;?j=yi;???break;
????????????????case?3:i=xi;???j=yi-1;?break;
????????????????}
????????????????if?(mg[i][j]==0)????????????????????????//(i,j)可走時(shí)
????????????????????mgpath(i,j,xe,ye,path);?????????//從(i,j)出發(fā)查找迷宮路徑
????????????????di++;???????????????????????????????//繼續(xù)處理(xi,yi)下一個(gè)相鄰方塊
????????????}
????????}
????????path.remove(path.size()-1);?????????????????//刪除path末尾方格(回退一個(gè)方塊)
????????mg[xi][yi]=0;
????}
}
public?class?Exam5_5
{????public?static?void?main(String[]?args){???int?[][]?a=?{?{1,1,1,1,1,1},{1,0,1,0,0,1},
????????????????{1,0,0,1,1,1},{1,0,1,0,0,1},
????????????????{1,0,0,0,0,1},{1,1,1,1,1,1}?};
????????MazeClassmz=new?MazeClass(6,6);
????????ArrayList?path=new?ArrayList();
????????mz.Setmg(a);
????????mz.mgpath(1,1,4,4,path);
????}
}

上述程序的執(zhí)行結(jié)果如下：

迷宮路徑1：?(1,1)??(2,1)??(3,1)??(4,1)??(4,2)??(4,3)??(3,3)??(3,4)??(4,4)
迷宮路徑2：?(1,1)??(2,1)??(3,1)??(4,1)??(4,2)??(4,3)??(4,4)

本例算法求出所有的迷宮路徑，可以通過路徑長度比較求出最短迷宮路徑(可能存在多條最短迷宮路徑)。

02

視頻講解

視頻教程如下：

03

源代碼下載

關(guān)注微信公眾號(hào)，后臺(tái)回復(fù)關(guān)鍵詞“迷宮問題”即可獲得完整源代碼。

【參考書籍】

《數(shù)據(jù)結(jié)構(gòu)教程(Java語言描述)》

ISBN：978-7-302-55134-8

李春葆 編著

定價(jià)：69.8元

上一篇：

用Python寫一個(gè)智力問答游戲 | 附代碼+視頻

利用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)股票預(yù)測(cè) | 附代碼

總結(jié)

以上是生活随笔為你收集整理的java 递归_采用递归算法求解迷宫问题（Java版） | 附代码+视频的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。