代價(jià)樹深度優(yōu)先搜索及優(yōu)化

劉慶宇

代價(jià)樹深度優(yōu)先搜索及優(yōu)化

劉慶宇

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

代價(jià)樹深度優(yōu)先搜索算法是代價(jià)樹搜索的常用方法之一，但在沒(méi)有限制條件的情況下，可能陷入死循環(huán)或者大量無(wú)效搜索，存在搜索不完備以及所找的解未必是最優(yōu)解的問(wèn)題。針對(duì)深度優(yōu)先搜索的缺點(diǎn)，在搜索過(guò)程中設(shè)計(jì)一定的剪枝條件，以提高搜索效率避免陷入死循環(huán)，并盡量返回代價(jià)更低的解。

代價(jià)樹；搜索；深度優(yōu)先

搜索是人工智能學(xué)科重要的研究?jī)?nèi)容之一，指從當(dāng)前狀態(tài)出發(fā)，根據(jù)一定的條件及規(guī)則搜索到達(dá)目標(biāo)狀態(tài)路徑的過(guò)程，包括盲目搜索和啟發(fā)式搜索[1]。其中盲目搜索指在搜索中每一步都根據(jù)既定的規(guī)則和策略進(jìn)行搜索，啟發(fā)式搜索則是指在搜索過(guò)程中的每一步都根據(jù)估價(jià)函數(shù)或一定的方法選擇離目標(biāo)狀態(tài)預(yù)測(cè)更優(yōu)的路徑繼續(xù)搜索[2]。

代價(jià)樹是代價(jià)搜索樹的簡(jiǎn)稱，指有向邊上標(biāo)有代價(jià)(或花費(fèi))的搜索樹。代價(jià)樹的搜索與普通搜索的區(qū)別在于搜索過(guò)程中要考慮當(dāng)前搜索路徑代價(jià)并選擇較低代價(jià)的路徑繼續(xù)搜索[3]。

1 代價(jià)樹深度優(yōu)先搜索算法

1.1 算法介紹

代價(jià)樹的深度優(yōu)先搜索主要是從根節(jié)點(diǎn)S0開始進(jìn)行擴(kuò)展，并從后繼節(jié)點(diǎn)中選擇代價(jià)最小的節(jié)點(diǎn)繼續(xù)擴(kuò)展，并以此類推，直到節(jié)點(diǎn)無(wú)法擴(kuò)展且沒(méi)有找到解時(shí)進(jìn)行回溯，若找到解，則返回。

代價(jià)樹深度優(yōu)先搜索需要定義2個(gè)隊(duì)列，OPEN隊(duì)列代表未擴(kuò)展節(jié)點(diǎn)的隊(duì)列，CLOSED隊(duì)列代表已擴(kuò)展節(jié)點(diǎn)的隊(duì)列。

定義節(jié)點(diǎn)j的代價(jià)f(j) = f(i) + c(i,j)，其中c(i,j)代表邊節(jié)點(diǎn)i到其后繼節(jié)點(diǎn)j的代價(jià)。

算法的流程如下。

(1)將節(jié)點(diǎn)S0放入OPEN表中，CLOSED表置空。

(2)判斷OPEN表是否為空，若空則返回，若不為空則從OPEN表的首部拿出第一個(gè)節(jié)點(diǎn)n放入CLOSED表中。

(3)判斷節(jié)點(diǎn)n是否目標(biāo)節(jié)點(diǎn)，若是，則返回。

(4)判斷節(jié)點(diǎn)n是否可擴(kuò)展，若不可擴(kuò)展，則返回步驟(2)。

(5)若節(jié)點(diǎn)n可擴(kuò)展，則對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展，計(jì)算后繼節(jié)點(diǎn)代價(jià)并按從小到大的順序排序后加入到OPEN表的首部，返回步驟(2)。

1.2 算法缺點(diǎn)分析

(1)算法在對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展時(shí)，沒(méi)有考慮后繼節(jié)點(diǎn)是否在祖先節(jié)點(diǎn)中出現(xiàn)過(guò)，導(dǎo)致可能出現(xiàn)死循環(huán)。

(2)算法在擴(kuò)展節(jié)點(diǎn)時(shí)沒(méi)有考慮該節(jié)點(diǎn)是否是已搜索過(guò)的無(wú)效節(jié)點(diǎn)。

(3)算法在執(zhí)行復(fù)雜搜索時(shí)由于沒(méi)有限制條件導(dǎo)致可能在無(wú)解路線上浪費(fèi)大量時(shí)間。

(4)算法返回的搜索結(jié)果不一定是最優(yōu)解。

2 代價(jià)樹深度優(yōu)先搜索優(yōu)化

2.1 算法優(yōu)化

針對(duì)代價(jià)樹深度優(yōu)先搜索的缺點(diǎn)，對(duì)算法進(jìn)行相應(yīng)改進(jìn)。

(1)根據(jù)具體問(wèn)題對(duì)深度優(yōu)先搜索算法進(jìn)行搜索層數(shù)限制，當(dāng)搜索達(dá)到規(guī)定的層數(shù)后，即視為無(wú)法擴(kuò)展。若搜索完畢后依然沒(méi)有找到解，則提高限制層數(shù)。

(2)對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展時(shí)，判斷其是否出現(xiàn)在CLOSED表中，若存在則丟棄節(jié)點(diǎn)n。

(3)對(duì)節(jié)點(diǎn)n進(jìn)行擴(kuò)展時(shí)，判斷相應(yīng)的后繼節(jié)點(diǎn)是否出現(xiàn)在OPEN表中，若存在則比較其代價(jià)，若后繼節(jié)點(diǎn)代價(jià)低則丟棄OPEN表中的相應(yīng)節(jié)點(diǎn)，若節(jié)點(diǎn)n后繼節(jié)點(diǎn)代價(jià)高則丟棄相應(yīng)的后繼節(jié)點(diǎn)。

2.2 改進(jìn)算法應(yīng)用分析

推銷員旅行問(wèn)題，設(shè)有7個(gè)城市A、B、C、D、E、F、G，交通路線如圖1所示，圖中數(shù)字代表所需路費(fèi)，推銷員要從A城市到達(dá)G城市，怎么樣去搜索一條花費(fèi)更低的路線？

2.2.1 深度優(yōu)先搜索過(guò)程

按照深度優(yōu)先搜索方法，遍歷順序如圖2所示。

(1)首先從節(jié)點(diǎn)A出發(fā)擴(kuò)展，將節(jié)點(diǎn)B、節(jié)點(diǎn)C加入OPEN表中，將節(jié)點(diǎn)A加入CLOSED表中。

圖2 深度優(yōu)先搜索過(guò)程

(2)選擇代價(jià)更小的B節(jié)點(diǎn)擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)B并將節(jié)點(diǎn)B加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)B，將節(jié)點(diǎn)C、節(jié)點(diǎn)E加入OPEN表中。

(3)選擇代價(jià)更小的C節(jié)點(diǎn)擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)C并將節(jié)點(diǎn)C加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)C，將節(jié)點(diǎn)E、節(jié)點(diǎn)D加入OPEN表中。

(4)選擇代價(jià)更小的E節(jié)點(diǎn)擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)E并將節(jié)點(diǎn)E加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)E，此時(shí)后繼節(jié)點(diǎn)中B為代價(jià)最小的節(jié)點(diǎn)，搜索將會(huì)陷入死循環(huán)。

2.2.2 改進(jìn)深度優(yōu)先搜索過(guò)程

因城市數(shù)量較少，可以不通過(guò)設(shè)置層數(shù)限制搜索深度，按照改進(jìn)的深度優(yōu)先搜索方法，遍歷順序如圖3所示。

圖3 改進(jìn)深度優(yōu)先搜索過(guò)程

(1)首先從節(jié)點(diǎn)A出發(fā)擴(kuò)展，將節(jié)點(diǎn)B、節(jié)點(diǎn)C加入OPEN表中，將節(jié)點(diǎn)A加入CLOSED表中。

(2)選擇代價(jià)更小的B節(jié)點(diǎn)擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)B并將節(jié)點(diǎn)B加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)B，因節(jié)點(diǎn)C已經(jīng)在OPEN表中存在且原節(jié)點(diǎn)代價(jià)更小故丟棄，將節(jié)點(diǎn)E加入OPEN表中。

(3)選擇節(jié)點(diǎn)E擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)E并將節(jié)點(diǎn)E加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)E，將節(jié)點(diǎn)F加入OPEN表中。

(4)選擇節(jié)點(diǎn)F擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)F并將節(jié)點(diǎn)F加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)F，節(jié)點(diǎn)F不可擴(kuò)展。

(5)選擇節(jié)點(diǎn)C擴(kuò)展，從OPEN表中取出節(jié)點(diǎn)C并將節(jié)點(diǎn)C加入CLOSED表中，擴(kuò)展節(jié)點(diǎn)C，將節(jié)點(diǎn)E和D加入OPEN表中。

(6)選擇節(jié)點(diǎn)E擴(kuò)展，因節(jié)點(diǎn)E在CLOSED表中已經(jīng)存在，是無(wú)效節(jié)點(diǎn)，故丟棄。

(7)選擇節(jié)點(diǎn)D擴(kuò)展，找到解，搜索結(jié)束。

3 結(jié)語(yǔ)

經(jīng)過(guò)推銷員旅行問(wèn)題的驗(yàn)證，改進(jìn)后的算法避免了搜索陷入死循環(huán)，提高了搜索效率。但依然存在找到的解未必是最優(yōu)解的問(wèn)題，搜索到的解相比普通深度優(yōu)先搜索更優(yōu)。

[1] Lu Kai, Tang Tao, Gao Chunhai. The Depth-First Optimal Strategy Path Generation Algorithm for Passengers in a Metro Network[J]. Sustainability, 2020, 12(13): 1-16.

[2] 龔建華. 深度優(yōu)先搜索算法及其改進(jìn)[J]. 現(xiàn)代電子技術(shù), 2007(22): 90-92.

[3] 張建旭, 蔣燕, 劉興國(guó). 基于深度優(yōu)先反向搜索算法確定有效路徑集合[J]. 重慶交通大學(xué)學(xué)報(bào): 自然科學(xué)版, 2015, 34(3): 93-98.

Depth First Search for Cost Tree and Its Optimization

LIU Qing-yu

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

The depth first search algorithm for cost tree is one of the common methods of cost tree search. It may fall into an endless loop or a large number of invalid searches in the case of no constraints. The depth first search may be not complete and the solution may be not optimal. Aiming to solve the shortcomings of depth first search, some pruning conditions are designed in the search process to improve the search efficiency and avoid falling into the dead loop and return the solution with lower.

cost tree; search; depth first

10.15916/j.issn1674-3261.2021.05.010

TP301.6

A

1674-3261(2021)05-0322-03

2020-12-15

劉慶宇(1991-)，男，遼寧康平人，講師，碩士。

責(zé)任編輯：孫 林