要制作一個能順利走到迷宮終點，并能按最短路徑回來的小車，重中之重就是尋找其最短路徑的算法，迷宮情況復(fù)雜多變，多個路口交錯縱橫，想要完美的找出最短路徑并不容易，我因此總結(jié)出一套算法，能迅速找出最短路徑，并適用于大多數(shù)迷宮情形，此算法對算力要求不高，不會過多阻礙主程序的運行。

(資料圖)

在小車去終點時，我們規(guī)定小車必須優(yōu)先左轉(zhuǎn)，其次直走，最后右轉(zhuǎn)，用暴力枚舉即可到達終點。在迷宮中，把每一個線段相交的地方稱作結(jié)點，經(jīng)過總結(jié)，共有十字結(jié)點，正T型結(jié)點，左T型結(jié)點，右T型結(jié)點四種結(jié)點，大多數(shù)傳統(tǒng)算法要求對每一個結(jié)點進行精準分類再分別處理，而此算法能對不同類型的結(jié)點進行統(tǒng)一處理。

在一個結(jié)點處，小車正對且壓在車身下面的那根線我們稱為點a，其正對著車的左側(cè)的線稱為點b，同理，正對著車前方的直線稱為點c，右側(cè)稱為點d。

把此節(jié)點稱為點A（見下圖），當A為1，稱為無效結(jié)點，A為0，稱為有效節(jié)點，考慮到有多個結(jié)點，所以A，a，b，c，d用數(shù)組表示，每個字母的初始值都為0，數(shù)組下標最大值為100。再設(shè)定一個p統(tǒng)計結(jié)點個數(shù)，初始值為1。此外再設(shè)置一個調(diào)頭結(jié)點N，N為1則已有調(diào)頭動作，否則無。小車去往終點時途經(jīng)每一個結(jié)點都計算一次，在此先介紹我的結(jié)點轉(zhuǎn)向算法。

在遇到結(jié)點時，若車左轉(zhuǎn)，則：若d[p]為1，則a[p]加1，否則若c[p]為1，則d[p]加1，否則若b[p]為1，則c[p]加1，否則若a[p]為1，則b[p]加1。稱此為左側(cè)結(jié)點轉(zhuǎn)向法。

在遇到結(jié)點時，若車直走，則：若b[p]為0，則c[p]加1，否則若c[p]為0，則d[p]加1，否則若d[p]為0，則a[p]加1。稱此為前側(cè)結(jié)點轉(zhuǎn)向法。

在遇到結(jié)點時，計算方法為：（小車在調(diào)頭動作完成后，N置1）當小車駛到一個任意結(jié)點時，若N為1，則判定此節(jié)點為原結(jié)點，p不變，此時轉(zhuǎn)向時再根據(jù)情況同理調(diào)用結(jié)點轉(zhuǎn)向法，此時p為p，完成轉(zhuǎn)向算法后將N置0。

否則若N為0，若A[p-1]為2，則判定此結(jié)點為已過結(jié)點，p不變此時轉(zhuǎn)向時繼續(xù)根據(jù)情況調(diào)用結(jié)點轉(zhuǎn)向法，此時p為p-1，完成轉(zhuǎn)向算法后將A[p]置為0，為無效結(jié)點。

否則，則立即將a置1，此時結(jié)點狀態(tài)為新節(jié)點，p加1，A[p]置為1，為有效節(jié)點，此時若車左側(cè)有線，則調(diào)用左側(cè)結(jié)點轉(zhuǎn)向法，否則調(diào)用前側(cè)結(jié)點轉(zhuǎn)向法，此時p為p。

以上述算法走到終點時，已將所走過的每個結(jié)點都歸納到算法中，每個小車已走過的結(jié)點都有屬于自己的值，用另一套算法逐個處理結(jié)點值即可計算出最短路徑。

在小車回起點時，我們拋棄原有的一切算法，另起爐灶，此時要先把所有有效節(jié)點剝離出來，然后按從終點到起點的順序?qū)⒂行Ч?jié)點存到一個數(shù)組中，在這里先介紹我的第三種算法。

在遇到結(jié)點時，若此結(jié)點d為1，則左轉(zhuǎn)，否則若c為1，則直走，否則若b為1，則右轉(zhuǎn)，我稱此為結(jié)點回溯法，

由此算法可順利回到起點。因為在每一個結(jié)點計算一次，統(tǒng)一計算再運行，故而此算法對算力要求低，占用運行內(nèi)存少，運算速度極短，不會影響其他程序的運行。

總結(jié)來說，由結(jié)點轉(zhuǎn)向算法和結(jié)點回溯法即可完美走完迷宮。

但此算法可靈活處理至二級結(jié)點，對于處理n級結(jié)點寫死即可，因此我優(yōu)化了此算法，使其可靈活處理n個結(jié)點，算法雖簡單，但寫代碼實踐時，其中也有許多細節(jié)需要處理，但由于篇幅限制，至此不做過多贅述。

免責聲明：以上內(nèi)容為本網(wǎng)站轉(zhuǎn)自其它媒體，相關(guān)信息僅為傳遞更多信息之目的，不代表本網(wǎng)觀點，亦不代表本網(wǎng)站贊同其觀點或證實其內(nèi)容的真實性。如稿件版權(quán)單位或個人不想在本網(wǎng)發(fā)布，可與本網(wǎng)聯(lián)系，本網(wǎng)視情況可立即將其撤除。