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

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

引言：

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

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

一、相關(guān)工作

（一）A*算法流程

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

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

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

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

在一般的A*算法8數(shù)碼問(wèn)題學(xué)習(xí)過(guò)程中，我們通常采用起始狀態(tài)與目標(biāo)狀態(tài)之間的矩陣差分（matrix differences）來(lái)度量距離[9]。在衡量相對(duì)簡(jiǎn)單的矩陣差異時(shí)，矩陣差分法和曼哈頓距離法都擁有相當(dāng)理想的實(shí)驗(yàn)效果。

然而，很容易發(fā)現(xiàn)的是，這兩種方法在差異點(diǎn)分布較遠(yuǎn)的情況下，會(huì)給出明顯錯(cuò)誤的計(jì)算結(jié)果。這是因?yàn)榭臻g位置的差異未必能夠反應(yīng)移動(dòng)所需的步數(shù)，即使矩陣之間看上去只有細(xì)微的差別，實(shí)際計(jì)算的過(guò)程中也可能耗費(fèi)大量的成本。

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

二、本文算法研究

（一）8數(shù)碼問(wèn)題數(shù)據(jù)集及其精度判定標(biāo)準(zhǔn)

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

（二）ENet特征映射分類(lèi)模型

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

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

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

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

二、實(shí)驗(yàn)分析

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

（一） 評(píng)價(jià)指標(biāo)

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

（3）

在這種判斷標(biāo)準(zhǔn)下，前述的兩種方法精度為：

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

（二）實(shí)驗(yàn)參數(shù)設(shè)置

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

（三）實(shí)驗(yàn)結(jié)果分析

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

五、結(jié)束語(yǔ)

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

作者單位：顧宇軒? ? 安徽大學(xué)

參? 考? 文? 獻(xià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ù)碼問(wèn)題的搜索算法的研究[J]. 電子制作， 2021（14）：3.

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

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

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

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

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

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

[10]胡敏杰. A*算法的探討及其對(duì)八數(shù)碼問(wèn)題的實(shí)現(xiàn)[J]. 漳州師范學(xué)院學(xué)報(bào)：自然科學(xué)版， 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]// 中國(guó)控制會(huì)議. 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.