基于八數碼問題的搜索算法對比研究

熱西旦木·吐爾洪太　王慧玲

摘要：文章以八數碼問題為例，對比兩種搜索算法——寬度優先算法和A*算法的性能。在同一初始結點和目標結點的情況下對兩種算法所用步驟、時間和節點數進行比較，通過具體的實驗數據分析，進一步驗證各算法的性能。

關鍵詞：寬度優先算法；A*算法；八數碼問題

中圖分類號：TP18? ? ? 文獻標識碼：A

文章編號：1009-3044（2023）01-0001-03

問題求解是人工智能的核心問題之一，但因所需求解對象多數為難以獲取全部信息的非結構化或結構不良的問題，故而通常無法以既有算法來求解。從問題實際出發，持續尋求可用知識以構造出最小代價的推理路線，最終解決問題的過程被稱為搜索[1]。其中盲目搜索和啟發式搜索在人工智能領域被廣泛使用。前者是以事先預定的控制策略為依據進行搜索，其控制策略不會因搜索過程中所產生的“中間信息”而改變。后者則通過向搜索過程注入與所求問題相關且具有啟發性的信息的方式，持續地將搜索過程引向有望之途，最終獲致最優解。本文采用對比實驗的思路，即對于同一八數碼問題，分別運用屬于盲目搜索的寬度優先算法和屬于啟發式搜索的A*算法進行解決，而后對比驗證盲目和啟發式兩種搜索算法的性能。

1算法描述

1.1寬度優先搜索算法

寬度優先搜索算法（Breadth-FirstSearch，BFS）是一種先生成的節點先擴展的策略。其搜索過程是：從初始節點S0開始逐層向下擴展，在第n層節點還沒有全部搜索完之前，不進入第n+1層節點的搜索[2]。圖1樹狀圖模型說明BFS算法的工作過程及原理。

1）將初始節點S₀放入隊列queue中，標記為已遍歷；

2）從隊列中取出隊列頭的節點S₀，找出與節點S₀鄰接的節點S₁S₂S₃，放入隊列queue中并標記為已遍歷；

3）從queue中取出隊列頭的節點S₁，找出與節點S₁鄰接的節點S₀S₄S₅，由于S₀已遍歷，故排除；標記S₄S₅為已遍歷，然后放入queue中；

4）從queue中取出隊列頭的節點S₂，找出與S₂鄰接的節點S₀S₆S₇，由于S₀已遍歷，排除；標記S₆S₇為已遍歷，然后放入queue中；

5）沿該規律繼續往下，一直到從queue中取出隊列頭的節點S₈，找出與節點S₈鄰接的節點S₃，而S₃屬于已遍歷節點，不作下一步操作；

6）此時隊伍為空，BFS遍歷結束。

1.2A*算法

A*算法由Stanford研究院的PeterHart等人于1968年發表，是目前被廣泛使用的搜索方法[3]。A*算法是以A算法為基礎的啟發式搜索方法。A算法以估計函數f（n）=g（n）+h（n）為依據，賦予諸待擴展節點以順序，進而擇取其中估價值最小者加以拓展。其中ｆ（n）為由S₀（初始節點）出發，經過n（約束節點），最終到達S_g（目標節點）的所有可行路徑中代價最小者的估計值[4]；其中g（n）為由S₀出發抵達n所付出的實際代價；其中h（n）為由n出發，以最優路徑抵達S_g的估價代價。A*算法的估價函數用f（n）=g（n）+h（n）表達，其中g（n）和h（n）是對應于g（n）和h（n）的最小代價，由于f（n）不能預先知道，可以在A算法的基礎上計算得到。A*算法要滿足以下兩個條件：

其一，g（n）表示對最小代價g（n）的估計，且g（n）>0，

其二，h（n）表示最小代價h（n）的下界，即是說對任意節點而言，均有h（n）<=h（n）。

A*算法中需要建立兩個數據結構。其一是用以存放新生成的、尚未得以擴展的節點的Open表（亦稱未擴展節點表），其二是用以存放已然或即將擴展的節點的Closed表（亦稱已擴展節點表）[5]。

A*算法的工作過程及原理：

1） Open表起初只存放初始節點S₀；

2） 查看Open表為空與否，若為空，則意味著問題無解，搜索失?。?/p>

3） 將Open表中首個節點放入Closed表中，并將其標記為已遍歷節點n；

4） 對已遍歷節點n進行檢驗，若恰為目標節點，則意味著找到了問題的解，搜索成功結束；

5） 若節點n無法擴展，則需轉至第二步；

6） 若節點n能夠擴展，則實施拓展以獲得其子節點n_i（i=1，2，...），進而對n_i的估價值f（ni）（i=1，2，...）進行計算，對從子節點到父節點的指針進行設置，而后將其放入Open表中；

7） 將Open表中的所有節點按估價函數值由小到大的順序加以重排；

8） 轉至第二步。

2八數碼問題描述

八數碼問題，也稱九宮格問題，系人工智能狀態搜索問題中的典型。其規則可表述為：在一個縱橫各三路的九宮格棋盤上已擺入八枚棋子，其中每枚棋子以數字1至8為標號，且互不重復。棋盤上尚留有一空格，與其四鄰的棋子皆可以出入空格。對此問題，圖2（a）給出初始狀態，圖2（b）則給出目標狀態。從初始狀態到目標狀態過程中的每次移棋皆應視為空格四鄰的一個棋子（數碼）出入空格。

為了便于描述，每一個狀態用數列來表示，如圖2中初始狀態表示為S₀=283164705，目標狀態表示為S_g=123804765或123456780。

八數碼問題的可解性。事實上只有部分八數碼問題是有解的，一個八數碼問題有解的前提是其初始狀態數列的逆序數與目標狀態數列的逆序數在奇偶性上一致。具體而言，在由某一八數碼問題引出的數列中任意選取一對數，若這兩個數的序位關系與大小關系相反（序位居先者較大，而序位居后者較?。?，便可稱這兩個數為一個逆序（空格對應的數字0不納入考慮），而該數列中逆序的總數即是逆序數。以圖2為例，其初始狀態數列S₀=283164705中的數對83、31、64、75等均是逆序。通過計算、對比可知，其初始狀態數列S₀的逆序數為11（1+3+1+2+1+3），而其目標狀態數列S_g=123804765的逆序數為7（1+1+2+3），兩者皆是奇數，奇偶性一致。故而圖2所示的八數碼問題有解。

當圖2中的空格向左右移動時，逆序數的大小不會隨之改變；當空格上下移動時，逆序數可能會隨之改變，但變動幅度僅可能為±2，其奇偶性仍保持不變。由此可知，有解八數碼問題中的空格移動所得到的數字排列方式并不影響其是否有解。

3兩種算法在八數碼問題上的性能對比

3.1問題描述

實驗給出幾個用來進行效率對比的變量：節點數：搜索過程中所遍歷的節點總數；估價函數：用來估計節點重要性的函數；時間：搜索程序的運行時間（單位為毫秒，ms），每種搜索過程執行3次，取其平均數作為最終結果時間；步數：從初始節點到目標節點的路徑長度。實驗結果如表1和圖3到圖5所示。

1）兩種算法節點數比較

BFS算法中先生成的節點排在隊列的前面，后生成的節點排在隊列后面，每次取出隊列頭部的節點進行遍歷。

A*算法中設估價函數f（n）=d（n）+w（n），其中g（n）=d（n），為每一個節點的深度，由于d（n）>=0，其滿足A*算法的第一個條件，h（n）=w（n）為“不在位”的數碼個數，可以得出至少要移動w（n）步才能達到目標，顯然有w（n）<=h（n），滿足A*算法的第二個限制條件。搜索過程從所有待遍歷節點中選擇估值最小的一個節點進行擴展。

2）A*算法估價函數的改進

對于八數碼問題，如果把不在位的數碼個數作為估價函數，不足以描述該節點到目標節點的路徑長度，因此本文對A*算法的估價函數進一步改進，取另一種啟發式函數f（n）=d（n）+p（n）來描述兩個狀態節點之間的差距，其中d（n）為每一個節點的深度，跟上例一致，p（n）定義為每一個數碼與其目標位置之間距離（不考慮夾在其間的數碼）的總和，可以斷定至少要移動p（n）步才能到達目標節點，因此有p（n）<=h（n），即滿足A*算法的第二個限制條件。使用改進了的估價函數對圖4中的八數碼問題進行遍歷，能夠取得更好的搜索效果。其搜索過程所得到的搜索樹如圖5所示。

3）兩種算法所耗步驟與時間比較

選擇不同的初始節點，分別采用BFS算法、A*算法和改進后的A*算法進行遍歷，求出達到目標節點的步數和搜索程序的運行時間。

3.2結果分析

由圖3和圖4可知，盡管通過BFS能夠找到問題的最優解，但該算法所產生的節點數將遠超過A*算法。其原因在于，A*算法在搜索過程中可以忽略一部分節點的遍歷，而BFS則不能。特別是當某一八數碼問題的初始狀態與目標狀態差距較大時，BFS將產生更多的無用節點。從表1可知，從同一個初始節點出發，分別采用BFS與A*算法，兩者到達目標節點所用的步數數目相同，但所耗的時間卻不一樣，由于A*算法訪問的節點數較少，所耗時間會更短。雖然BFS算法能夠保證在搜索樹中找到一條通向目標節點的最短路徑，但其時間和空間復雜度都比較高。因此，對于復雜的搜索問題A*算法更具有針對性，可以縮小搜索范圍，并提高搜索效率。從圖5可以看出對A*算法估價函數進行優化后遍歷的節點數為11個，比改進之前的遍歷節點減少了2個，雖然空間利用率與A*算法差距不大，但從表1可以看出改進后的A*算法時間復雜度更低。因此A*算法如果針對具體的問題能選擇最為合理的估價函數，可以進一步提高搜索的效率。

參考文獻：

[1] 王萬森.人工智能原理及其應用[M].2版.北京：電子工業出版社，2007.

[2] 曹剛.基于迷宮問題寬度優先捜索算法解析[J].華夏教師，2018（34）：29-30.

[3] 熊偉，張仁平，劉奇韜，等.A*算法及其在地理信息系統中的應用[J].計算機系統應用，2007，16（4）：14-17．

[4] 楊璐，汪博涵，張雪潔.基于A*算法的AGV路徑規劃研究[J].公路與汽運，2014（4）：47-49.

[5] 陳巖，李濤，印明昂.基于改進A*算法的管路自動敷設研究[J].兵器裝備工程學報，2018，39（10）：91-95，104.

【通聯編輯：代影】