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

李彤

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

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

李彤

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

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

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

1 電腦鼠算法概述

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

2 迷宮信息的存儲(chǔ)

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

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

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

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

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

2.2 尋路算法

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

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

2.3 轉(zhuǎn)彎算法

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

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

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

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

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

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

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

2.4 優(yōu)化算法

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

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

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

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

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

3.2 消除不必要的停頓

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

3.3 去除“傻瓜式”尋路過(guò)程

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

3.4 防止小車(chē)在終點(diǎn)浪費(fèi)時(shí)間

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

3.5 限制探索迷宮的深度

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

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

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

4 結(jié)語(yǔ)

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

［1］周慈航，吳光文.基于嵌入式實(shí)時(shí)操作系統(tǒng)的程序設(shè)計(jì)技術(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)化。