動機
選擇行動之前,程式必須知道甚麼才算成功。送貨機械人可能要找總成本最低的路線;遊戲程式則要選擇一個經得起對手最佳回應的行動。兩者都探索未來,但數學目標不同。一條路線的成本只涉及該路線;一個可靠的遊戲選擇,卻要計及由對手決定的多種後續局面。
若每個狀態至多有 個後繼,深度為 的完整搜尋樹可有 個節點。啟發式估計能把注意力放在較有希望的方向,但看似合理的分數並非證明。我們要找出哪些不等式令結果可靠,以及哪些實作選擇會破壞它們。
閱讀者應熟悉有限圖、歸納法及基本漸近記號。
定義
定義 1.1.1
(搜尋問題與最優剩餘成本)
確定性搜尋問題包含狀態集 、起點 、目標狀態、有向合法轉移,以及邊成本 。路徑成本是各邊成本之和。以 表示由 到任一目標的最低剩餘成本;沒有可行路徑時取無窮大。在有限且成本非負的圖中,刪去非負成本迴圈不會增加成本,因此可達目標的最優值可由某條簡單路徑取得。
定義 1.1.2
(狀態與搜尋節點)
搜尋節點記錄一條特定路徑,狀態則記錄足以決定往後合法行動的資訊。因此,多個節點可以對應同一狀態。若燃料會影響行動,單用位置作狀態便不夠完整,合併這些節點可能丟掉正確答案。圖搜尋通常保留最小已發現路徑成本 ,以及用來重建路徑的前驅。
定義 1.1.3
(可採納與一致的啟發式;A*)
非負啟發式函數 稱為可採納,若每個狀態均有 ,並要求所有目標的估計為零。若每條合法邊均滿足下式,便稱它一致:
沿到達目標的路徑反覆套用此式,可見一致性蘊涵可採納性;反方向一般不成立。A* 以 排列已發現而尚未展開的狀態。鬆弛一條邊,是在 時改善後者並更新前驅。若已展開的狀態獲得改善後重新進入邊界集合,便稱為重新開啟。
定義 1.1.4
(局部搜尋與爬山法)
爬山法作出另一種取捨:它只保留當前候選,移到目標分數更好的鄰居,不必保存其他路徑。局部最大點沒有更好的鄰居,卻可能遠遜於別處。平台上的同分行動要有明確處理規則,否則無限制橫向移動可以造成循環。
定義 1.1.5
(極小極大值)
遊戲部分假設搜尋樹有限、轉移確定、資訊完全,MAX 與 MIN 輪流行動,每個葉節點有一個給 MAX 的收益。葉節點的極小極大值就是其收益;MAX 節點取子節點最大值,MIN 節點取最小值。這是零和模型,假設 MIN 正在最小化 MAX 的同一收益。隨機結果或隱藏資訊需要另外的模型。
定理/命題
定理 1.1.6
(一致啟發式下的 A*)
設有向圖有限,邊成本非負,啟發式非負、一致且在目標為零。A* 每次取最小 ,只在成本嚴格改善時更新,並忽略優先隊列中的過期項目,便可在取出狀態時永久關閉它。每個已取出狀態的 均為最優成本;若在取出目標時停止,所得路徑最便宜。
命題 1.1.7
(可採納啟發式配合重新開啟的 A*)
設有向圖有限,邊成本非負, 可採納且在目標為零,並設從 可達某個目標。考慮這樣的 A*:每當標記 被嚴格改善, 就重新放回邊界集合,即使它之前已展開過;並在取出目標時停止。則它必會停止,且所返回的路徑最便宜。
命題 1.1.8
(極小極大值與 - 截斷)
在上述有限交替遊戲樹中,極小極大值是 MAX 面對最佳對抗仍可保證的收益。深度優先計算時,若 MAX 節點目前下界已不小於祖先 MIN 選擇的上界,可停止該節點其餘分支;若 MIN 節點目前上界已不大於祖先 MAX 選擇的下界,也可停止。這些截斷保留根節點的極小極大值。
正確性不等於普遍高效。有限狀態圖仍可能非常龐大,- 也不排除最壞情況下的指數級葉節點數。定理說明在指定模型中答案有甚麼保證,沒有承諾任意問題都能快速解決。
證明思路
證明
(重加權把 A* 化為 Dijkstra)
引入重加權邊成本:
一致性恰好表示新成本非負。從 到 的路徑中,中間啟發式項互相抵消,故新成本等於原成本加 。因此,按 排序,等價於按暫定的新路徑成本排序。A* 的永久關閉論證於是轉成非負邊上的 Dijkstra 論證。
具體來說,假設某次取出的 還有更便宜的路徑。在該路徑上取第一個未關閉狀態 ;它的前驅已用最優成本關閉,因此鬆弛後, 有最優暫定標記。由於餘下的新邊成本非負, 的新暫定成本不超過 的最優新成本,卻嚴格小於目前取出項目的成本,與取最小值矛盾。起點成本為零,歸納便完成所有狀態的論證。目標估計為零;若還有更便宜的目標,其路徑必有優先值更小的邊界前綴,故不能先取出較貴目標。
證明透視
啟發式不等式真正提供甚麼
關鍵是假設每條邊一致,而不只是估計通常偏低。一致性把所有重加權邊變成非負,後來的路徑便不能經過負成本新邊,偷偷降低已確定的標記。可採納性仍可提供目標的下界論證,卻不足以單獨支持永久關閉。
證明
(已定案的前綴令邊界上有狀態不超過最優值)
終止性。 每個標記 都是一條由鬆弛串連而成的路線的成本。由歸納可知這些路線都是簡單路徑:若到達 的路線已經經過 ,則 的標記早已不大於該前綴的成本,而標記只降不升,故經 的鬆弛不會是嚴格改善。有限圖只有有限條簡單路徑,所以每個狀態只可能有有限個標記值。每次重新放入邊界集合都跟隨一次嚴格下降,因此放入次數有限。
最優性。 設 是成本為 的最便宜目標路徑,其每個前綴都是到該端點的最便宜路徑,成本為 。若 曾在標記等於 時被展開,便稱它已定案。假設尚未取出任何目標,則 未定案,所以路徑上有第一個未定案的狀態 。若 ,則 在邊界上,標記為 。若 ,則 已用最優標記展開,所以 得到的標記不大於 。標記是路徑成本,故它等於 。由於 尚未以該標記展開,而每次嚴格改善都會令狀態重新進入邊界,所以它在邊界上。它的優先值滿足
因為路徑餘下部分到達目標的成本是 。所以在取出目標之前,邊界非空,且最小優先值至多為 。以標記 取出的目標,其優先值就是 (目標處 )。取出最小優先值項目,故 ;又因 是從 到某個目標的路徑成本,所以 。因此 。
證明
(對樹高歸納,再傳遞界限)
極小極大法用樹高歸納。葉的值由模型指定。MAX 可以選取保證值最大的子節點,MIN 則能把任何其他選擇限制在其子節點值;MIN 節點作對稱論證。這同時證明收益可保證,以及對手能達到相應上界。
剪枝時,若較早選擇已保證根收益至少為 ,新 MIN 子節點只要找到一個收益不超過 的回應,該整個子節點的值便至多為 。其餘回應只可能令最小值更低,不能改善根選擇。MAX 的情況對稱。相等時可為求值或找一個最優行動而剪枝,但若要列出所有同分最優行動,就可能要保留更多分支。被截斷子樹的返回值亦可能只是界限,而非精確值。
以下追蹤使用另一棵有八個葉節點的樹。比較根節點的確切值與被剪枝子樹傳回的界。
例題詳解
例題 1.1.9
(一致的路線估計)
邊為 成本 、 成本 、 成本 、 成本 、 成本 。設 。每邊均一致,包括 。A* 先取 ,再以 取 ,把 改善至 ,並發現成本 的目標。展開 後,目標改善至 。取出 才證實路徑 的成本為 。較早發現成本 的目標不足以停止。
例題 1.1.10
(需要重新開啟的可採納估計)
邊為 成本 、 成本 、 成本 、 成本 。取 。從 出發的真成本為 ,故估計可採納。A* 先以成本 關閉 ,因其優先值 低於 的 ;隨後發現成本 的目標。展開 後才找到成本 的 ;若不重新開啟它,改善無法傳至目標,便錯誤返回 ,而非 。失敗的一致性不等式在 :。重新開啟 便能修正結果。
以下互動使用的圖與上面兩個例子不同:一致圖的最優成本是 7,首次產生的目標成本是 10;不一致圖中重新開啟得到 5,拒絕改善已關閉狀態則得到 6。比較兩種停止政策並追蹤隊列,不要直接套用上例的數值。
例題 1.1.11
(確實成立的 - 截斷)
MAX 根有兩個 MIN 子節點。先讀左邊葉收益 ,得左子值 ,根下界為 。右子節點的第一個葉收益為 ,已給整個右子樹上界 ,故可略過其餘葉。若未讀葉為 ,右子值仍是 ;若為 ,右子值成為 。兩者都不能改善根的選擇,根值為 。
常見錯誤
反例模式
局部改善未必通往最佳狀態
鏈狀鄰居 的分數依次為 。從 嚴格爬山會到 並停止,因兩個鄰居都較差;全域最大卻在 。停止只證明沒有允許的局部步驟能改善當前值。隨機重啟或擴闊鄰域可在實務上幫助,成功保證仍須另證。
常見錯誤
(在剛發現目標時便停止)
A* 必須在狀態從邊界集合取出時才檢查目標,而不是在它被產生時。在上面一致路線的例題中,目標 最先以 被產生,但最便宜的路徑成本是 ,要展開 後才找到。
常見錯誤
(用已知路線檢驗可採納性)
可採納性比較的是 與真正最優值 ,並非與已找到的某條路線的成本。在重新開啟的例題中,從 最先找到的路線成本為 ,而 。若聲稱 ,它通過 的檢驗,卻違反 。
常見錯誤
(把每一層都當作 MAX)
每層都取最大值,等於假設對手會合作。設 MAX 根有兩個 MIN 子節點,葉分別為 與 ,則極小極大值是 ;每層都取最大值卻會聲稱 ,而對手根本不必容許這個收益。
狀態鍵要保留所有會影響未來的資訊。深度截斷的極小極大法只對截斷樹及指定葉評分精確,對完整遊戲的預測仍受未搜尋戰術與評分誤差影響。
時間與空間成本也要分開:A* 常保存大量邊界及成本標記,深度優先遊戲搜尋可只保存與深度成正比的調用堆疊,另加行動產生及可選表格。若用置換表重用局面,必須區分精確值、下界及上界,也要記錄剩餘深度;剪枝所得界限不能隨意冒充完整求值。
在最佳走法次序下,剪枝只需檢查完整樹葉子數的大約平方根。
自然延伸的下一個問題
剪枝最多能省下多少葉子?
在最佳走法次序下,剪枝只需檢查完整樹葉子數的大約平方根。
在分支因子為 、深度為 、葉值互異的均勻樹中,- 至少要檢查 片葉子,完整極小極大則要檢查 片。當 、 時,是 片中的 片。最佳情況需要有利的走法次序,而這事先並不知道;最壞情況仍要檢查所有葉子。
總結
先說清每個數值的意義,再判斷算法。A* 的 是已發現路徑成本, 是剩餘成本下估,一致性容許永久關閉。極小極大值是面對對抗的保證,- 用界限省去不影響選擇的工作。局部搜尋只憑改善分數並不提供全域證明。狀態模型、停止規則及重複狀態政策都是算法規格的一部分。
練習
練習 1.1.12
(在每步成本為一的四鄰居方格上,證明到固定目標的曼哈頓(Manhattan)距離一致,即使部分格被封閉。從某狀態根本無法到目標時,可採納性如何解讀?)
基礎證明
解答(3)
- 1
檢查一步合法移動
關鍵一步
記 。相鄰格只有一個座標改變一,絕對值的三角不等式給出 。
依據: 兩項座標差中只有一項改變,且最多改變一。
- 2
封閉格與路徑
封閉格只刪除邊,所以保留下來的每條邊上不等式仍成立,目標處 為零。沿一條由 到目標的 步合法路徑,把不等式用 次得 ,因此 。
- 3
無法到達的狀態
∎若從 根本無法到達目標,則 ,有限的估計 仍滿足 。可採納並不承諾路徑存在。
練習 1.1.13
(對上面的不一致例題,求所有真正剩餘成本,列出每條失敗的一致性不等式,並追蹤容許重新開啟的 A*,直到取出目標。)
核心
解答(3)
- 1
求真正剩餘成本
關鍵一步
。從 只有路線 ,故 。從 只有路線 ,故 。從 出發,路線 與 的成本分別是 與 ,所以 。
- 2
逐邊檢驗
:。:。:。: 不成立。只有 不一致。
- 3
追蹤容許重新開啟的 A*
以 記標記。展開 後有 、;展開 得 ;展開 把 改善並重新開啟為 ;再展開 ,把 改善為 。取出 返回成本 。優先值在展開後下降,正反映一致性不成立。
快速檢查
(MAX 根的三個 MIN 子節點,葉列表為 、、,按左至右搜尋。求根值,並列出以無窮初始界限執行 - 時略過的葉。)
解答 · 答案
三個子值為 ,根值為 。左邊兩葉均須讀取,才確立根下界 。中間子節點的第一葉 已不大於此界,可跳過葉 。最後一組先讀 不能截斷,仍要讀葉 才定出其值。因此只略過一片葉,即 。在 MIN 節點看見一個高收益回應,不代表其他回應也高。
練習 1.1.14
(若 都是非負、一致且目標為零的啟發式,證明它們逐點最大值仍一致。它們的和必定可採納嗎?給明確例子。)
核心
解答(3)
- 1
選取達到最大值的指標
關鍵一步
令 ,並固定一條邊 。選指標 使 ,則 。
依據: 每個 都一致,而 是最大值,故 。
- 2
檢查其餘性質
非負函數的最大值仍非負;在目標處兩者皆為零,故 亦為零。所以 是一致且目標為零的啟發式。
- 3
檢驗它們的和
取只有一條成本 的邊 ,兩個估計在 均為 、在 均為零。各自精確且一致,但其和在 為 ,超過真成本 。最大值可安全結合這些下界,相加則需要額外的成本分解依據。所以和不一定可採納。