《人工智能：計算Agent基礎》——3.3 圖搜尋

本節書摘來自華章計算機《人工智能：計算agent基礎》一書中的第3章，第3.3節,作者：（加）david l.poole,alan k.mackworth 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

在這一章中，我們将一般搜尋機制抽象表示為在有向圖中的路徑搜尋。要解決一個問題，首先定義潛在的搜尋空間，然後将搜尋算法應用于其中。74許多問題求解的任務都可以轉化為在圖中尋找路徑的問題。圖搜尋提供了抽象的一個合适層次，用這種抽象，可以研究獨立于特定領域的簡單問題求解。

一個（有向）圖包含一個節點集及一個節點間的有向弧集。其思路是找到一條沿着這些弧從起始節點到目标節點的路徑。

因為将問題表示為圖不止一種方式，是以抽象很重要。這一章中的例子都是有關狀态空間搜尋，節點代表狀态，弧代表動作，以後的章節中會讨論用圖表示問題的不同搜尋方式。

形式化圖搜尋

一個有向圖(graph)包括：

一個節點(node)集合n；

一個節點的有序對集合a，叫做弧(arc)。

在這個定義中，節點可以是任何東西。定義的實質是限制弧是節點的有序對。可以有無限多的節點和弧。我們并沒有假設圖完全明确地表示出來，我們僅需要有一個程序根據需要産生節點和弧。

弧〈n1,n2〉是一條從n1的出弧(outgoing arc)和一條至n2的入弧(incoming arc)。

如果有一條從節點n1到節點n2的弧線，也就是〈n1,n2〉∈a，節點n2就是節點n1的鄰居(neighbor)。注意到兩點是鄰居不意味着對稱，因為n2 是n1 的鄰居并不意味着n1就必須是n2的鄰居。例如，弧可能被标記(lable)為使agent從一個狀态到達另一個狀态的動作。

一條從節點s到節點g的路徑(path)是一個節點序列〈n0,n1,…,nk〉，節點s=n0,g=nk,〈ni-1,ni〉∈a，即對于每一個i都有從ni-1到ni的弧。有時将路徑看做弧的序列很有用，〈n0,n1〉,〈n1,n2〉,…,〈nk-1,nk〉，或者是這些弧的标記序列。

一個環(cycle)是一條起點和終點相同的非空路徑，即一個環是一條路徑〈n0,n1,n2,…,nk〉,n0=nk且k≠0。一個有向圖如果沒有任何環就稱作有向無環圖（directed acyclic graph,dag）。這可能應該是一個無環的有向圖，因為它是有向圖但是恰好無環，而不是無環圖正好有向，但是有向無環圖（dag）比無環有向圖（acyclic directed graph,adg）聽起來更好一些。

樹(tree)就是一個有向無環圖，其中有一個節點沒有入弧，其他每一個節點都正好有一條入弧。沒有入弧的節點叫做樹的根(root)節點，沒有出弧的節點叫葉(leaves)節點。

要将問題編碼為圖，一個節點集叫做起始節點(start node)，另一個節點集叫做目标節點(goal node)。解(solution)就是從起始節點到目标節點的一條路徑。

有時會有一個與弧相關的花費(cost)，是一個正數，我們将弧〈ni,nj〉的花費記作cost(〈ni,nj〉)，弧的花費會引起整個路徑的花費。

給定一條路徑p=〈n0,n1,n2,…,nk〉，路徑p的花費就是路徑上弧的花費之和：

最優解(optimal solution)是最低花費的解之一。也就是說，如果存在一條從起始節點到目标節點的路徑p，而不存在其他從起始節點到目标節點的路徑p′使得cost(p′)

https://yqfile.alicdn.com/95a1520e01d04c61cd0f3a07fadfd3afa8db5d55.png" >

圖3-2　帶有弧花費的投遞機器人域的圖【例3-4】　再來看圖3-1中描述的投遞機器人尋找從位置o103到位置r123的路徑問題。在這個圖中，感興趣位置已經标注。為了簡化問題，我們隻考慮加粗字型訓示的位置并且一開始就限定機器人移動的方向。圖3-2顯示了結果圖，在這個圖中節點代表位置，弧則表示機器人在位置間的可能做出的每一步移動，且每條弧線上标示出了從一個位置到下一個位置的花費。76

在這個圖中，節點集合n={mail,ts,o103,b3,o109,…}，弧集合a={〈ts,mail〉，〈o103,ts〉,〈o103,b3〉,〈o103,o109〉,…}。節點o125沒有相鄰節點，節點ts有一個相鄰節點，即mail。節點o103有三個相鄰節點，即ts、b3和o109。

這樣從o103到r123就有三條路徑：

如果o103是起始節點，r123是目标節點，那麼這三條路徑都是圖搜尋問題的解。

很多問題中搜尋圖沒有明确給出，要根據需要動态架構。所有搜尋算法都要求遵循的原則是：從一個節點生成它的鄰居（子節點），然後确定它是否是目标節點。

一個節點的前向分支系數(forward branching factor)是指離開該節點的弧（出弧）的數目，而它的後向分支系數(backward branching factor)則是指進入該節點的弧（入弧）的數目。這些系數提供了圖的複雜度的測量标準。當我們讨論搜尋算法的時間和空間複雜度時,假定分支系數最高值（自上而下）由一個常數來界定。

【例3-5】　在圖3-2中，節點o103的前向分支系數是3，即從o103有三條出弧。節點o103的後向分支系數是0，即無入弧指向節點o103。mail前向分支系數為0，後向分支系數為1。節點b3前向分支系數為2，後向分支系數為1。

分支系數很重要，因為它是決定圖大小的關鍵因素。如果每一個節點前向分支系數是b，且是樹型圖，那麼該圖中有bn個節點，目前節點離任意節點的弧的段數是n。