一種電腦鼠走迷宮算法

周杰

摘要：該文通過對電腦鼠走迷宮算法的研究，提出了一種電腦鼠走迷宮算法，該算法引用了斜線K和Z用以更新期望坐標(biāo)，并將迷宮分割為多個部分，以斜線K上的點為起點坐標(biāo)，下一條斜線K上的點為期望終點坐標(biāo)，找到起點坐標(biāo)和終點坐標(biāo)的最優(yōu)解，以局部最優(yōu)，引出全局最優(yōu)找到最佳路徑，并與傳統(tǒng)走迷宮算法進(jìn)行比較，提高了迷宮搜索效率。

關(guān)鍵詞：迷宮；斜線；局部最優(yōu)；最佳路徑

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）03-0053-03

1 概述

電腦鼠是一種機(jī)電一體化裝置，是由單片機(jī)、傳感器、機(jī)電運動部件組成的一種能在迷宮行走的小型機(jī)器人可以通過預(yù)先設(shè)定的算法，探索迷宮，可以找到一條從預(yù)設(shè)的起點到終點的最佳路徑，運行環(huán)境是由一個16X16正方形單元格所組成的迷宮，其中單元格的大小為18cmX18cm，文獻(xiàn)[1][2]給出了電腦鼠走迷宮的相關(guān)規(guī)則，每一個單元格有相應(yīng)的擋板組成，電腦鼠的目的是在最短的時間內(nèi)找到出口，在整個電腦鼠中最重要的是硬件的可靠性和算法的優(yōu)劣，在當(dāng)今單片機(jī)迅速發(fā)展的時代，硬件穩(wěn)定性上已經(jīng)趨于穩(wěn)定，本文主要研究和設(shè)計搜索迷宮算法，并提出了一種電腦鼠搜索迷宮的算法。

2 迷宮環(huán)境建模

電腦鼠不具有思維能力，它只能按照我們設(shè)定的算法運行，因此需要模擬現(xiàn)場運行環(huán)境[6][7].

構(gòu)建一個16X16的迷宮，迷宮的水平方向為Y軸，垂直方向為X軸，第一個坐標(biāo)為（1，1），那么依次下去最上角的坐標(biāo)為（16，16）。迷宮構(gòu)建圖，如圖1 所示，迷宮內(nèi)的擋板信息未知。

假設(shè)起點為（1，1）終點為（16，16），現(xiàn)在規(guī)定，X方向為地理北，Y方向為地理南，如圖2所示。

對于當(dāng)前坐標(biāo)，和下一步目標(biāo)，兩個坐標(biāo)的差值比如（X1，Y1）-（X2，Y2）。

（1，0）表示電腦鼠向北前進(jìn)一步。其中差值（0，1）表示向東前進(jìn)一步，（-1，0）表示向南前進(jìn)一步，（0，-1）表示向西前進(jìn)一步。從起點為其構(gòu)造如圖所示的切線Z1，如圖3所示，Z2一直到Zn，總是希望以最短的路徑由一條斜線到達(dá)另外斜線上的坐標(biāo)，然后以該點為起始點總是希望以最短的路徑到達(dá)下一條斜線上的坐標(biāo)，依次尋找下去，就可以找到從起點到達(dá)終點的路徑由于每次選取的都是兩條斜線之間行走的步數(shù)是最短的，然后記錄下行走的路徑，處理掉重復(fù)的路徑，因此能找到，起點到終點的最佳路徑。

3 搜索迷宮算法

3.1 迷宮特殊情況

搜索迷宮，找到最短路徑的方法分為以下幾種基本情況：

理想情況：起點（1，1），終點（16，16）兩點之間直線最短，以先搜索左上迷宮為原則，那么希望走過的路徑為（1，1）（2，2）（3，3）（4，4）（5，5）（6，6）……（16，16），但是對于迷宮，迷宮的每一個格子都有相應(yīng)的擋板信息，不能走直線，起始坐標(biāo)為（1，1），下一步希望到達(dá)（2，2），但是由于（2，2）-（1，1）的權(quán)值為2，在迷宮里如果兩個坐標(biāo)相減權(quán)值大于1那么意味著不能直接到達(dá)，以兩點之間距離最短的原則進(jìn)行最佳路徑選擇，現(xiàn)在人為的規(guī)定最佳路徑如圖4所示：

路徑（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16）為最佳路徑，現(xiàn)以（1，1）為起點，那么下一步它需要到達(dá)（2，1），而（2，1）-（1，1）權(quán)值為1能一步到達(dá)，差值可以表示為（1，0），（1，0）表示電腦鼠向北前進(jìn)一步。其中差值（0，1）表示向東前進(jìn)一步，（-1，0）表示向南前進(jìn)一步，（0，-1）表示向西前進(jìn)一步。如果能到達(dá)（2，1），那么起點就是（2，1），那么下一步要到達(dá)（2，2）則（2，2）和（2，1）的差值為（0，1）電腦鼠右轉(zhuǎn)探測，前面是否有擋板，如沒有擋板，前進(jìn)一格到達(dá)（2，2），依次下去，如果理想狀態(tài)下，就能按照我們預(yù)設(shè)的最佳路徑（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16）到達(dá)終點。

特殊情況1：迷宮是隨機(jī)的，擋板信息也是隨機(jī)的，理想狀態(tài)下的路徑肯定無法達(dá)到，當(dāng)遇到以下情況時為情況1處理.

此時從（1，1）出發(fā)目的是想到達(dá)（2，2），規(guī)定了行走路線是（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16），借助（2，1），此時將到達(dá)（2，1），是當(dāng)想到目達(dá)（2，2）的時候，（2，2）-（2，1）值為（0，1），表示向東行走一步，此時電腦鼠傳感器掃描，發(fā)現(xiàn)前面有擋板不能直接到達(dá)。

那么此時如圖6所示我們畫出一條斜線Z1，此時Z1通過三個點（3，1），（2，2），（1，3）。發(fā)現(xiàn)這三個點的橫縱坐標(biāo)之和是相等的值為4。當(dāng)發(fā)現(xiàn)下一步期望坐標(biāo)（2，2）無法直接到達(dá)時，找到和它橫縱坐標(biāo)之和相等的點，而此時電腦鼠在（2，1），用（3，1），（1，3）與（2，1）相減得到一個權(quán)值，選取權(quán)值最小的坐標(biāo)來代替目的坐標(biāo)即用（3，1），來代替（2，2）來作為下一步目標(biāo)那么，人為的規(guī)定最佳路徑也隨之改變。

假設(shè)現(xiàn)在到達(dá)了（3，1），那么（3，1）將作為我們的起點坐標(biāo)相應(yīng)的最佳路徑就更改為：（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（5，3）……（15，14）（16，15）（16，16）。下一步期望坐標(biāo)更改為（4，2）借助（4，1）。

特殊情況2：遇到以下情況時為情況2處理。

迷宮是隨機(jī)的，行進(jìn)過程中可能會遇到死區(qū)，比如特殊情況1，電腦鼠到達(dá)了（3，1），那么（3，1）將作為我們的起點坐標(biāo)相應(yīng)的最佳路徑就更改為（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（5，3）……（15，14）（16，15）（16，16）。下一步期望坐標(biāo)更改為（4，2）借助（4，1），掃描迷宮，成功到達(dá)（4，2），下一步希望到達(dá)（5，3）借助（5，2），發(fā)現(xiàn)（5，2）不能直接到達(dá)，于是舍棄找到它關(guān)于K3對稱得點（4，3），借助（4，3）到達(dá)，如果（4，3）能到達(dá)，再掃描能否經(jīng)過（4，3）到達(dá)（5，3），能到達(dá)就繼續(xù)下一步，如果不能到達(dá)就找到和（5，3）權(quán)值相等的坐標(biāo)，從權(quán)值相等的坐標(biāo)中找到差值為1的（4，4），掃描能否到達(dá)，能到達(dá)，更新路徑繼續(xù)掃描。

特殊情況3：遇到以下情況時為情況3處理.

假設(shè)電腦鼠到達(dá)（4，2），掃描（4，2）發(fā)現(xiàn)，既不能到達(dá)（5，2） 也不能到達(dá)（4，3），退回這時候的起點坐標(biāo)（3，1）掃描右側(cè)，看能否到達(dá)，如果能，就前進(jìn)到（3，2），這時候不以（4，2）作為目標(biāo)，而是從權(quán)值相等的坐標(biāo)里面，找到能一步到達(dá)的點，如果有則到達(dá)，如果不能到達(dá)，則返回上一步起點。

特殊情況4：當(dāng)行進(jìn)到某一點發(fā)現(xiàn)下一步目標(biāo)不可達(dá)，這時查找和它權(quán)值相等的坐標(biāo)，發(fā)現(xiàn)斜線上只有一點時，斜線上的坐標(biāo)即為終點坐標(biāo)。此時起點坐標(biāo)為（7，5）下一步希望到達(dá)（8，6）但是借助（8，5），，與掃描能否到達(dá)，發(fā)現(xiàn)不能到達(dá)，這時找到和其對稱點（7，6）發(fā)現(xiàn)可以到達(dá)，電腦鼠到達(dá)（7，6），希望到達(dá)（8，5）發(fā)現(xiàn)不可達(dá)，這時找到與（8，6）權(quán)值相等的坐標(biāo)，發(fā)現(xiàn)斜線上只有一點（7，7），以該點為下一步坐標(biāo)，掃描發(fā)現(xiàn)有擋板不能到達(dá)，由于（7，7）是終點坐標(biāo)，于是找到（7，6）的對稱點（6，7）需要借助（6，6）發(fā)現(xiàn)無擋板，電腦鼠到達(dá)（6，6）再經(jīng)過（6，7）到達(dá)（7，7）

3.2 完成迷宮搜索

將16*16的迷宮縮小為8*8迷宮進(jìn)行模擬，根據(jù)設(shè)定的規(guī)則以（1，1）為起點（8，8）為終點，將電腦鼠放在起點坐標(biāo)，車頭向北，這時候人為規(guī)定行走路徑為：（1，1）（2，1）（2，2）（3，2）（3，3（4，3）（4，4）（5，4）（5，5）（6，5）（6，6）（7，6）（7，7）（8，7）（8，8），現(xiàn)在電腦鼠在坐標(biāo)（1，1），下一步希望到達(dá)（2，1），坐標(biāo)（2，1）-（1，1）為（1，0），表示往北前進(jìn)一步，此時傳感器掃描擋板，發(fā)現(xiàn)可行，電腦鼠到達(dá)（2，1），下一步希望到達(dá)坐標(biāo)（2，2），坐標(biāo)（2，2）-（2，1），表示往東走，傳感器掃描擋板信息，發(fā)現(xiàn)（2，2）不能直接到達(dá)，此時為特殊情況1，將對期望坐標(biāo)（2，2）修改為（3，1），路徑行走路線重新修改，修改路線方法為平移，修改后的坐標(biāo)的橫坐標(biāo)比原坐標(biāo)大1平移（1，-1），如果修改后的坐標(biāo)的縱坐標(biāo)比原坐標(biāo)大1平移（-1，1），走過的和超出界限的不做修改如（1，1）（8，8），修改后的坐標(biāo)為（1，1）（2，1）（3，1）（4，1）（4，2）（5，2（5，3）（6，3）（6，4）（7，4）（7，5）（8，5）（8，6）（8，7）（8，8），此時電腦鼠行進(jìn)到（5，2），期望的下一步（5，3）不能到達(dá)，于是找到Z斜線上的替代坐標(biāo)，同樣為情況1，更新起點坐標(biāo)為（6，2），那么路線更改為（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（6，2）（7，2）（7，3）（8，3）（8，4）（8，5）（8，6）（8，7）（8，8）。電腦鼠到達(dá)（6，2），下一步希望到達(dá)（7，2），掃描擋板信息，發(fā)現(xiàn)（7，2）不可達(dá)，此時為情況2，找到（7，2）對稱點（6，3），到達(dá)坐標(biāo)（7，3），按照情況1，2處理，電腦鼠到達(dá)（7，7）情況4處理，，最后到達(dá)（8，8），找到了終點坐標(biāo)。記錄下行走路徑為（1，1）（2，1）（3，1）（4，1）（4，2）（5，2）（6，2）（6，3）（7，3）（7，4）（7，5）（7，6）（7，7）（8，7）（7，7）（7，8）（8，8）。

4 結(jié)論

本文設(shè)計了一種走迷宮的算法，從起點坐標(biāo)開始每次找到下一條斜線Z上的點的最佳路徑，有局部的最優(yōu)構(gòu)造出全局的最優(yōu)，電腦鼠走迷宮有經(jīng)典的，右手法則，左手法則，中左法則，中右法則[3][4][5]與傳統(tǒng)算法作比較如表1所示：

本文提出的算法有效地提高了電腦鼠對整個迷宮的探索，以局部最優(yōu)完成全局最優(yōu)的探索。下一步研究計劃對各類特殊迷宮進(jìn)行測試，以及電腦鼠從終點返回起點的路徑探索。

參考文獻(xiàn)：

[1] 周立功.IEEE電腦鼠開發(fā)指南[M].廣州：廣州致遠(yuǎn)電子有限公司，2008.

[2] IEEE 國際電工和電子工程學(xué)會.IEEE 電腦鼠（迷宮）競賽規(guī)則和介紹 .嵌入之夢 [EB/OL].htttp：//www.embedream.com/ xgzl/2007-08-28/24.html.

[3] 賀少波.基于向心法則的電腦鼠走迷宮算法設(shè)計與優(yōu)化[J].計算機(jī)系統(tǒng)應(yīng)用，2012，21（9）.

[4] 王鳳林.一種電腦鼠走迷宮算法的設(shè)計與實現(xiàn)[J].計算機(jī)應(yīng)用與軟件，2010，27（12）：270-273.

[5] 郭長生 ， 龔濤 ，李龍.一種電腦鼠走迷宮搜索算法[J].華中科技大學(xué)學(xué)報：自然科學(xué)版， 2013 ， 41 （s1） ：388-391.

[6] 王斌，張衛(wèi)鋼.基于IEEE標(biāo)準(zhǔn)的電腦鼠走迷宮的智能算法研究[J].電子設(shè)計工程，2011，19（12）：42-45.

[7] 張新誼.一種電腦鼠走迷宮的算法[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2007（5）：84-85.