一種電腦鼠走迷宮算法

周杰

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）03-0053-03

1 概述

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

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

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

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

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

對于當前坐標，和下一步目標，兩個坐標的差值比如（X1，Y1）-（X2，Y2）。

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

3 搜索迷宮算法

3.1 迷宮特殊情況

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

理想情況：起點（1，1），終點（16，16）兩點之間直線最短，以先搜索左上迷宮為原則，那么希望走過的路徑為（1，1）（2，2）（3，3）（4，4）（5，5）（6，6）……（16，16），但是對于迷宮，迷宮的每一個格子都有相應(yīng)的擋板信息，不能走直線，起始坐標為（1，1），下一步希望到達（2，2），但是由于（2，2）-（1，1）的權(quán)值為2，在迷宮里如果兩個坐標相減權(quán)值大于1那么意味著不能直接到達，以兩點之間距離最短的原則進行最佳路徑選擇，現(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）為起點，那么下一步它需要到達（2，1），而（2，1）-（1，1）權(quán)值為1能一步到達，差值可以表示為（1，0），（1，0）表示電腦鼠向北前進一步。其中差值（0，1）表示向東前進一步，（-1，0）表示向南前進一步，（0，-1）表示向西前進一步。如果能到達（2，1），那么起點就是（2，1），那么下一步要到達（2，2）則（2，2）和（2，1）的差值為（0，1）電腦鼠右轉(zhuǎn)探測，前面是否有擋板，如沒有擋板，前進一格到達（2，2），依次下去，如果理想狀態(tài)下，就能按照我們預設(shè)的最佳路徑（1，1）（2，1）（2，2）（3，2）（3，3）（4，3）（4，4）……（16，15）（16，16）到達終點。

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

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

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

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

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

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

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

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

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

3.2 完成迷宮搜索

將16*16的迷宮縮小為8*8迷宮進行模擬，根據(jù)設(shè)定的規(guī)則以（1，1）為起點（8，8）為終點，將電腦鼠放在起點坐標，車頭向北，這時候人為規(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)在電腦鼠在坐標（1，1），下一步希望到達（2，1），坐標（2，1）-（1，1）為（1，0），表示往北前進一步，此時傳感器掃描擋板，發(fā)現(xiàn)可行，電腦鼠到達（2，1），下一步希望到達坐標（2，2），坐標（2，2）-（2，1），表示往東走，傳感器掃描擋板信息，發(fā)現(xiàn)（2，2）不能直接到達，此時為特殊情況1，將對期望坐標（2，2）修改為（3，1），路徑行走路線重新修改，修改路線方法為平移，修改后的坐標的橫坐標比原坐標大1平移（1，-1），如果修改后的坐標的縱坐標比原坐標大1平移（-1，1），走過的和超出界限的不做修改如（1，1）（8，8），修改后的坐標為（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），此時電腦鼠行進到（5，2），期望的下一步（5，3）不能到達，于是找到Z斜線上的替代坐標，同樣為情況1，更新起點坐標為（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）。電腦鼠到達（6，2），下一步希望到達（7，2），掃描擋板信息，發(fā)現(xiàn)（7，2）不可達，此時為情況2，找到（7，2）對稱點（6，3），到達坐標（7，3），按照情況1，2處理，電腦鼠到達（7，7）情況4處理，，最后到達（8，8），找到了終點坐標。記錄下行走路徑為（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è)計了一種走迷宮的算法，從起點坐標開始每次找到下一條斜線Z上的點的最佳路徑，有局部的最優(yōu)構(gòu)造出全局的最優(yōu)，電腦鼠走迷宮有經(jīng)典的，右手法則，左手法則，中左法則，中右法則[3][4][5]與傳統(tǒng)算法作比較如表1所示：

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

參考文獻：

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

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

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

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

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

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

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