IEEE標準電腦鼠算法的探索與研究

師建軍

[摘 要] 介紹了IEEE標準電腦鼠搜尋最優(yōu)路徑的構思和實現(xiàn)方法，結合相關的軟、硬件設計，使電腦鼠能在多條路徑中選擇最優(yōu)路徑到達終點。

[關 鍵 詞] 最優(yōu)路徑；電腦鼠；算法

[中圖分類號] G433 [文獻標志碼] A [文章編號] 2096-0603（2016）24-0161-01

一、電腦鼠概述

電腦鼠的英文名稱為Micromouse，實際上是一個由微處理器控制的，集感知、判斷、行走功能于一體，能夠自動尋找最佳路徑到達目的地的小型機器人。它可以在“迷宮”中自動感知并記憶迷宮地圖，通過一定的算法，尋找一條最佳路徑，以最快的速度到達目的地。1997年，在美國舉辦了第一屆電腦鼠競賽，隨后，電腦鼠競賽傳入歐洲，首屆歐洲電腦鼠競賽于1980年在倫敦舉辦，之后英國的電腦鼠比賽便由電子工程協(xié)會（IEE）主辦。1980年11月日本電腦鼠協(xié)會（JMA）在東京舉辦了第一屆競賽，此后，日本每年都要舉辦一屆電腦鼠競賽。我國臺灣也于1986年10月舉辦了首屆電腦鼠比賽。現(xiàn)在國際電工和電子工程學會（IEEE）每年都要舉辦一次國際性的電腦鼠走迷宮競賽，各國選手報名踴躍，主要是大學生，為此部分大學還開設了“電腦鼠原理和制作”選修課程。

由于電腦鼠要由參賽選手自己設計制作，不僅要求選手具有嵌入式系統(tǒng)應用、傳感器、控制技術等多方面的知識、經(jīng)驗和實踐能力，還要求具有編寫尋找最佳路徑算法的能力。由于迷宮路徑設置是隨機的，因而競賽難度較大，極富挑戰(zhàn)性。這對培養(yǎng)和提高學生的創(chuàng)新精神和實踐能力有著深遠的意義。

二、算法研究

電腦鼠在第一次進入迷宮時，可以采用全迷宮搜索策略，即將迷宮的所有單元均搜索一次，從中找出最佳的行走路徑。這種策略需要有足夠的時間，在IEEE競賽規(guī)則中每場競賽只有規(guī)定的很短時間，因此，保證電腦鼠順利走完全程是比較困難的。另一種方法是部分迷宮搜索策略，即在有限的時間內(nèi)，只搜索迷宮的一部分，從中找出最佳的路徑。

假如電腦鼠在行走的過程中，進入一條前、左、右都有障礙的道路，則必須掉頭，回到最近的支路，再次選擇新的道路進行搜索，直至找到終點。除此之外，電腦鼠在任一單元內(nèi)，可能的行走方向最多只有三個（前、左、右），如果有兩個或兩個以上的可能行走方向，稱為交叉，遇有交叉時，由于有多個可以行走的方向，在行走方向的選擇上，通常情況下，有以下幾種選擇法則，迷宮搜索流程圖如右圖所示。

右手法則：以右邊為優(yōu)先的前進方向，然后是直線方向、左邊方向。

左手法則：以左邊為優(yōu)先的前進方向，然后是直線方向、右邊方向。

中左法則：以前面為優(yōu)先的前進方向，然后是左邊方向、右邊方向。

中右法則：以前面為優(yōu)先的前進方向，然后是右邊方向、左邊方向。

中心法則：由于終點在迷宮的中心，遇有交叉時，以向迷宮中心的方向為優(yōu)先的前進方向。

三、算法選擇

在整個電腦鼠比賽的過程中，要求電腦鼠要在沒有觸碰，或者觸碰次數(shù)盡量少的情況下，以最短的時間完成由起點到終點的沖刺。因此，路徑的選擇至關重要，步數(shù)少的路徑，是最佳路徑的條件之一，但不是唯一條件。

在比賽過程中，由于比賽的迷宮是未知的，所以我們在選擇電腦鼠的算法時，就勢必要綜合考慮運行時間和支路的情況等。若遇到十字路口多迷宮，如果我們只是單純地選擇右手法則或者左手法則，則電腦鼠在經(jīng)過多個連續(xù)的十字路口，或者其中的一個十字路口時，就有可能會進入死循環(huán)，因為右手法則或者左右法則，最終會讓電腦鼠走一個閉合的環(huán)形路徑，要想避免，就必須在程序中另外調(diào)用子程序來解決這個問題。但如果我們選擇的算法是中心法則，則可以有效地避免上述問題的出現(xiàn)，而且節(jié)省電腦鼠在迷宮中的運行時間。

四、直接到指定坐標程序設計

該程序的目的是讓電腦鼠能夠以最短路徑前進到指定坐標點，當然該功能實現(xiàn)的前提是目的地是電腦鼠已經(jīng)走過且記錄下來的方格。設計該程序的步驟如下：

1.制作以目的地為起點的等高圖。

2.檢查電腦鼠是否已達到目的地，如果是則跳到第7步，否則繼續(xù)順序執(zhí)行。

3.獲取當前坐標的等高值。

4.尋找比當前坐標等高值小的支路方向，且優(yōu)先選擇不需要轉(zhuǎn)彎的方向前進。如果選擇的方向是正前方，則前進步數(shù)cNBlock加一并返回第2步，否則繼續(xù)執(zhí)行。

5.前進cNBlock步，并清零cNBlock。

6.根據(jù)目標方向控制電腦鼠轉(zhuǎn)彎，完成后返回第2步。

7.控制電腦鼠前進cNBlock，任務完成后程序結束。