一種電腦鼠走迷宮算法

周杰

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

關鍵詞：迷宮；斜線；局部最優；最佳路徑

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

1 概述

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

2 迷宮環境建模

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

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

假設起點為（1，1）終點為（16，16），現在規定，X方向為地理北，Y方向為地理南，如圖2所示。

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

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

3 搜索迷宮算法

3.1 迷宮特殊情況

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

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

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

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

此時從（1，1）出發目的是想到達（2，2），規定了行走路線是（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），表示向東行走一步，此時電腦鼠傳感器掃描，發現前面有擋板不能直接到達。

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

假設現在到達了（3，1），那么（3，1）將作為我們的起點坐標相應的最佳路徑就更改為：（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處理。

迷宮是隨機的，行進過程中可能會遇到死區，比如特殊情況1，電腦鼠到達了（3，1），那么（3，1）將作為我們的起點坐標相應的最佳路徑就更改為（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），發現（5，2）不能直接到達，于是舍棄找到它關于K3對稱得點（4，3），借助（4，3）到達，如果（4，3）能到達，再掃描能否經過（4，3）到達（5，3），能到達就繼續下一步，如果不能到達就找到和（5，3）權值相等的坐標，從權值相等的坐標中找到差值為1的（4，4），掃描能否到達，能到達，更新路徑繼續掃描。

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

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

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

3.2 完成迷宮搜索

將16*16的迷宮縮小為8*8迷宮進行模擬，根據設定的規則以（1，1）為起點（8，8）為終點，將電腦鼠放在起點坐標，車頭向北，這時候人為規定行走路徑為：（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），現在電腦鼠在坐標（1，1），下一步希望到達（2，1），坐標（2，1）-（1，1）為（1，0），表示往北前進一步，此時傳感器掃描擋板，發現可行，電腦鼠到達（2，1），下一步希望到達坐標（2，2），坐標（2，2）-（2，1），表示往東走，傳感器掃描擋板信息，發現（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），掃描擋板信息，發現（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 結論

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

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

參考文獻：

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

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

[3] 賀少波.基于向心法則的電腦鼠走迷宮算法設計與優化[J].計算機系統應用，2012，21（9）.

[4] 王鳳林.一種電腦鼠走迷宮算法的設計與實現[J].計算機應用與軟件，2010，27（12）：270-273.

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

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

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