電腦鼠算法優(yōu)化分析

李彤

（天津渤海職業(yè)技術(shù)學(xué)院，天津 300000）

電腦鼠算法優(yōu)化分析

李彤

（天津渤海職業(yè)技術(shù)學(xué)院，天津 300000）

電腦鼠是由微處理器控制的集感知、判斷、行走功能于一體的小型機器人，其可以在“迷宮”中自動感知并記憶迷宮地圖，以最快的速度到達(dá)目的地。基于此，針對電腦鼠算法進(jìn)行優(yōu)化分析。

電腦鼠算法；微處理器控制；路徑選擇法則；自動搜索

1 電腦鼠算法概述

電腦鼠走迷宮可采用全迷宮探索策略，即將迷宮所有單元均搜索一次，從中找出最佳行走路徑。這種策略需要有足夠的時間或探測次數(shù)，但在IEEE競賽規(guī)則中每場競賽只有15min，因此是不可能的。另一種方法是部分迷宮探索策略，即在有限的時間或探測次數(shù)下，只探測迷宮的一部分，從中找出次最佳的路徑，顯然只能采用這種策略。

2 迷宮信息的存儲

因為迷宮分為16×16=256個方格，所以很直觀地可以想到用一個二維矩陣來存儲一個迷宮的信息，矩陣中的每一個元素用于存儲地圖中一個方格的信息，矩陣每個元素可以定義成Byte型，只用其中的4位就可以存儲方格四面的擋板信息。要獲取某一個方格單個方向的擋板信息，只需做一個簡單的運算看結(jié)果是否為0即可。

2.1 數(shù)據(jù)的存儲方式

絕對方向和相對方向的變換：假設(shè)數(shù)值0、1、2、3分別表示絕對方向的上、右、下、左，那么就用0、1、2、3中的其中一個數(shù)值來表示當(dāng)前小車車頭朝向的方向，當(dāng)然這個數(shù)值是動態(tài)變化的，其實轉(zhuǎn)化的規(guī)則相當(dāng)簡單，右轉(zhuǎn)方向數(shù)值加1，左轉(zhuǎn)方向數(shù)值加3，后轉(zhuǎn)方向數(shù)值加2，當(dāng)然可能有越界的情況。所以，得出的方向數(shù)值再進(jìn)行模運算對4取余數(shù)得出的結(jié)果，就是轉(zhuǎn)彎后小車的車頭所面向的方向的數(shù)值。通過矩陣可以找到當(dāng)前的小車方向和轉(zhuǎn)彎后的小車方向的對應(yīng)關(guān)系，得出的相對方向和絕對方向的轉(zhuǎn)換公式如下所示［1］：

轉(zhuǎn)彎后的絕對方向=（轉(zhuǎn)彎前的絕對方向+轉(zhuǎn)彎數(shù)值）%4

小車的車頭方向一般是用一個全局變量來存儲的，方便在轉(zhuǎn)彎的函數(shù)中進(jìn)行修改，避免C語言中一些作用域的問題。

2.2 尋路算法

尋路是小車在運行的整個過程中進(jìn)行的第一個操作，目的是讓小車在迷宮中探索，同時記錄已經(jīng)走過的路徑信息，直到小車找到終點就可以結(jié)束探索尋路的過程。當(dāng)然也可以在找到終點后繼續(xù)探索整個迷宮，盡可能多地收集迷宮的信息，以便后期進(jìn)行最短路徑分析計算時能夠運用更多的信息，找到更佳的最短路徑，得到更好的成績。

尋路算法的2個關(guān)鍵點如下。一是在岔路口的轉(zhuǎn)彎策略以及小車運行的穩(wěn)定性。轉(zhuǎn)彎策略決定了從小車開始運行到找到終點的時間長短。良好的轉(zhuǎn)彎尋路策略可以大量減少不必要的尋路時間。小車運行的穩(wěn)定性對于尋路過程也十分重要，所以小車的行進(jìn)和轉(zhuǎn)彎的過程一定要在機械和軟件方面都調(diào)節(jié)到最穩(wěn)定的狀態(tài)。二是正確使用堆棧，整個選路算法的運行過程中會大量地使用堆棧的入棧和出棧操作，如果對入棧和出棧的條件判斷不正確，有可能造成數(shù)據(jù)紊亂，最好使用調(diào)試版上的數(shù)碼管實時顯示堆棧棧頂?shù)臄?shù)據(jù)，發(fā)現(xiàn)有錯誤就在程序中尋找錯誤，直到整個尋路算法穩(wěn)定為止。

2.3 轉(zhuǎn)彎算法

在尋路過程中，如果小車遇到迷宮中的岔路口時，應(yīng)該考慮選擇哪個方向繼續(xù)探索。常規(guī)的策略有右手法則、左手法則、優(yōu)先向前法則、向心法則等。

2.3.1 右手法則。小車在搜過程中有2個以上的搜索方向時，優(yōu)先選擇向右轉(zhuǎn)，其次是向前行進(jìn)，最后才考慮向左轉(zhuǎn)彎。

2.3.2 左手法則。小車在搜過程中有2個以上的搜索方向時，優(yōu)先選擇向左轉(zhuǎn)，其次是向前，最后向右。

2.3.3 優(yōu)先向前法則。優(yōu)先向前行進(jìn)不轉(zhuǎn)彎，然后考慮向左或向右可自行設(shè)定。

2.3.4 隨即策略。在可前進(jìn)的方向中隨機選擇一個前進(jìn)，沒有什么規(guī)律可循。

上述的策略都有一個共同的缺陷，就是在選擇轉(zhuǎn)彎方向時，沒有考慮小車當(dāng)前在迷宮的哪個位置，一味地調(diào)用一種尋路策略都是不科學(xué)的。

2.3.5 向心法則。把整個16×16的迷宮地圖分解為左下、右下、左上、右上4個均等的區(qū)域，在不同的區(qū)域中選擇不同的轉(zhuǎn)彎策略，使得小車始終向著迷宮的中心靠近，這樣就可以以最快的速度接近終點。

2.4 優(yōu)化算法

在電腦鼠的尋路過程中有一個比較特殊的過程，就是在小車遇到死胡同時，應(yīng)讓小車回到上一個岔路口，換言之，需要實現(xiàn)將小車從當(dāng)前的位置移動到一個指定的任意位置，而且還要使得移動過程經(jīng)歷的路徑盡可能短。后期最短路徑的生成問題其實是上述問題的一個特例，僅把當(dāng)前位置設(shè)為了迷宮起點，把要達(dá)到的位置設(shè)為中點。

綜上所述，只需要集中精力解決上述第一個問題即可，即怎樣從當(dāng)前的位置尋找一條最短的路徑到達(dá)一個指定的任意位置。要實現(xiàn)上面的功能，就需要用到等高表。等高表是以一個二維矩陣的形式表現(xiàn)的，對于16×16的迷宮地圖而言，可以開辟一個16×16的二維矩陣來表示等高表，數(shù)值類型選擇Byte型就夠用了，等高表中的每一項對應(yīng)迷宮每一個方格，用于存儲起點到該方格最短路徑。

3 軟件中可改進(jìn)的部分優(yōu)化建議

3.1 直接到指定的坐標(biāo)

控制小車直接從當(dāng)前的坐標(biāo)到一個指定的坐標(biāo)是整個軟件設(shè)計中要實現(xiàn)的最為關(guān)鍵的功能，在尋路的過程中涉及到頻繁地回到以前所經(jīng)歷的岔路口的過程，這就是一個從當(dāng)前坐標(biāo)移動到指定坐標(biāo)的典型情況，還有從起點到終點的沖刺過程其實是一句代碼完成的，就是將迷宮的起點作為小車的運行起點，將迷宮的終點作為小車運行的終點來調(diào)用這個關(guān)鍵的功能。該功能的實現(xiàn)要用到迷宮的等高表信息。

3.2 消除不必要的停頓

在出廠代碼試跑中，小車每到一個岔路口就會停頓一下，然后再重新加速前進(jìn)。根據(jù)上次比賽對代碼的分析，出現(xiàn)這種現(xiàn)象的原因在于出廠示例代碼的架構(gòu)安排不合理，出場的示例代碼中小車的前進(jìn)和在岔路口是否轉(zhuǎn)彎的判斷是分離的，所以小車每到一個岔路口，程序就會從控制前進(jìn)的函數(shù)跳回到主函數(shù)中進(jìn)行是否需要轉(zhuǎn)彎的判斷，然后轉(zhuǎn)彎后又跳回到控制前進(jìn)的函數(shù)中運行程序。這樣就造成了不必要的停頓。其實在岔路口是否轉(zhuǎn)彎應(yīng)在控制前進(jìn)的函數(shù)結(jié)束前判斷，不需要跳回主函數(shù)進(jìn)行正以上缺陷的方法是增加控制前進(jìn)的子過程的返回條件，在不需要轉(zhuǎn)彎的岔路口不跳出前進(jìn)的子路程即可。

3.3 去除“傻瓜式”尋路過程

在出廠實例代碼的試跑過程中，發(fā)現(xiàn)其尋路過程效率非常低，經(jīng)常在一些三面都有擋板的單個方格間打轉(zhuǎn)，其原因是因為沒有進(jìn)行數(shù)據(jù)補全，迷宮里方格的信息，通過推斷方法也可以得到，利用某個方格四周方格的信息，就有可能推斷出這個方格的信息。

3.4 防止小車在終點浪費時間

普通的代碼中并沒有在小車到達(dá)終點之后進(jìn)行特殊的處理，造成小車在終點的4個方格中轉(zhuǎn)一圈才返回終點，這顯然是應(yīng)該改進(jìn)的，需要對終點的判定增加特殊的處理。

3.5 限制探索迷宮的深度

在小車找到終點后，可以繼續(xù)探索迷宮，但是比賽的迷宮有256個方格，全部探索完是相當(dāng)耗時間的，所以需要控制遍歷迷宮的深度，可以通過已經(jīng)探測的方格個數(shù)來衡量迷宮的探測程度，給探測的迷宮方格數(shù)設(shè)置一個上限，在到達(dá)探索的上限后返回迷宮起點，結(jié)束尋路的過程。

3.6 改進(jìn)轉(zhuǎn)彎的模式

傳統(tǒng)的左拐彎和右拐彎都是先讓電機停轉(zhuǎn)，然后一個電機正轉(zhuǎn)，另外一個電機反轉(zhuǎn)實現(xiàn)轉(zhuǎn)彎，電機的停轉(zhuǎn)會浪費很多時間，所以相對而言，沒有電機停轉(zhuǎn)過程的前進(jìn)中拐彎方式是比較理想的轉(zhuǎn)彎方式。

4 結(jié)語

電腦鼠是一個系統(tǒng)工作，在比賽中對光和靜電影響很大，在遇到靜電問題可刷三合油減小對電腦鼠比賽誤差。

［1］周慈航，吳光文.基于嵌入式實時操作系統(tǒng)的程序設(shè)計技術(shù)［M］.北京：北京航空航天大學(xué)出版社，2006.

Optimization Analysis of Computer Mouse Algorithm

Li Tong

（Tianjin Bohai Vocational and Technical College，Tianjin 300000）

The computer mouse is controlled by a microprocessor,and integrates the sensing,judging and walking functions into a small robot.It can automatically sense and memory maze map in the maze,reach the destination at the fastest speed.Based on this,the optimization of computer mouse algorithm was analyzed.

computer mouse algorithm；microprocessor control；path selection rule；automatic search

TP242

A

1003-5168（2017）02-0024-02

2017-01-12

李彤（1988-），男，碩士，助教，研究方向：電腦鼠算法優(yōu)化。