離散數(shù)學(xué)視域下迷宮尋路問題的解決路徑

1、離散數(shù)學(xué)視域下迷宮尋路問題的解決路徑關(guān)鍵詞：迷宮尋路; 謂詞邏輯; 廣度優(yōu)先搜索;迷宮尋路問題本質(zhì)上屬于人工智能中路徑搜索分支,解決迷宮尋路問題對于人工智能中游戲設(shè)計(jì)具有重要的指導(dǎo)意義1。謂詞邏輯接近于人類的自然語言,在早期人工智能表示方法中廣泛應(yīng)用在計(jì)算機(jī)存儲表示中。廣度優(yōu)先搜索通過隊(duì)列存儲迷宮路徑節(jié)點(diǎn),因此若給定起點(diǎn)和終點(diǎn)且存在最優(yōu)路徑,通過廣度優(yōu)先搜索求解出的路徑一定屬于最優(yōu)路徑,對于解決迷宮問題有著顯著優(yōu)勢。1、 謂詞邏輯與迷宮尋路問題1.1、 問題提出迷宮的每一個(gè)格子,對應(yīng)一個(gè)狀態(tài)。設(shè)有迷宮的大小為6×7,共有42個(gè)狀態(tài),如圖1所示。初始狀態(tài)為41,目標(biāo)狀態(tài)為2和5。對于

2、迷宮中的每個(gè)狀態(tài),在它的上下左右四個(gè)方向中,如果某個(gè)方向沒有墻,則可以走進(jìn)下一個(gè)狀態(tài)2。圖1 迷宮圖圖2迷宮矩陣表示1.2、 問題分析根據(jù)定義所需求解問題,首先定義表示事物狀態(tài)的謂詞,AT(person,x)表示person位于位置x處,Start(x)表示位置x是起始位置,End(x)表示位置x是終點(diǎn)位置,Pass(x,y)表示位置x和位置y合法,且相鄰,且無阻隔;定義表示事物狀態(tài)的謂詞,設(shè)初始狀態(tài)AT(person,41),最終求解得到目標(biāo)狀態(tài)AT(person,2)或AT(person,5);定義操作符Move(person,x)表示從位置x向上下左右移動;假定條件AT(person,x

3、)表示當(dāng)前在節(jié)點(diǎn)x處;定義動作謂詞Goto(x,y)表示從x走到y(tǒng);定義條件:AT(person,x)∧Pass(x,y)表示刪除AT(person,x),添加AT(person,y)。1.3 、問題求解通過推理可以獲得一條路徑:AT(person,41)→AT(person,40)→AT(person,39)→AT(person,38)→(person,37)→AT(person,36)→AT(person,29)→AT(person,30)→AT(person,31)→AT(person,32

4、)→AT(person,33)→AT(person,26)→AT(person,27)→AT(person28)→AT(person,21)→AT(person,14)→AT(person,7)→AT(person,6)→AT(person,5)(而無法達(dá)到位置2)。2 、廣度優(yōu)先搜索與迷宮尋路問題2.1、 問題提出廣度優(yōu)先搜索采用的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列,利用隊(duì)列先進(jìn)先出的特點(diǎn),來模擬走迷宮的過程。2.2 、問題分析以不含多條出路,不帶環(huán)的簡單迷宮為例,以1為障礙物、0為可行路,且僅可上、下、左、右行走;且假設(shè)

5、均可到達(dá)終點(diǎn),模擬計(jì)算機(jī)中走迷宮的過程,用矩陣存儲迷宮圖,如上圖2。2.3 、問題求解定義初始化條件,設(shè)輸入起點(diǎn)(0,0),終點(diǎn)(4,4),定義空隊(duì)列Q=,表示當(dāng)前無可行點(diǎn);得到輸出路徑隊(duì)列Qp;算法執(zhí)行過程如下:首先起點(diǎn)加入隊(duì)列Q=(0,0);其次取出隊(duì)列Q中頭結(jié)點(diǎn)Vn,Vn=(0,0),Vn加入隊(duì)列Qp=(0,0);Q=;然后取出Vn所有相鄰節(jié)點(diǎn),判斷:相鄰節(jié)點(diǎn)需滿足未被訪問且節(jié)點(diǎn)值不為0;不含終點(diǎn)(4,4),加入隊(duì)列Q,Q=(1,0);重復(fù)以上步驟直至到達(dá)終點(diǎn)。3、 結(jié)語對于迷宮問題求解,除了上文中不含多條出路,不帶環(huán)的簡單迷宮,還有不帶環(huán)的多通路迷宮、帶環(huán)迷宮,均可采用廣度優(yōu)先搜索找到通路3。利用謂詞邏輯尋找迷宮求解策略,需要定義狀態(tài)謂詞及操作符,謂詞邏輯解決迷宮問題可讀性強(qiáng),但是對于復(fù)雜迷宮問題的求解會出現(xiàn)組合爆炸4,5等問題。利用廣度優(yōu)先搜素尋找最短路徑先訪問到的目標(biāo)一定是,層數(shù)最少的即路徑最短的,但也存在一定的局限性,廣度優(yōu)先搜索假定了路和路之間的代價(jià)是相同的。參考文獻(xiàn)1楊科選.人工智能尋路算法及其在游戲中的應(yīng)用研究D.長沙:中南大學(xué),2009.2徐瑛蔚.基于分布式存儲的大規(guī)模圖的深度優(yōu)先搜索算法研究D.沈陽:遼寧大學(xué),2018.3羅敏娜,侍嘯.貪心優(yōu)化的搜索算法在RGV動態(tài)調(diào)度中的應(yīng)用J.沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2019,37(04):315-3