基于八數(shù)碼問(wèn)題的搜索算法對(duì)比研究

熱西旦木·吐?tīng)柡樘⊥趸哿?/p>

摘要：文章以八數(shù)碼問(wèn)題為例，對(duì)比兩種搜索算法——寬度優(yōu)先算法和A*算法的性能。在同一初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)的情況下對(duì)兩種算法所用步驟、時(shí)間和節(jié)點(diǎn)數(shù)進(jìn)行比較，通過(guò)具體的實(shí)驗(yàn)數(shù)據(jù)分析，進(jìn)一步驗(yàn)證各算法的性能。

關(guān)鍵詞：寬度優(yōu)先算法；A*算法；八數(shù)碼問(wèn)題

中圖分類(lèi)號(hào)：TP18? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2023）01-0001-03

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

1算法描述

1.1寬度優(yōu)先搜索算法

寬度優(yōu)先搜索算法（Breadth-FirstSearch，BFS）是一種先生成的節(jié)點(diǎn)先擴(kuò)展的策略。其搜索過(guò)程是：從初始節(jié)點(diǎn)S0開(kāi)始逐層向下擴(kuò)展，在第n層節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索[2]。圖1樹(shù)狀圖模型說(shuō)明BFS算法的工作過(guò)程及原理。

1）將初始節(jié)點(diǎn)S₀放入隊(duì)列queue中，標(biāo)記為已遍歷；

2）從隊(duì)列中取出隊(duì)列頭的節(jié)點(diǎn)S₀，找出與節(jié)點(diǎn)S₀鄰接的節(jié)點(diǎn)S₁S₂S₃，放入隊(duì)列queue中并標(biāo)記為已遍歷；

3）從queue中取出隊(duì)列頭的節(jié)點(diǎn)S₁，找出與節(jié)點(diǎn)S₁鄰接的節(jié)點(diǎn)S₀S₄S₅，由于S₀已遍歷，故排除；標(biāo)記S₄S₅為已遍歷，然后放入queue中；

4）從queue中取出隊(duì)列頭的節(jié)點(diǎn)S₂，找出與S₂鄰接的節(jié)點(diǎn)S₀S₆S₇，由于S₀已遍歷，排除；標(biāo)記S₆S₇為已遍歷，然后放入queue中；

5）沿該規(guī)律繼續(xù)往下，一直到從queue中取出隊(duì)列頭的節(jié)點(diǎn)S₈，找出與節(jié)點(diǎn)S₈鄰接的節(jié)點(diǎn)S₃，而S₃屬于已遍歷節(jié)點(diǎn)，不作下一步操作；

6）此時(shí)隊(duì)伍為空，BFS遍歷結(jié)束。

1.2A*算法

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

其一，g（n）表示對(duì)最小代價(jià)g（n）的估計(jì)，且g（n）>0，

其二，h（n）表示最小代價(jià)h（n）的下界，即是說(shuō)對(duì)任意節(jié)點(diǎn)而言，均有h（n）<=h（n）。

A*算法中需要建立兩個(gè)數(shù)據(jù)結(jié)構(gòu)。其一是用以存放新生成的、尚未得以擴(kuò)展的節(jié)點(diǎn)的Open表（亦稱(chēng)未擴(kuò)展節(jié)點(diǎn)表），其二是用以存放已然或即將擴(kuò)展的節(jié)點(diǎn)的Closed表（亦稱(chēng)已擴(kuò)展節(jié)點(diǎn)表）[5]。

A*算法的工作過(guò)程及原理：

1） Open表起初只存放初始節(jié)點(diǎn)S₀；

2） 查看Open表為空與否，若為空，則意味著問(wèn)題無(wú)解，搜索失??；

3） 將Open表中首個(gè)節(jié)點(diǎn)放入Closed表中，并將其標(biāo)記為已遍歷節(jié)點(diǎn)n；

4） 對(duì)已遍歷節(jié)點(diǎn)n進(jìn)行檢驗(yàn)，若恰為目標(biāo)節(jié)點(diǎn)，則意味著找到了問(wèn)題的解，搜索成功結(jié)束；

5） 若節(jié)點(diǎn)n無(wú)法擴(kuò)展，則需轉(zhuǎn)至第二步；

6） 若節(jié)點(diǎn)n能夠擴(kuò)展，則實(shí)施拓展以獲得其子節(jié)點(diǎn)n_i（i=1，2，...），進(jìn)而對(duì)n_i的估價(jià)值f（ni）（i=1，2，...）進(jìn)行計(jì)算，對(duì)從子節(jié)點(diǎn)到父節(jié)點(diǎn)的指針進(jìn)行設(shè)置，而后將其放入Open表中；

7） 將Open表中的所有節(jié)點(diǎn)按估價(jià)函數(shù)值由小到大的順序加以重排；

8） 轉(zhuǎn)至第二步。

2八數(shù)碼問(wèn)題描述

八數(shù)碼問(wèn)題，也稱(chēng)九宮格問(wèn)題，系人工智能狀態(tài)搜索問(wèn)題中的典型。其規(guī)則可表述為：在一個(gè)縱橫各三路的九宮格棋盤(pán)上已擺入八枚棋子，其中每枚棋子以數(shù)字1至8為標(biāo)號(hào)，且互不重復(fù)。棋盤(pán)上尚留有一空格，與其四鄰的棋子皆可以出入空格。對(duì)此問(wèn)題，圖2（a）給出初始狀態(tài)，圖2（b）則給出目標(biāo)狀態(tài)。從初始狀態(tài)到目標(biāo)狀態(tài)過(guò)程中的每次移棋皆應(yīng)視為空格四鄰的一個(gè)棋子（數(shù)碼）出入空格。

為了便于描述，每一個(gè)狀態(tài)用數(shù)列來(lái)表示，如圖2中初始狀態(tài)表示為S₀=283164705，目標(biāo)狀態(tài)表示為S_g=123804765或123456780。

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

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

3兩種算法在八數(shù)碼問(wèn)題上的性能對(duì)比

3.1問(wèn)題描述

實(shí)驗(yàn)給出幾個(gè)用來(lái)進(jìn)行效率對(duì)比的變量：節(jié)點(diǎn)數(shù)：搜索過(guò)程中所遍歷的節(jié)點(diǎn)總數(shù)；估價(jià)函數(shù)：用來(lái)估計(jì)節(jié)點(diǎn)重要性的函數(shù)；時(shí)間：搜索程序的運(yùn)行時(shí)間（單位為毫秒，ms），每種搜索過(guò)程執(zhí)行3次，取其平均數(shù)作為最終結(jié)果時(shí)間；步數(shù)：從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度。實(shí)驗(yàn)結(jié)果如表1和圖3到圖5所示。

1）兩種算法節(jié)點(diǎn)數(shù)比較

BFS算法中先生成的節(jié)點(diǎn)排在隊(duì)列的前面，后生成的節(jié)點(diǎn)排在隊(duì)列后面，每次取出隊(duì)列頭部的節(jié)點(diǎn)進(jìn)行遍歷。

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

2）A*算法估價(jià)函數(shù)的改進(jìn)

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

3）兩種算法所耗步驟與時(shí)間比較

選擇不同的初始節(jié)點(diǎn)，分別采用BFS算法、A*算法和改進(jìn)后的A*算法進(jìn)行遍歷，求出達(dá)到目標(biāo)節(jié)點(diǎn)的步數(shù)和搜索程序的運(yùn)行時(shí)間。

3.2結(jié)果分析

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

參考文獻(xiàn)：

[1] 王萬(wàn)森.人工智能原理及其應(yīng)用[M].2版.北京：電子工業(yè)出版社，2007.

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

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

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

[5] 陳巖，李濤，印明昂.基于改進(jìn)A*算法的管路自動(dòng)敷設(shè)研究[J].兵器裝備工程學(xué)報(bào)，2018，39（10）：91-95，104.

【通聯(lián)編輯：代影】