為甚麼要保存前沿?
設想機械人在單向走廊中移動。我們需要指定起點、合法移動及目標,地圖才構成一個搜尋問題。若每次移動都花一分鐘,最少步數就給出最短行程;若走廊的通行時間不同,步數最少的路線卻可能更慢。因此,搜尋策略必須配合我們想最小化的量。
定義 22.1.1
(狀態與搜尋節點)
狀態須包含判定未來合法行動及辨認目標所需的一切數據。若開門會消耗鑰匙,位置本身便不足以描述狀態;可以考慮(位置、持有的鑰匙)這個配對。搜尋節點則可記錄抵達某狀態的一條具體路徑;不同路徑可以抵達同一狀態。圖搜尋將重複狀態合併,避免一再探索相同的未來。只有當相同狀態標籤確實代表相同的未來選擇及代價時,這樣合併才正確。
本節研究有限圖上的三種基本方法,為使用啟發式函數改變優先次序的 A* 作準備。
同一問題,三種前沿策略
定義 22.1.2
(搜尋問題、前沿與解)
令 為有限有向圖,起點為 、目標集合為 ;為重現追蹤結果,固定每個狀態的後繼次序。路徑長度是邊數。一致代價搜尋另為每條邊指定有限非負代價 ;路徑代價是邊代價之和。解是由 到某目標的路徑;若 本身是目標,長度零的路徑也是解。前沿保存已發現但尚未處理其外出邊的狀態。沿父指標反向追溯至 ,便可重建路徑。
定義 22.1.3
(廣度優先搜尋)
廣度優先搜尋(BFS)把 放進先入先出隊列並標記為已發現。反覆移除隊首 ;若它是目標,回傳父指標路徑。否則依次檢查後繼:對每個尚未發現的 ,立即標記、令其父節點為 ,再把它加入隊尾。隊列耗盡便報告失敗。加入時立即標記,可防止兩個父節點把同一狀態重複放進隊列;對最少邊數的目標而言,不必保留之後的路徑。
定義 22.1.4
(深度優先搜尋)
深度優先搜尋(DFS)可遞歸實作:進入 時標記,測試它是否目標,然後按次序遞歸造訪每個仍未發現的後繼,調用前設定父指標。找到第一個目標便停止;若從 開始的調用返回仍未找到,則報告失敗。遞歸堆疊保存目前路徑。使用顯式堆疊時,標記及插入後繼的時機可以改變造訪次序,因此應追蹤實際算法,而非單憑名稱推斷次序。
定義 22.1.5
(一致代價搜尋)
一致代價搜尋(UCS)維護暫定代價 :開始時 ,其餘為無窮大,最小優先隊列含 。移除代價最小的項;若其狀態已確定,或項目的代價不等於目前 ,便忽略它。否則確定該狀態;若它是目標,回傳父指標路徑和代價。對每條外出邊,若 ,就更新 、設定父指標為 ,並插入新項。此做法容許過期的隊列項,無須實作 decrease-key。相同代價不必更換父指標。在上述條件下,已確定狀態不會再得到改善,證明如下。
保證與證明
定理 22.1.6
(BFS 最小化邊數)
在有限有向圖上,BFS 回傳邊數最少的可達目標路徑,或正確報告沒有目標可達。每個狀態至多發現一次。使用鄰接表時,時間為 ,輔助狀態及隊列儲存空間為 。
證明
(隊列次序與最短距離)
隊列最初只有深度零的起點。移除深度 的狀態時,新狀態以深度 加到隊尾。因此由歸納法,隊列按記錄深度非遞減排列;每個已發現狀態的父指標均給出該深度的路徑。為證明起見,考慮一個假想的完整遍歷:遇到目標時不停下來,而照常展開它。對最短距離 作歸納,證明距離為 的每個可達狀態都以深度 被發現。 是起點。對距離為 的 ,最短路徑上其前驅距離為 ,依歸納假設以前者深度入隊,並在任何深度 的狀態之前被移除;屆時它會發現 ,除非 已以不大於 的深度被發現。每條已發現路徑都真實存在,因此其深度不可能小於最短距離 。命題成立。實際執行直至移除第一個目標之前,與完整遍歷完全相同。若該目標深度為 ,卻有另一目標的最短距離更小,完整遍歷便會依隊列次序先移除後者,矛盾。每個狀態只入隊一次,各外出邊只檢查一次,得到所述界限。隊列耗盡時所有可達狀態均已處理,故失敗判斷正確。
證明透視
隊列次序帶來甚麼
證明分兩部分。不變式是隊列按記錄的深度排序:每次移出深度為 的狀態,只會把深度為 的狀態加到較舊的項目之後。真正的想法是對真實距離作歸納: 在最短路徑上的前驅距離為 ,所以以深度 入隊,並先於任何深度為 的狀態被移出,於是 至遲在深度 被發現;又因為每個記錄的深度都是實際的路徑長度,不可能更早。有限性只用於窮盡,使失敗報告正確。整個論證沒有用到邊的代價,這正是 BFS 看不見代價的原因。
定理 22.1.7
(UCS 最小化非負路徑代價)
在邊代價有限且非負的有限圖上,上述 UCS 確定每個非過期移除狀態時,其標籤等於最小路徑代價。因此第一個確定的目標在所有可達目標中代價最小。若沒有可達目標,算法會終止並報告失敗。
證明
(第一個被錯誤確定的狀態)
每個有限暫定標籤都對應實際路徑,故不會小於真正的最小值。反設 是第一個被確定時標籤大於最小值的狀態。取一條到 的最便宜路徑,令 為確定 前該路徑上第一個尚未確定的狀態。若 ,其標籤為零;否則其前驅 已被正確確定,鬆弛 時已給 一個不大於該路徑前綴代價的標籤。由於餘下邊均非負,前綴代價不大於整條路徑的代價。因此隊列中有 的有效項,其優先值不大於 的最優代價,嚴格小於正在確定 的項,與最小值先出矛盾。同一前綴論證排除了第一個確定目標以外存在更便宜目標的可能。狀態有限、每個狀態只確定一次,而每次處理的邊有限,故只會產生有限個隊列項;即使有零代價邊也會終止。
證明透視
非負代價的作用
最便宜路徑的前綴代價必須不大於整條路徑。負邊可使不等式倒轉:一條目前看似昂貴的前綴,之後可能通往便宜的目的地。此時永久確定狀態及在第一個目標停止都可能失敗。
命題 22.1.8
(帶過期項的一致代價搜尋的時間)
使用二元堆與鄰接表時,上述 UCS 程序在 時的時間為 ,空間為 。
證明
(計算堆操作次數)
每個狀態只確定一次,確定時只檢查其外出邊一次,所以鬆弛最多 次。每次成功鬆弛插入一項,故全程最多插入並移除 項,堆內也從不超過 項。因 ,一次堆操作的成本為 。移除狀態已確定的過期項只花一次移除,沒有其他工作。再加上 的簿記工作,便得到所述界限。
有限圖上的 DFS 若標記狀態,而且每個鄰接表有限,也必會終止;若報告失敗,所有可達狀態都已造訪。但找到的第一個目標取決於後繼次序,不保證最少邊數或最小代價。使用鄰接表,完整圖 DFS 的時間為 ;包括已造訪標記和遞歸的空間為 。若忽略已造訪標記而只說它使用路徑深度的記憶體,便容易誤導。沒有標記時,即使狀態有限,環也可能使搜尋永不停止。
算例:同一張圖,不同答案
例題 22.1.9
(同一張圖上的廣度優先與深度優先搜尋)
依所列次序取邊: 代價 、 代價 、 代價 、 代價 、 代價 ,沒有其他邊。路徑 有三條邊、代價 ; 有兩條邊、代價 。
BFS 依次移除 ,此時隊列為 : 由 加入, 由 加入。處理 時, 已被發現,故父指標仍為 。BFS 返回邊數最少的 ;它不會比較代價 與 。
遞歸 DFS 每次走第一個後繼,造訪 並回傳該路徑。這次剛好得到較便宜的路徑;若倒轉 的兩個後繼,便得到 。偶然的次序不能證明最優。
例題 22.1.10
(有並列與較遲改善的一致代價搜尋)
UCS 以 確定 ,以 確定 ,再以 確定 ,兩者先後不限。若 先被確定,它插入 ,然後 把標籤改善至 。若 先被確定,它插入 ,而 不會插入 ,因為 並非改善。最後以 確定目標,回傳 。如果 先於 確定,在第一次發現 時就停止可能錯誤地回傳 。
概念視角算法
把一致代價搜尋看成細分圖上的廣度優先搜尋
當所有代價都是正整數時,把每條代價為 的邊換成由 條單位邊組成的鏈,中間經過 個新狀態。路徑代價就變成邊數,所以細分圖上 BFS 的第 層,恰好包含最小代價為 的原有狀態,而 UCS 按相同的代價次序結算原有狀態。在例子的圖中, 與 都在第 層; 最早在第 層出現,經由 ,而經由 的路線要到第 層才到達。這個描述需要正整數代價,因為零代價無法細分;優先隊列只是掃過同樣各層的省力方法。
例題 22.1.11
(零代價環與不可達的目標)
設 與 的代價都是 , 代價為 。UCS 以 確定 並插入 ;再以 確定 。鬆弛 不是改善,因為 不成立;鬆弛 則插入 。以 確定 ,回傳 ,代價為 。零代價環不會造成迴圈:每個狀態只確定一次,而替換必須是嚴格改善。若移除邊 ,隊列在確定 與 後耗盡,程序正確地報告失敗,因為沒有目標可達。
反例模式
邊數最少不等於代價最小
直接邊 代價為 ,邊數比兩邊路徑 少;但若後者兩條邊各花 ,總代價只有 。BFS 對單位邊數、或更一般地相等正邊代價,提供最優保證,對任意非負代價則沒有。
常見錯誤
(在發現時而非確定時停止)
在例圖中,若 先於 被確定, 第一次被發現時的標籤是 。此刻就回傳,得到代價 ,但 的代價是 ,標籤 在 被確定後才出現。對 UCS,目標測試應放在狀態由隊列移除並確定的時刻。(BFS 可以在發現時測試,因為每條邊都算作一步。)
保證的界限
有限圖仍可比它的簡短問題描述大得多。若一棵搜尋樹每個節點至多有 個子節點,深度至 的節點數至多為 ;這是對明確生成的樹的界,不自動是任意問題輸入位元長度的界。不同路徑到達有效的共同狀態時,圖合併可節省工作;但若狀態表示把未來不同的情況合併,結論便不可靠。
UCS 是在目標處停止的 Dijkstra 算法。若邊代價均相等且嚴格為正,BFS 與 UCS 找到的最優目標代價相同,平手時選擇則可能不同。若所有邊代價均為零,每個可達目標代價都是零,而 BFS 仍選擇邊數最少者。A* 按 排序;它的目標判定和重新開啟規則需要另外的假設,詳見啟發式搜尋一節。
練習
快速檢查
(所有邊代價為一,後繼次序為 、、、。寫出 BFS 直至目標的移除次序及回傳路徑;遞歸 DFS 回傳甚麼路徑?)
明確維持隊列,每次移除後寫出隊列內容。
解答 · 答案
隊列由 依次變成 、、、。直至目標的移除次序是 。 的父節點為 ,故路徑是 。遞歸 DFS 走 ,然後停止。
快速檢查
(邊為 代價 、 代價 、 代價 、 代價 、 代價 。執行 UCS,寫出確定標籤及回傳路徑,並解釋 的過期項。)
記錄每次插入及其優先值,並注意哪些項在移除時已過期。
解答 · 答案
以 確定 ,加入 ;以 確定 ,把 改善至 ,並加入 ;以 確定 ,把 改善至 。舊項 被忽略,因為 已確定,而且其優先值與目前的 不符。最後以 確定 ;父指標給出 ,代價為 。
快速檢查
(設 代價 、 代價 、 代價 。說明 UCS 在確定 時停止的結果,以及證明中哪一步失效。)
寫出確定 後的隊列,看哪一項先被移除。
解答 · 答案
處理 後隊列含 及 。算法確定 並回傳代價 ,但 的代價為 。到 的前綴代價 大於整條路徑代價 ;證明中的前綴界正依賴非負性。負環更會造成另一問題:最小值可能根本不存在。
快速檢查
(有限圖有環 和邊 。若遞歸 DFS 在 總是先訪問 再訪問 ,為何沒有標記時可能失敗?為何有標記的版本會終止並找到 ?)
從 起跟隨遞歸,寫出調用序列。
解答 · 答案
沒有標記時,遞歸在 間交替,永遠到不了 的第二個後繼。有標記時,第二次遇見 會跳過,接著便造訪 。一般而言,每個狀態最多進入一次,而每個有限後繼表最終都會處理完,所以遞歸終止。