面向最優化問題的人工智能搜索算法研究*

王永建，楊建華，郭廣濤，王治東

（中國通信建設集團設計院有限公司，北京 100079）

面向最優化問題的人工智能搜索算法研究*

王永建，楊建華，郭廣濤，王治東

（中國通信建設集團設計院有限公司，北京 100079）

搜索是人工智能領域的關鍵技術，隨著信息技術的不斷發展與成熟，人工智能未來發展前景寬廣。現實中，許多問題解決的實質就是最優化過程。首先介紹最優化的概念，從解答最優化問題出發，分析動態規劃算法在解決最優化問題的特殊作用。然后，分析基本搜索算法中典型的深度搜索算法和廣度搜索算法的特點以及適用場景。最后，搭建仿真環境，進行對比測試。結果表明，動態規劃算法的時間復雜度遠小于搜索算法，但是其空間復雜度遠大于搜索算法，二者適用于不同的場景。

人工智能；最優化；動態規劃；深度搜索；廣度搜索

0 引 言

近年來，微電子﹑大數據﹑互聯網+﹑云計算﹑新算法等技術的發展，極大推動了人工智能技術的發展。不過，目前人工智能技術還不是非常成熟，在解決某些問題的過程中還不是很完美，但人工智能已在社會上開始廣泛應用。例如，人工坐席中的語音自動識別系統，醫療衛生領域中的影像識別與分析，生命科學領域中的數據預測與基因演變預測，新聞出版﹑文獻檢索領域中的自然語言翻譯﹑自動閱讀，工業領域中的機器人等。

最優化原理，即一個問題的最優解只取決于其子問題的最優解。也就是說，非最優解對問題的求解沒有影響[1]。實際中，很多問題解決或者求解的過程，實質上就是最優化的過程。一個問題可以分解為多個子問題的最優化問題，全部子問題的最優解，往往就是整個問題的最優解。

搜索是人工智能的基本問題，一個問題的求解過程就是搜索[2]。搜索技術已滲透在各種各樣的人工智能系統中，從某種意義上來講，“沒有搜索就沒有人工智能”。本文面向最優化問題，對人工智能搜索算法進行研究。

1 動態規劃算法

1.1 動態規劃簡析

1.1.1 舉例分析

要理解最優化問題，需先理解動態規劃算法。要理解動態規劃，必須先理解幾個關鍵名詞。本文通過舉例進行分析，如圖1所示。

圖1 動態規劃

圖1中，A﹑B﹑C﹑D分別代表一個景區。假定一旅客從A景區出發去往D景區，下面探討如何選擇一條最短路徑到達D景區。

將圖中的點分為四類（A﹑B﹑C﹑D），圖中所有的邊都與相鄰的兩類點互聯，并且都從前一類點指向后一類點，則圖中的邊可分為三類：A→B，B→C和C→D。需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，并且要求這條路徑最短。該問題可分解為多個階段子問題[1]。

1.1.2 動態規劃關鍵詞

通常，一個動態規劃算法應該包含以下幾種基本關系與屬性。

狀態（State）：表示事物的性質，是描述動態規劃中的“單元”的量。

階段（Stage）：指一些性質相近﹑可以同時處理的狀態集合。通常，一個問題可以由處理的先后次序劃分為幾個階段。實際上，階段只是標識某些處理方法相同，和處理順序無關的狀態。一個階段可包含多個狀態，也可只包含一個狀態[3]。

狀態轉移方程：指前一個階段的狀態轉移到后一個狀態的演變規律，是關于兩個相鄰階段狀態的方程，是動態規劃的中心。

決策（Decision）：指每個階段采取的某種選擇性的活動，是系統需要完成的選擇。

動態規劃所處理的問題屬于“多階段決策問題”，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策構成了決策序列，同時確定了完成整個過程的活動路線（通常是求最優的活動路線），如圖2所示。

圖2 動態規劃

圖2中，決策和狀態轉移之間的關系可以理解為：決策是狀態轉移的途徑，狀態轉移是決策的目的。

各段決策確定后，整個問題的決策序列就構成一個策略，用P1,n={u1(s1),u2(s2),…,un(sn)}表示。對每個實際問題，可供選擇的策略具有一定的范圍，稱為允許策略集合，記作P1,n，而使整個問題達到最優效果的策略就是最優策略[3]。

因此，運用動態規劃的一個前提，即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對于先前決策所形成的狀態而言，其以后的所有決策應構成最優策略。這就是最優化原理，可以理解為“最優策略的子策略也是最優策略”。

1.2 無后效性

無后效性即一個問題被劃分階段后，階段I中的狀態只能由階段I+1中的狀態通過狀態轉移方程獲得，與其他狀態沒有關系，特別是與未發生的狀態沒有關系，這就是無后效性。

在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但往往會在后效性這一點上設置障礙。

1.3 最優指標函數和規劃方程

1.3.1 最優指標函數

用于衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk采用最優策略Pk*(sk)到過程終止時的最佳效益值。

最優指標函數實質是關注問題的解。在上面的例子中，f2(B1)表示從B1點到終點D1點的最短路徑長度，求解的最終目標就是f1(A1)。

1.3.2 規劃方程

最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：

其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表示為max或min。

fn(sn)=某個初始值，稱為邊界條件。

結合本文的例子分析，規劃方程即：

邊界條件為f4(D1)=0。

這里是一種從目標狀態往回推的逆序求法，適用于目標狀態確定的問題。在信息學問題中，存在很多有著確定的初始狀態。當然，對于初始狀態確定的問題，也可以采用從初始狀態出發往前推的順序求法[4]。

2 基本搜索算法

2.1 回溯算法

回溯算法是所有搜索算法中最為基本的一種算法，采用“此路不通就回撤”思想作為其控制結構。相當于采用了先根遍歷的方法來構造解答樹，可用于找解﹑所有解以及最優解[5]。具體的算法分為遞歸算法和非遞歸算法兩種。

2.1.1 遞歸算法

解決遞歸問題的算法通常稱為遞歸算法，遞歸算法的本質是把一個較復雜問題的處理歸結為較簡單問題的處理[6]。從數學角度闡述，如果一個函數在它的函數體內又直接或間接地調用該函數本身，那么此函數稱為遞歸函數[7]。

遞歸算法描述如下：

2.1.2 非遞歸算法

雖然遞歸算法的結構簡潔﹑可讀性強﹑實現簡單，但是運行效率較低[8]。尤其是遞歸越深，占用棧空間越多。如果遞歸的深度達到超出棧空間的程度時，遞歸算法將不再適合[9]。非遞歸算法與遞歸算法是相對的。

非遞歸算法描述如下：

Node(節點類型)＝Record

Situtation:TSituation（當前節點狀態）;

Way-NO:Integer（已使用過的擴展規則的數目）;

End

List(回溯表):Array[1..Max(最大深度)] of Node;

pos(當前擴展節點編號):Integer;

分析總結：回溯算法對空間的消耗較少，當其與分支定界法一起使用時，對于所求解處于解答樹中層次較深時的問題有較好的效果，但應避免在后繼節點可能與前繼節點相同的問題中使用，以免產生循環[10]。

2.2 深度搜索算法

深度搜索算法有廣義和狹義兩種理解。廣義理解是，只要最新產生的結點（即深度最大的結點）先進行擴展的方法，就稱為深度搜索方法。在這種理解情況下，深度搜索算法有全部保留和不全部保留產生的結點的兩種情況。而狹義理解是，僅僅只保留全部產生結點的算法[11]。本文采用廣義理解，不保留全部結點，屬于一般的回溯算法范疇。保留全部結點的算法，實際上是在數據庫中產生一個結點之間的搜索樹，屬于圖搜索算法的范疇。

算法實現描述如下：

對上面算法實現描述進行分析，深度搜索算法可總結如下：

（1）深度搜索算法有遞歸以及非遞歸兩種設計方法。一般，當搜索深度較小﹑問題遞歸方式比較明顯時，用遞歸方法設計好，可以使程序結構更簡捷易懂。當搜索深度較大﹑數據量較大時，由于系統堆棧容量的限制，遞歸容易產生溢出，此時用非遞歸方法設計比較好[11]。

（2）不保留全部結點的深度搜索算法。將擴展的結點從數據庫中彈出刪除，這樣一般在數據庫中存儲的結點數就是深度值。因此，占用的空間較少，所以，當搜索樹的結點較多，用其他方法易產生內存溢出時，深度搜索算法不失為一種有效的算法[5]。

（3）如果要求出最優解，一種方法將是后面要介紹的動態規劃算法；另一種方法是修改原算法，即把原輸出過程的地方改為記錄過程，即記錄達到當前目標的路徑和相應的路程值，并與前面已記錄的值進行比較，保留其中最優的。等全部搜索完成后，才把保留的最優解輸出[12]。

2.3 廣度搜索算法

廣度搜索算法與深度搜索算法的控制結構和產生系統很相似，唯一的區別在于對擴展節點的選取。

這兩種算法每次都擴展一個節點的所有子節點，廣度搜索擴展則是本次擴展的節點的兄弟節點。與之不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個。由于深度搜索保留了所有的前繼節點，所以在產生后繼節點時可以去掉一部分重復節點，從而提高搜索效率[13]。在具體實現上，為了提高效率，采用了不同的數據結構。

具體的算法描述如下：

Node(節點類型)＝Record

Situtation:TSituation（當前節點狀態）;

Level:Integer(當前節點深度);

Last :Integer(父節點);

對上面算法實現描述進行分析，廣度搜索算法可總結如下：

（1）在產生新的子結點時，深度越小的結點越先得到擴展，即先產生它的子結點。為使算法便于實現，存放結點的數據庫一般采用隊列結構。

（2）無論問題性質如何不同，利用廣度搜索算法解題的基本算法相同，但數據庫中每一結點內容﹑產生式規則，根據不同的問題有不同的內容和結構，即便同一問題也可以有不同的表示方法。

（3）當結點到根結點的耗散值和結點的深度成正比時，特別是當每一結點到根結點的耗散值等于深度時，用廣度搜索算法得到的解是最優解；若不成正比，則得到的解不一定是最優解。這類問題要求出最優解，一種方法是改進前面深度（或廣度）搜索算法。具體的，先找到一個目標后，不是立即退出，而是記錄下目標結點的路徑和耗散值；如果有多個目標結點，就加以比較，留下較優的結點；把所有可能的路徑都搜索完后，才輸出記錄的最優路徑。

（4）廣度搜索算法，一般需要存儲產生的所有結點，占用的存儲空間要比深度搜索算法大得多。因此，程序設計中，必須考慮溢出和節省內存空間的問題。

（5）比較深度和廣度兩種搜索算法。廣度搜索算法一般無回溯操作，即無入棧和出棧的操作。所以，廣度搜索算法的運行速度比深度搜索算法要快。

2.4 深度與廣度搜索算法對比

廣度搜索算法是求解最優解問題的一種較好的方法，而深度搜索算法多用于只要求解的情況。當解答樹中的重復節點較多且重復判斷較難時使用，但往往可以用回溯算法或者A*算法代替。

一般情況下，深度搜索算法占內存少但速度較慢，廣度搜索算法占內存多但速度較快。在距離和深度成正比的情況下，兩者都能較快求出最優解。因此，在選擇用哪種算法時，要綜合考慮后再決定取舍。

3 對比測試

對比基本搜索算法與動態規劃算法，以本文第1節例子作為測試依據。測試環境為：浪潮NF5270M2服 務 器，Windows Sever2012，2×Intel E5-2650v2處理器，32GB DDR3內存，2×300GB 15K SAS硬盤；在仿真軟件Matlab 2013a中建立數學模型。采用搜索算法與采用動態規劃算法完成問題解答，消耗時間如表1所示。

表1 搜索算法與動態規劃算法消耗時間

從表1可以分析，動態規劃算法與搜索算法在實際應用中的運行時間差異是巨大的。從理論上講，搜索算法的時間復雜度為O(N!)，動態規劃算法的時間復雜度是O(N2)，兩個時間根本不在一個數量級。指數級的時間增長十分可怕，遠遠大于多項式級的算法。所以，經常稱多項式級的算法為“較好”的算法，稱指數級的算法是“較差”的算法。

動態規劃算法實質上是一種“以空間代價來換取時間代價”的技術，它在實現過程中不得不存儲產生過程中的各種狀態，所以空間復雜度要大于其他算法。具體的，動態規劃的時間復雜度為O(N2)，搜索算法的時間復雜度為O(N!)。

依據測試結果分析總結：對于實時性要求不高，資源緊張或者成本敏感的場景，適用于搜索算法；對于實時性要求較高，資源充裕或者成本不敏感的場景，適用于動態規劃算法。

4 結 語

人工智能是個方興未艾的領域，將對未來人類社會的發展與生活產生重大影響。隨著人工智能技術的不斷成熟，其商業價值與社會價值將不可估量。本文分析動態規劃算法，對基本搜索算法中的代表算法進行闡述研究，并對搜索算法和動態規劃算法進行對比測試，測試結果將為不同場景選擇適合的算法提供參考依據。隨著信息技術﹑人工智能領域的不斷發展，將會產生新的算法和技術。因此，該領域的研究任重道遠。

[1] 李剛.動態規劃的深入討論[DB/OL].(2011-09-20)[2016-05-22].http://wenku.baidu.com/view/ a17920f57c1cfad6195fa790.htm l.

LI Gang.A Deep Discussion on Dynamic Programming[DB/ OL].(2011-09-20)[2016-05-22].http://wenku.baidu.com/ view/a17920f57c1cfad6195fa790.html.

[2] 陳溪.基于電力市場環境下江西省購電優化及管理研究[D].南昌:南昌大學,2014.

CHEN Xi.Study on the Optimization and Management of Electricity Purchase in Jiangxi Province based on the Electricity Markets[D].Nanchang:Nanchang University,2014.

[3] 胡運權,郭耀煌.運籌學教程[M].北京:清華大學出版社,2012.

HU Yun-quan,GUO Yao-huang.Operational Research Tutorial[M].Beijing:Tsinghua University press,2012.

[4] 魏慶來,宋睿卓,孫秋野.迭代自適應動態規劃理論及應用[M].北京:科學出版社,2015.

WEI Qing-lai,SONG Rui-zhuo,SUN Qiu-ye.Theory and App lication of Iterative Adap tive Dynam ic Programming[M].Beijing:Science Press,2015.

[5] 歐陽圣,胡望宇.幾種經典搜索算法研究與應用[J].計算機系統應用,2011,20(05):243-247.

OU YANG-sheng,HU W ang-yu.Research and Application of Several Classical Search Algorithms[J]. Computer Systems & Applications,2011,20(05):243-247.

[6] 張國.基于遞歸算法的非遞歸實現研究[J].長江大學學報:自然科學版,2009,6(03):223-225.

ZHANG Guo.Implementation and Research of Non Recursive based on Recursive Algorithm[J].Journal of Yangtze University(Natual Science),2009,6(03):223-225.

[7] 魏斌,馬繼輝,牛虎.基于遞歸算法的樹型結構圖的設計與實現[J].計算機應用與軟件,2011,28(01):96-98.

WEI Bin,MA Ji-hui,NIU Hu.Design and Implementation of Recursion Algorithm-based Tree Structure Diagram[J]. Computer Applications and Software,2011,28(01):96-98.

[8] 楊春花,姚進,趙培英等.一個遞歸算法非遞歸化的算法框架[J].計算機應用與軟件,2010,27(09):81-84.

YANG Chun-hua,YAO Jin,ZHAO Pei-ying,et al.An Algorithm Frame for Converting Recursive Algorithms to Nonrecursive Ones[J].Computer Applications and Software,2010,27(09):81-84.

[9] 單學廣,楊慶紅,焦莉.遞歸問題的非遞歸實現方法的應用研究[J].計算機與現代化,2011,(01):25-28.

SHAN Xue-guang,YANG Qing-hong,JIAO Li. Application Research on Recursion Question's Nonrecursion Realization Method[J].Computer and Modernization,2011(01):25-28.

[10] 羅斯.搜索算法基礎教程[DB/OL].(2010-03-01) [2016-05-22].http://blog.csdn.net/alsm168/article/ details/6487146..

LUO Si.Basic Course of Search Algorithm[DB/OL]. (2010-03-01)[2016-05-22].http://blog.csdn.net/ alsm168/article/details/6487146.

[11] 張麗娟.自主移動服務機器人路徑規劃方法研究[D].天津:天津科技大學,2012.

ZHANG Li-juan.The Research of the Autonomous Mobile Service Robot Path Planning Method[D]. Tianjin:Tianjin University of Science&Technology,2012.

[12] 龔兵.基于IP網絡的自動拓撲搜索算法[J].五邑大學學報:自然科學版,2007,20(04):6-12.

GONG Bing.An Au tomatic Topological Search Algorithm based on IP Network[J].Journal of Wuyi University(Natural Science Edition),2007,20(04):6-12.

[13] 陳圣群,滕忠堅,洪親等.四種最短路徑算法實例分析[J].電腦知識與技術:學術交流版,2007,3(16):1030-1032.

CHEN Sheng-qun,TENG Zhong-jian,HONG Qing,et al.The Case Analysis of Four Shortest Path Algorithm[J]. Computer Know ledge and Technology(Academ ic Exchange),2007,3(16):1030-1032.

Artificial-Intelligence Search A lgorithm for Optim ization Problem

WANG Yong-jian, YANG Jian-hua, GUO Guang-tao, WANG Zhi-dong

(China International Telecommunication Construction Group Design Institute Co. Ltd., Beijing 100079, China)

Search is the key technology in the field of artificial intelligence. With the ripid development and mature of information technologies, artificial intelligence would have a broad development prospects in the future. The essence for solving many problems, in fact, is the process of optimization. Firstly, the concept of optimization is described, and then from the solution to optimization problem, the special functions of dynamic programming algorithm in solving optimization probleMare analyzed. And then the typical depth search algorithMand breadth search algorithm in basic search algorithms are discussed, including their applicable environments. Finally, the simulation environment is built up and the contrast test is done, and the results show that the time complexity of dynamic programming algorithm is much less than that of search algorithm, but the space complexity is much larger than that of search algorithm, and these two algorithms are suitable for different scenarios. As the ascendant field, artificial intelligence requires continuous research and exploration.

artificial intelligence; optimization; dynamic programming; depth search; breadth search

TP392

A

1002-0802(2016)-11-1459-07

10.3969/j.issn.1002-0802.2016.11.009

王永建（1981—），男，碩士，高級工程師，主要研究方向為信息安全﹑大數據﹑信息編碼；

楊建華（1979—），男，學士，高級工程師，主要研究方向為云計算﹑計算機應用；

郭廣濤（1977—），男，學士，高級工程師，主要研究方向為云計算﹑物聯網；

王治東（1981—），男，學士，高級工程師，主要研究方向為云計算﹑數據通信。

2016-07-16；

2016-10-13 Received date:2016-07-16;Revised date:2016-10-13