迷宮問(wèn)題中最短路徑問(wèn)題的探究

韓霖

摘要：經(jīng)典的最短路徑算法——Dijkstra算法是目前多數(shù)系統(tǒng)解決最短路徑問(wèn)題所采用的理論基礎(chǔ)，該文通過(guò)對(duì)Dijkstra算法的研究，給出利用Dijkstra算法求解“迷宮”的最短路徑的方法，進(jìn)一步探究經(jīng)過(guò)固定點(diǎn)的最短路徑，并建立簡(jiǎn)單的整數(shù)規(guī)劃模型通過(guò)Lingo軟件進(jìn)行求解此種情況下的最短路徑。

關(guān)鍵詞：最短路徑；迷宮問(wèn)題；Dijkstra算法；整數(shù)規(guī)劃；Lingo

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）33-0055-02

1 問(wèn)題描述

迷宮問(wèn)題早在古希臘時(shí)就已出現(xiàn)，如今迷宮又以游戲程序的形式呈現(xiàn)在我們?nèi)粘Ｊ褂玫碾娔X和手機(jī)上，求解迷宮問(wèn)題的基本思想是如何尋找從入口到出口的一條路徑，其基本算法主要包括傳統(tǒng)算法及智能算法兩大類。利用Dijkstra算法求解迷宮問(wèn)題的關(guān)鍵在兩點(diǎn)：一是如何把“迷宮”轉(zhuǎn)換化為一個(gè)帶權(quán)圖；二是如何使用Dijkstra算法求從入口到出口的最短路徑。戰(zhàn)略決策、機(jī)器人路徑規(guī)劃等許多智能問(wèn)題都可轉(zhuǎn)化為尋找迷宮最短路徑問(wèn)題。從迷宮的入口到出口的路徑有多條，最短的路徑是哪條一直都是人們探討的重點(diǎn)。

2 迷宮問(wèn)題轉(zhuǎn)換為帶權(quán)圖的鄰接矩陣

迷宮中的位置采用二維數(shù)組存儲(chǔ)，任何位置記作a[i][j]，當(dāng)a[i][j]=0，則有通路，如果a[i][j]=1，則無(wú)通路。按照這樣的規(guī)定我們求入口到出口的一條最短路徑。

接下來(lái)用鄰接矩陣進(jìn)行存儲(chǔ)，需要找到迷宮問(wèn)題中所有值為0的點(diǎn)的個(gè)數(shù)為節(jié)點(diǎn)個(gè)數(shù)，令i為這些點(diǎn)中第i個(gè)節(jié)點(diǎn)，此點(diǎn)其八個(gè)方向?yàn)?的點(diǎn)作為i的鄰接點(diǎn)。由于鄰接表的頂點(diǎn)存儲(chǔ)方式為散列存儲(chǔ)，我們把每個(gè)為0的元素定義一個(gè)序號(hào)，不妨在二維數(shù)組中按行優(yōu)先的規(guī)則找到為0的元素并按照順序設(shè)置序號(hào)，這樣鄰接點(diǎn)節(jié)點(diǎn)既有行號(hào)列號(hào)，又有此節(jié)點(diǎn)作為頂點(diǎn)節(jié)點(diǎn)的位置，采用二維數(shù)組來(lái)存儲(chǔ)，當(dāng)a[i][j]為0時(shí)，b[i][j]存儲(chǔ)a[i][j]的序號(hào)，否則為0。以圖1所示的迷宮問(wèn)題為例，由上面分析得到數(shù)組b的存儲(chǔ)（如圖2），（其中b[i][j]為0無(wú)通路，b[i][j]非0則有通路）。

因?yàn)轫毲蟪鰪娜肟诘匠隹诘淖疃搪窂?，則要給出表示迷宮的帶權(quán)圖的鄰接矩陣。最短路徑即是從入口到出口經(jīng)過(guò)邊數(shù)最少的路，所以，約定每相鄰接的兩個(gè)頂點(diǎn)間的權(quán)值為1，令鄰接矩陣中第i行第j列的元素為[aij]，則鄰接矩陣可定義為：

3 用Dijkstra算法求解“迷宮問(wèn)題”

上面我們已將迷宮問(wèn)題表示為一個(gè)圖的鄰接矩陣（如圖4），利用Dijkstra算法（參考[1]）求解迷宮問(wèn)題就轉(zhuǎn)化為對(duì)此臨接矩陣求從迷宮入口出發(fā)到其余各頂點(diǎn)的最短路徑。假設(shè)入口頂點(diǎn)為[v1]，出口頂點(diǎn)為[v10]，則問(wèn)題轉(zhuǎn)化為求[v1]到[v10]的最短路徑。

3.1 距離向量d[i]的求解

我們根據(jù)Dijkstra算法構(gòu)造可得到下表1。

3.2 路徑向量p[i]的求解

我們得到關(guān)于路徑向量的表格，如下表2。

3.3 小結(jié)

從表1中可以看出從頂點(diǎn)1到頂點(diǎn)10的最短路徑的距離為5，由表2知從起始點(diǎn)到終點(diǎn)經(jīng)過(guò)[v3]、[v5]、[v7]、[v9]四點(diǎn)，即路徑為：[v1?v3?v5?v7?v9?v10]。這就是所求的從迷宮入口（頂點(diǎn)1）到迷宮出口（頂點(diǎn)10）的一條最短路徑，如圖5：

4 關(guān)于“迷宮問(wèn)題”的進(jìn)一步討論

有時(shí)“迷宮問(wèn)題”中并不只是從入口進(jìn)入找到出口走出即可，例如，需要進(jìn)入迷宮中的固定地點(diǎn)，然后再找到出口走出。這時(shí)如何走才能使路徑最短呢？下面我們就來(lái)解決這樣的問(wèn)題。

5 結(jié)束語(yǔ)

本文給出了解決“迷宮問(wèn)題”最短路徑的方法，把迷宮問(wèn)題轉(zhuǎn)化成一個(gè)帶權(quán)圖，利用Dijkstra算法求出從入口到出口的一條最短路徑，并且對(duì)“迷宮問(wèn)題”做進(jìn)一步討論，對(duì)于有限制條件的“迷宮問(wèn)題”，通過(guò)簡(jiǎn)單的整數(shù)規(guī)劃方法并利用lingo軟件求解經(jīng)過(guò)固定點(diǎn)的最短路徑。

參考文獻(xiàn)：

[1] 胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用[M].北京：高等教育出版社，2008.

[2] 卜月華.圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2000.

[3] 嚴(yán)蔚敏，沈佩娟.數(shù)據(jù)結(jié)構(gòu)[M].北京：國(guó)防工業(yè)出版社，1982.

[4] 楊淑群.迷宮問(wèn)題轉(zhuǎn)變成圖的問(wèn)題的討論[J].計(jì)算機(jī)與現(xiàn)代化，2003（2）：10-11.

[5] 朱素英.迷宮問(wèn)題的圖論解法探討[J].湖南人文科技學(xué)院學(xué)報(bào)，2006，6（3）：73-74.

[6] 馬良.旅行推銷員問(wèn)題的算法綜述[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2000，30（2）：156-157.

[7] 陳芳芳，姜忠義，吳春青.運(yùn)籌學(xué)教學(xué)中的動(dòng)態(tài)規(guī)劃求解最短路徑問(wèn)題的一個(gè)注記[J].高師理科學(xué)刊，2016（9）.

[8] 徐天亮.運(yùn)輸與配送[M].2版.北京：中國(guó)物資出版社，2012.

【通聯(lián)編輯：代影】