以算法設(shè)計(jì)和Matlab編程為主題,對(duì)經(jīng)典算法問(wèn)題"羅密歐與朱麗葉的迷宮問(wèn)題"提出了一種基于回溯法的有效解決策略,并使用Matlab編程語(yǔ)言實(shí)現(xiàn)了結(jié)果的可視化輸出。 

【文章來(lái)源】：電腦編程技巧與維護(hù). 2019,(09)

【文章頁(yè)數(shù)】：7 頁(yè)

【部分圖文】：

羅密歐與朱麗葉的迷宮問(wèn)題的程序調(diào)用關(guān)系圖

2019.09elseifA(j,k)==row*column-numberOfClose-dRoomstext(k-0.35,j,num2str(A(j,k))+"：朱麗葉",'FontSize',10);elseifA(j,k)==-1text(k-0.35,j,num2str(A(j,k))+"：封閉房間",'FontSize',10);elsetext(k,j,num2str(A(j,k)),'FontSize',18);endendendendend3.6程序調(diào)用關(guān)系根據(jù)程序模塊的設(shè)計(jì)方案，各程序之間的調(diào)用關(guān)系如圖3所示。4程序測(cè)試4.1測(cè)試數(shù)據(jù)輸入以下測(cè)試數(shù)據(jù)：迷宮的行數(shù)和列數(shù)為3和4，迷宮中封閉房間的數(shù)量為2，封閉房間的位置為（1,2）和（3,4），羅密歐的初始位置為（1,1），朱麗葉的位置為（2,2）。輸入的數(shù)據(jù)如圖4所示，命令行輸出的結(jié)果如圖5所示，可視化輸出的圖片如圖6所示。4.2測(cè)試結(jié)果分析根據(jù)測(cè)試數(shù)據(jù)的結(jié)果可知，當(dāng)迷宮的行數(shù)和列數(shù)為3和4，迷宮中封閉房間的數(shù)量為2，封閉房間的位置為（1,2）和（3,4），羅密歐的初始位置為（1,1），朱麗葉的位置為（2,2）時(shí)，羅密歐通往朱麗葉房間的最少轉(zhuǎn)彎次數(shù)為6，不同的最少轉(zhuǎn)彎次數(shù)的路線數(shù)量為7，以二維矩陣的形式進(jìn)行表示。所有的轉(zhuǎn)彎次數(shù)最少的路線如下所示。（1）（2）圖3羅密歐與朱麗葉的迷宮問(wèn)題的程序調(diào)用關(guān)系圖圖4測(cè)試數(shù)據(jù)圖5測(cè)試數(shù)據(jù)命令行窗口結(jié)果輸出圖6測(cè)試數(shù)據(jù)結(jié)果可視化輸出main函數(shù)initialize函數(shù)searchPath函數(shù)PrintResult函數(shù)checkStep函數(shù)savePath函數(shù)resultVisualization函數(shù)(下轉(zhuǎn)第167頁(yè))146

2019.091問(wèn)題描述算法問(wèn)題“羅密歐與朱麗葉的迷宮問(wèn)題”的問(wèn)題描述如下所示：羅密歐與朱麗葉身處一個(gè)m*n的迷宮中，如圖1所示。每一個(gè)方格表示迷宮中的一個(gè)房間，迷宮中有一些房間是封閉的，不允許任何人進(jìn)入，如黃色方格所示。在迷宮中任何位置均可沿8個(gè)方向（上、下、左、右、左上、左下、右上、右下）進(jìn)入未封閉的房間。羅密歐位于迷宮的某一個(gè)房間中，他需要找出一條通向朱麗葉所在房間的路線，該路線必須滿足以下條件：（1）在抵達(dá)朱麗葉的房間之前，羅密歐必須走遍所有未封閉的房間各一次。（2）該路線的轉(zhuǎn)彎次數(shù)為最少，每改變一次前進(jìn)方向算作一次轉(zhuǎn)彎。試設(shè)計(jì)一個(gè)算法幫助羅密歐找出所有符合上述要求的通往朱麗葉房間的路線。2問(wèn)題分析2.1解題目標(biāo)根據(jù)問(wèn)題描述可知，羅密歐與朱麗葉的迷宮問(wèn)題的解題目標(biāo)是：給定一個(gè)m*n的迷宮（假設(shè)以迷宮左上角為坐標(biāo)原點(diǎn)建立直角坐標(biāo)系）、迷宮中封閉房間的數(shù)量為k、封閉房間的位置為（pi,qj）（i,j=1,2,3,...)、羅密歐房間的起始位置（a,b）、朱麗葉房間的位置（c,d）、求滿足走遍所有未封閉房間各一次且轉(zhuǎn)彎次數(shù)最少的羅密歐通往朱麗葉房間的路線。假設(shè)迷宮中未封閉房間的數(shù)量為w，羅密歐通往朱麗葉的路線的每一步為Si（Si∈（0,1),i=1,2,3,...）（Si為0表示當(dāng)前房間為封閉房間，為1表示當(dāng)前房間未封閉），該路線的轉(zhuǎn)彎次數(shù)為t，羅密歐最后一步到達(dá)的房間的位置為（x,y），朱麗葉房間的位置為（c,d），則羅密歐與朱麗葉的迷宮問(wèn)題等價(jià)于滿足以下條件的問(wèn)題

【參考文獻(xiàn)】：
期刊論文
[1]回溯法與分枝限界法的分析與比較[J]. 楊超,何書(shū)前,鄭志群,石春.  電腦知識(shí)與技術(shù). 2018(11)
[2]回溯法在計(jì)算機(jī)程序設(shè)計(jì)中的應(yīng)用[J]. 裴南平,畢傳林.  電腦知識(shí)與技術(shù). 2017(31)
[3]回溯算法的形式模型[J]. 王巖冰,鄭明春,劉弘.  計(jì)算機(jī)研究與發(fā)展. 2001(09)



本文編號(hào)：3290700