一種基于A*算法與8數(shù)碼問題的特征映射與估價方法

【摘要】? ? 本文提出一種基于A*算法與8數(shù)碼問題的特征映射與估價模型ENet，將神經(jīng)網(wǎng)絡的思想應用到估價函數(shù)中，使算法本身更具魯棒性和高效性。同時，本文還將構(gòu)筑了一個有關(guān)8數(shù)碼問題的數(shù)據(jù)集ENumbers，并給出一種基于8數(shù)碼問題的算法評價標準。實驗顯示，ENet方法相比其它經(jīng)典方法更加有效，能夠更加精確地擬合A*算法背景下的8數(shù)碼問題，就皮爾遜相關(guān)系數(shù)這一精度指標對經(jīng)典方法提升了約4.025%。

【關(guān)鍵詞】? ? 神經(jīng)網(wǎng)絡? ? 啟發(fā)式搜索? ? 圖搜索? ? 8數(shù)碼問題

引言：

A*算法[1]是在靜態(tài)網(wǎng)絡中求解最短路徑問題下最有效的直接搜索方法之一。作為一種歷史悠久而效率較高的人工智能方法，A*算法自提出以來，已經(jīng)被廣泛應用于諸如防反彈襲擊[2]、機器人的自主無碰行動[3]、物流管理中的車輛問題[4-5]及類似的資源管理資源配置等路徑規(guī)劃與圖搜索問題。

8數(shù)碼問題是一種A*算法的經(jīng)典應用場景與理論探索空間。所謂八數(shù)碼問題起源于一種游戲：將分別標有數(shù)字0，1，2，3，…，8的八塊正方形數(shù)碼牌任意地放在一塊3*3的數(shù)碼盤上。規(guī)定0代表一個可以自由移動的空格，現(xiàn)在要求按照每次只能將與空格相鄰的數(shù)碼牌與空格交換的原則，將擺放完畢的數(shù)碼盤樣式（稱初始狀態(tài)）逐步擺成某種給定的數(shù)碼盤樣式（稱目標狀態(tài)）。如圖1給出了一種8數(shù)碼問題的常見形式。

一、相關(guān)工作

（一）A*算法流程

A*算法[1]是啟發(fā)式搜索中的一個門類，所謂啟發(fā)式搜索，與DFS和BFS這類盲目型搜索最大的不同，就在于當前搜索結(jié)點往下選擇下一步結(jié)點時，可以通過一個啟發(fā)函數(shù)來進行選擇，選擇代價最少的結(jié)點作為下一步搜索結(jié)點而跳轉(zhuǎn)其上（遇到有一個以上代價最少的結(jié)點，不妨選距離當前搜索點最近一次展開的搜索點進行下一步搜索）。而A*算法得以從其它啟發(fā)式搜索中脫穎而出的部分，就在于它的一個估值函數(shù)的設(shè)計上：

f（n）=g（n）+h（n）? ? ? ? ? ? ?   ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

其中f（n）是每個可能試探點的估值，它由兩部分組成：一部分為g（n），它表示從起始搜索點到當前點的代價。另一部分h（n），它表示當前結(jié)點到目標結(jié)點的估值，h（n）設(shè)計的好壞，直接影響A*算法的效率。

（二）關(guān)于8數(shù)碼問題經(jīng)典的估價函數(shù)計算方法

在一般的A*算法8數(shù)碼問題學習過程中，我們通常采用起始狀態(tài)與目標狀態(tài)之間的矩陣差分（matrix differences）來度量距離[9]。在衡量相對簡單的矩陣差異時，矩陣差分法和曼哈頓距離法都擁有相當理想的實驗效果。

然而，很容易發(fā)現(xiàn)的是，這兩種方法在差異點分布較遠的情況下，會給出明顯錯誤的計算結(jié)果。這是因為空間位置的差異未必能夠反應移動所需的步數(shù)，即使矩陣之間看上去只有細微的差別，實際計算的過程中也可能耗費大量的成本。

綜上所述，以上經(jīng)典計算方法雖然擁有在簡單情況下適用的性質(zhì)，然而面對一些特殊情況，它們反而更容易陷入誤判的泥沼。因此，提出一種全新的距離衡量方法，有其必要性與進步性。

二、本文算法研究

（一）8數(shù)碼問題數(shù)據(jù)集及其精度判定標準

首先，為了衡量不同方法在8數(shù)碼問題上的效率和精度，我們構(gòu)筑了一個有關(guān)8數(shù)碼問題的數(shù)據(jù)集ENumbers。該數(shù)據(jù)集由3個文檔文件組成，前兩個文檔文件各有10000行，分別表示初始狀態(tài)與目標狀態(tài)，共包含10000對8數(shù)碼矩陣。第三個文檔則存儲狀態(tài)間的最短距離。

（二）ENet特征映射分類模型

為了改善傳統(tǒng)A*算法與8數(shù)碼問題中廣泛存在的估值函數(shù)誤差大與魯棒性不足等問題，我們利用BP神經(jīng)網(wǎng)絡搭建了ENet深度學習模型，通過多層感知機將原本僅3*3的輸入特征圖映射到1*59049維的高層次特征空間中。再利用降維操作，對高層次特征逐步進行細化分類，最終輸出一個起始狀態(tài)到目標狀態(tài)距離的預測值。

實驗發(fā)現(xiàn)，在實際應用于8數(shù)碼問題時，將矩陣差分法與ENet輸出結(jié)果結(jié)合起來，往往能夠起到更優(yōu)良的效果。在這種情況下，模型的最終輸出結(jié)果可以被表示為：

output（x）=v*ENet（x）+difference（x）-0.5? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中，v為ENet融合權(quán)重，ENet（x）表示ENet的模型輸出，difference（x）表示輸入數(shù)據(jù)使用矩陣差分法得到的輸出值，為平衡二分類模型輸出系數(shù)。

二、實驗分析

本次實驗數(shù)據(jù)集為ENumbers8數(shù)碼問題數(shù)據(jù)集，隨機選取起始狀態(tài)與目標狀態(tài)數(shù)據(jù)7000對進行訓練，另有3000對數(shù)據(jù)按2：1比例隨機劃分為測試集和驗證集，我們將在驗證集上對實驗結(jié)果進行評估和檢測。

（一） 評價指標

其次，考慮到A*算法本身在實現(xiàn)過程中，因數(shù)據(jù)結(jié)構(gòu)的不同和數(shù)據(jù)集大小的限制，我們使用皮爾森相關(guān)系數(shù)來度量模型預測的整體精度，其公式為：

（3）

在這種判斷標準下，前述的兩種方法精度為：

針對本文提出的A*算法數(shù)據(jù)集，我們分別對矩陣差分和曼哈頓距離法進行了皮爾遜相關(guān)系數(shù)測試，實驗發(fā)現(xiàn)曼哈頓距離與實際標簽之間的相關(guān)性較差，而矩陣差分與實際標簽之間具有一定的相關(guān)性，但仍存在較大的改進空間。

（二）實驗參數(shù)設(shè)置

本文的ENet模型使用pytorch架構(gòu)實現(xiàn)，Block Loss采用二分類輸出，實驗采用二分類交叉熵損失函數(shù)，訓練選用Adam優(yōu)化器，設(shè)置初始學習率為5*10^-4，每20次訓練后衰減一次，衰減權(quán)重為0.05.設(shè)置實驗。輸入數(shù)據(jù)為兩個1*9數(shù)碼問題序列。

（三）實驗結(jié)果分析

對模型輸出結(jié)果和矩陣差分法進行復合，其結(jié)果在驗證集上進行評估，使用皮爾遜相關(guān)系數(shù)作為評價標準，可以得到如下圖4的輸出結(jié)果和點陣圖。

五、結(jié)束語

A*算法作為一種經(jīng)典的路徑規(guī)劃與圖搜索算法，在民用領(lǐng)域與軍用領(lǐng)域都有廣泛應用。本文針對A*算法中能夠特定表征知識的啟發(fā)函數(shù)部分，融合先進的神經(jīng)網(wǎng)絡模型，就皮爾遜相關(guān)系數(shù)這一指標對矩陣差分方法提升了約4.025%。同時，本文還提出了關(guān)于8數(shù)碼問題的數(shù)據(jù)集，更新了有關(guān)該問題背景下的判別指標。

作者單位：顧宇軒? ? 安徽大學

參? 考? 文? 獻

[1] Hart P E ， MEMBER， IEEE， et al. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics， 2007， 4（2）：100-107.

[2]楚孟慧， 吳姝瑤. 基于八數(shù)碼問題的搜索算法的研究[J]. 電子制作， 2021（14）：3.

[3]劉建娟，薛禮啟，張會娟，劉忠璞. 融合改進A*與DWA算法的機器人動態(tài)路徑規(guī)劃[J]. 計算機工程與應用， 2021（73-81）.

[4]江洪，姜民.基于變步長A*與車身穩(wěn)態(tài)轉(zhuǎn)向模型的UGV路徑規(guī)劃[J].計算機系統(tǒng)應用，2021，30（10）：240-247.DOI：10.15888/j.cnki.csa.008142.

[5]馮來春， 梁華為， 杜明博，等. 基于A*引導域的RRT智能車輛路徑規(guī)劃算法[J]. 計算機系統(tǒng)應用， 2017， 26（8）：7.

[7]龍振海， 林泓. 8數(shù)碼問題求解算法的改進與實現(xiàn)[J]. 中國高新技術(shù)企業(yè)， 2010（2）：3.

[8]陳萬軍， 梁敏， 于洪志. 人工智能中A*算法的改進及其在8數(shù)碼問題中的應用[J]. 西北民族大學學報：自然科學版， 2003， 24（4）：4.

[9]張信一， 黎燕. 基于A^*算法的八數(shù)碼問題的程序求解[J]. 現(xiàn)代計算機， 2003（5）：5.

[10]胡敏杰. A*算法的探討及其對八數(shù)碼問題的實現(xiàn)[J]. 漳州師范學院學報：自然科學版， 2005（3）：45-50.

[11] Yang L ，? Tian Y ，? Chen Y ， et al. Multi-pattern recognition of sEMG based on improved BP neural network algorithm[C]// 中國控制會議. 2010.

[12]Zhang Y ，? Jing H E ，? Kan X ， et al. Summary of road extraction methods for remote sensing images[J]. Computer Engineering and Applications， 2018.

[13] Jie H ，? Li S ，? Gang S ， et al. Squeeze-and-Excitation Networks[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， PP（99）.

[14]Vaswani A， Shazeer N， Parmar N， et al. Attention is all you need[C]//Advances in neural information processing systems. 2017： 5998-6008.

[15] Kip F? T N ，? Welling M . Semi-Supervised Classification with Graph Convolutional Networks[J].? 2016.