State Space Search

State

一件事物,以宏觀、全知的角度望去,所處的模樣稱作「狀態」。舉個容易揣摩、想像的實際例子:影片拍攝著一件正在動作中的車輛,影片的底片,其中一格的畫面,就是一個狀態。

狀態可以是一局棋的盤面,也可以是今天下午五點整時的車潮(或說成「車輛的分佈情況」就更貼切些)。狀態們之間,可以是不連續的(棋盤局面),也可以是連續的(車潮)。

Successor Function

狀態們可以經過特定的幾個動作,來改變現有狀態,讓現有狀態進行移轉。

例如象棋,我們可以選擇移動一顆棋子到其他空地,或者移動一顆棋子去收拾對手的棋子。例如流動中的車潮,每一輛車可以踩油門、煞車、轉彎。這些動作們,這些令現有狀態進行移轉的動作們,稱作Successor Function。

Cost

每個狀態都會有固定的「成本(價值)」,可想做是狀態本身的好壞程度,抑或是描述狀態的一種指標。

另外,狀態與狀態之間也都會有固定的「成本(價值)」,可想做是狀態進行移轉時所需要的花費、開銷。

State Space

一件事物其所有狀態所構成的集合。

一般來說,State Space可從某幾個狀態開始,然後藉由Successor Function不斷衍生而得。

State Space Search

中譯「狀態空間搜尋」,即是搜尋一件事物的所有狀態,以求得答案。

目前常見的作法是:將所有狀態依照衍生關係相連成圖,圖可以是樹狀圖或網狀圖,然後在圖上移動,搜尋各種狀態。

能夠用State Space Search解決的問題

一個問題要是可以化作一群狀態,且所有狀態本身的性質(成本)都永恆不變、所有狀態與狀態相互之間的關係(衍生方式、成本)都永恆不變,則可以使用State Space Search。

State Space Search
Search Tree(Rooted Tree Model)

目的

找出從一個狀態移轉到另一個狀態的路徑及成本。或者是找出一個狀態移轉到其他狀態們的路徑及成本。

搜尋樹(Search Tree)

依照狀態間的衍生關係,從一個起始狀態開始向外擴張延展,衍生出各式各樣的狀態,形成一顆樹,便是「搜尋樹」。此時可以用遍歷一棵樹的演算法,從起始狀態開始搜尋「搜尋樹」上的每個狀態,找出起始狀態到其他狀態的移動路線及成本。

簡言之,就是選定起點,不斷串連,形成一棵「搜尋樹」。遍歷此樹,以求得起始狀態與其他狀態們的關係。

樹是相當優雅的資料結構,具有許多美麗的特性,以及簡捷的演算法。串連狀態成樹,無非是想利用樹的特性及演算法。

1. 搜尋樹從起始狀態開始衍生至無限遠處。
2. 有些狀態可能會重複出現,並重複衍生。
3. 狀態進行移轉的成本,繪於其分支上。(通常只考慮移轉的成本,而不考慮狀態自身的成本。)
4. 從起始狀態移轉到其他狀態們的成本,就是其路徑上的成本做累加、求總和。(通常只加不乘。)

搜尋樹和一般的樹的差異

1. 搜尋樹有明確的樹根。
2. 搜尋樹的分支有方向性,衍生關係不見得可逆。
3. 搜尋樹的分支擁有成本。
4. 搜尋樹可無限延伸。
5. 搜尋樹的不同節點會擁有相同資訊(同一個狀態重複出現在不同節點上)。

以搜尋樹解決問題

1. 判斷問題是否是在求狀態與狀態之間進行移轉的路徑、成本。
2. 確立Successor Function、State Space、以及狀態進行移轉的成本。
3. 設定好起始狀態(及目標狀態,如果有的話),建立搜尋樹,並選擇適當的遍歷演算法來進行搜尋。

以兩個棋盤盤面之間所需的移動步數為例:Successor Function是下棋規則;State Space則是所有合法的盤面(棋子不疊合、位置不踰矩);狀態進行移轉的成本都是一。

一個狀態,除了可以是一整個棋盤盤面,也可以是目前所處的一個地點。例如最短路徑問題:Successor Function是圖的連接情形;State Space則是所有可處的地點;狀態進行移轉的成本,則對照圖上各個邊的成本。

搜尋樹搜尋技巧

pruning

pruning是指裁剪搜尋樹,去掉多餘子樹。裁剪時一般都是參照題目給定的限制。亦有用於特殊限制的特殊裁剪法,例如α-β Pruning。

好處:減少搜尋時間。

結合branch and bound

由於搜尋樹可以漫無止境的滋長,而電腦記憶體有限、人類時間有限,所以只好一邊走訪搜尋樹,一邊衍生分支、建立搜尋樹,走到哪,建到哪,便是branch and bound的精神。更詳細的來說:

branching是指建立適當的分支、走訪適宜的分支。建立分支時,一般是以狀態的衍生情形來做分支,使近似的狀態相互靠近;走訪分支時,即是往近似的狀態移動。

好處:有規律的搜尋狀態,更容易找到目標狀態。

bounding是指搜尋時隨時檢查目前的成本,一旦成本超過容忍範圍,就不再往深處搜尋。一般有兩種情形:一、目前成本太壞,不再往深處搜尋;二、目前的成本足夠好,不需往深處搜尋。

好處:減少搜尋時間。

結合backtracking

令分支有規律性,如此在搜尋途中,一旦遇到不好的狀態,即可馬上回溯,避免繼續往深處搜尋並非目標狀態的狀態,達到近似於pruning的效果。

好處:減少搜尋時間。

結合memoization

將搜尋當中遭遇過的狀態紀錄起來,可用來避免搜尋樹重複衍生相同的狀態。

好處:減少搜尋時間。

UVa 233

搜尋樹遍歷演算法

在中繼狀態時,計量成本的想法

在搜尋搜尋樹的途中,正位於一個中繼狀態,若想要找出起始狀態移轉到目標狀態的成本,此時有兩種計量(估量)成本的想法可供運用:

1. evaluation function〔常寫作g(x)〕:從起始狀態到狀態 x ,實際所花費的成本。
2. heuristic function 〔常寫作h(x)〕:從狀態 x 到目標狀態,預計所花費的成本。
1. 要找成本最小的路徑,就是在搜尋樹中尋找g(x)最小的狀態x。反之亦然。
2. 在搜尋樹上,離起始狀態越近的狀態,其g(x)通常也會比較小。反之亦然。
只使用 g(x) 的搜尋方式,被歸類為 blind search。
使用到 h(x) 的搜尋方式,被歸類為 heuristic search(informed search)。

g(x)其實就是從一個狀態移轉到另一個狀態的成本。至於h(x)是知道目標狀態時,直接觀察現有狀態與目標狀態之間的差異,推估而得的成本。g(x)+h(x)常用來逼近真正的成本。

在blind search當中,若是搜尋時採用g(x)由小到大的順序,則最先搜尋到的會是g(x)最小的狀態。這個觀點常用於找出起始狀態與目標狀態之間,其成本最小的路徑。

在heuristic search當中,有一個重要的定理:當h(x)小於等於真正將要花費的成本(不高估),搜尋時採用g(x) + h(x)由小到大的順序,則最先遇到的目標狀態,其g(x)會是最小的。這個性質常用於找出起始狀態與目標狀態之間,其成本最小的路徑。

heuristic search的功能是在搜尋搜尋樹時,隨時估計目標節點應該會在哪一個方向,然後往乍看之下較正確的方向走去。

搜尋樹遍歷演算法

乍看之下千變萬化、多采多姿,但其實大同小異、殊途同歸。於此提綱挈領、點到為止:

Breadth-first Search(BFS)
忽視g(x)、h(x),先拜訪所有鄰近的節點。通常用於每個分支的成本都一樣的時候。

Depth-first Search(DFS)
忽視g(x)、h(x),先走到最深的地方。通常用於每個分支的成本都一樣的時候。

Depth-limited Search(DLS)/ 過去曾稱作 Depth-first Branch-and-Bound(DFBnB)
DFS的改良版本。限制搜尋的深度(或成本),當深度(或成本)太深就不再往下搜尋、不再往下分支。

Iterative Deepening DFS(IDS)
DLS的改良版本。反覆使用DLS,並逐次放寬深度限制。
若每次放寬的量極少時,可達到類似於BFS的功能。

Uniform-cost Search(UCS)
g(x)最小的先分支。採用BFS方式實作。

Best-first Search
h(x)最小的先分支。採用BFS方式實作。

Recursive Best-first Search(RBFS)
h(x)最小的先做分支。採用IDS方式實作,逐步放寬h(x)的限制。

A* Search(A*)
g(x)+h(x)最小的先做分支。採用BFS方式實作。

Iterative Deepening A* Search(IDA*)
g(x)+h(x)最小的先做分支。採用IDS方式實作,逐步放寬g(x)+h(x)的限制。
若每次放寬的量極少時,可達到類似於A*的功能。

Weighted-A* Search(WA*)
a*g(x)+b*h(x)最小的先做分支,a b是可調整的比例參數。其餘同A*。

Weighted-IDA* Search(WIDA*)
a*g(x)+b*h(x)最小的先做分支,a b是可調整的比例參數。其餘同IDA*。

Memory-bounded A* Search(MA*) / Simplified Memory-bounded A* Search(SMA*)
限制記憶體用量的A*。當queue全滿時,就刪除其中g(x)最大的狀態。

Bidirectional Search(BS)
分別從起始狀態和目標狀態開始,分頭交互輪換進行BFS,直到兩端碰觸到同樣的節點為止。

Perimeter Search(PS)
當起始狀態和目標狀態其中一個是固定狀態的時候,BS的改良版本。
將固定的那端做BFS到記憶體幾乎用光並且存著,然後不固定的另一端開始做BFS,直到碰到為止。
不固定的那端採用A*則稱作PS*,採用IDA*則稱作IDPS*。

Beam Search
限制搜尋樹每一層的節點個數上限。當某一層的節點個數到達上限,以後該層生成之節點皆捨棄。

這裡有一些可用搜尋樹解決的題目。

UVa 260 298 314 321 429 571 589 704 985 10047 10603 10653 10682 10923 10103 10704 10067

另外也特地挑出有一些得以利用heuristic function的題目。

UVa 529 652 851 10181 10073 10422

搜尋樹與其他樹

Backtracking Dendrogram v.s. Search Tree

Backtracking的樹狀結構和搜尋樹不盡相同。若將Backtracking硬套在搜尋樹上面,則Backtracking的樹狀結構為有限深度,目標狀態都集中在葉子,遍歷演算法固定用DFS。

許多不明究理的人,把一個利用Backtracking解決的問題,說成是利用DFS解決的問題,然而兩者並無直接關係,概念也不相同。也有人會把一個利用State Space Search解決的問題,說成是利用DFS解決的問題,然而兩者之概念並不對等。

Backtracking、State Space Search是解題策略,DFS則是圖的遍歷演算法,意境截然不同,特此澄清。

Binary Search Tree v.s. Search Tree

Binary Search Tree和搜尋樹不盡相同,但是本質上兩者都是將答案置於樹上做搜尋。

State Space Search
Local Search(Graph Model)

目的

找出具有最佳成本的狀態。

Local Search

依照關係連起所有狀態,成為一張網狀圖。在圖上選定一個恰當的起點,然後開始在圖上遊走,盡可能找出最好的狀態。

【待補文字】

Local Search技巧

結合branch and bound

概念同於搜尋樹的branch and bound。

結合memoization

概念同於搜尋樹的memoization。

Local Search演算法

Hill Climbing

中文譯做「登山法」。【待補文字】

Simulated Annealing

中文譯做「模擬退火」。【待補文字】

Local Beam Search

【待補文字】

Genetic Algorithm

中文譯做「基因演算法」【待補文字】

UVa 10715

Tabu Search

【待補文字】

State Space Search
Ant Colony System

目的

找出多個狀態進行一連串移轉的路徑及成本。

Ant Colony System

【待補文字】

3 Jugs Problem

3 Jugs Problem

手邊有三個裝水的容器,容量由大到小分別是X公升、Y公升、Z公升,都沒有刻度。其中X公升的容器已經裝滿水了,問題是:如何將水在這三個容器中倒來倒去,使得其中一杯剛好有C公升的水?

資料結構

使用三個變數來記錄容器的容量,再使用三個變數來記錄容器中的水量。

Initial State:空容器

把三個容器裝水的情形視做一個狀態。一開始所有容器都是空的,沒有裝水。

Goal State:有一個容器裝了C公升的水量

Successor Function:把A容器的水倒入到B容器中

有兩種情形需要考慮。甲、A水量不夠、B剩餘容量太多,倒不滿B,A沒有剩水;乙、A水量太多、B剩餘容量不夠,B被倒滿,A還有剩水。

Cost

倒一次水算一個步驟,成本可定為一。

State Space:Memoization與空間複雜度

為了避免同樣的狀態循環不斷的發生,所以就把遭遇過的狀態給記錄下來。三個容器的水量只有可能是0~X公升、0~Y公升、0~Z公升,所以所有的狀態一共只有(X+1)*(Y+1)*(Z+1)個,可寫成O(XYZ)個。

時間複雜度

一個狀態總共可以衍生出三種裝水後、三種倒水後、C(3,2)種相互裝倒水後的狀態,也就是說每一個狀態都需要衍生O(3!)次,所以時間複雜度一共是O(XYZ * 3!)。

程式碼(BFS)

這種寫法可以找到步驟數最小的答案。

UVa 10603

Water Jug Problem

Water Jug Problem

手邊有一個三公升的容器和一個五公升的容器,都沒有刻度。另外身邊還有一個水龍頭和一個水槽,我們可以用水龍頭的水裝滿容器,也可以把容器的水倒入水槽(有點浪費),或者把一個容器的水倒入到另一容器、裝滿另一容器。如何利用這兩個容器量出四公升的水?

這個問題跟3 Jugs Problem相當類似。

資料結構

使用兩個變數來記錄容器的容量,再使用兩個變數來記錄容器中的水量。

Initial State:空容器

把兩個容器裝水的情形視做一個狀態。一開始兩個容器都是空的,沒有裝水。

Goal State:其中有一個容器裝了四公升的水

Successor Function:用水龍頭的水裝滿容器

用容器接水龍頭的水,只要沒裝滿,就不能確定裝了多少水量。要能準確的量出裝了多少水,就一定要裝滿才行。

Successor Function:把容器的水倒入水槽

容器也可以清空,如果有必要的話。

Successor Function:把A容器的水倒入到B容器中

有兩種情形需要考慮。甲、A水量不夠、B剩餘容量太多,倒不滿B,A沒有剩水;乙、A水量太多、B剩餘容量不夠,B被倒滿,A還有剩水。

Cost

倒一次水算一個步驟,成本可定為一。

State Space:Memoization與空間複雜度

為了避免同樣的狀態循環不斷的發生,所以就把遭遇過的狀態給記錄下來。兩個容器的水量只有可能是0~3公升以及0~5公升,所以所有的狀態一共只有(3+1)*(5+1)=24個。

時間複雜度

一個狀態總共可以衍生出兩種裝水後、兩種倒水後、兩種相互倒水後的狀態,也就是說每一個狀態都需要衍生6次,所以時間複雜度一共是O(24* 6)。

找出一種量出四公升的方法(BFS)

這種寫法可以找到步驟數最小的答案。

UVa 571

延伸閱讀:Modeling

這裡要說明一個有趣的Modeling方法。

首先建立只有第一象限的二維座標系,其中一軸為三公升的容器,範圍是零到三,另外一軸為五公升的容器,範圍是零到五,然後畫上很多斜線:

每個座標都代表著兩容器的水量,我們描一個點來表示目前兩容器的水量。一開始起點位於原點,代表著兩個容器都沒有裝水:

如果三公升的容器填滿水或倒光水,點就往三公升軸的一端或另一端移動到底;五公升的容器亦同。如果兩個容器互相倒水,點就往斜線方向移動到底:

至此,Water Jug Problem已經變成了:由原點畫線,只能畫直線、橫線、斜線並畫到底,然後畫到座標其中一個維度的數值是四的地方。

8 Puzzle Problem

8 Puzzle Problem

上下左右推動一個缺了一格的3x3方塊拼圖,讓它排列整齊。是小時候的回憶:http://www.permadi.com/java/puzzle8/

目前最常見的解決方法,便是將盤面化作「狀態」,直接使用State Space Search,所有狀態都搜一搜後就有答案。沒有花心思去想一些推動方塊的策略,而直接Search,感覺上挺隨便的。

處理這個問題時,每塊方塊都標上數字編號,會更清楚一些。

15 Puzzle Problem

就是改為4x4啦!相關數學資料:http://mathworld.wolfram.com/15Puzzle.html

檢查不合理的盤面:Permutation Inversion

http://mathworld.wolfram.com/PermutationInversion.html

http://bal4u.dip.jp/mt/program/2006/05/uva-10181-15puzzle-problem-2.html

當一個盤面的inversion的個數是偶數的時候,表示該盤面可以從排列整齊的狀態,經過一連串推動而得;如果個數是奇數,則表示該盤面不合理、不可能存在。另外還要考慮空格的位於哪一列。此處省略原理說明。

heuristic function

這裡提供兩種不高估的方法,不高估的理由都很明顯:

1. 不在正確位置上的方塊個數。
2. 每個方塊與其正確位置的 city block distance(Manhattan distance)的總和。

實做:使用IDA*

其他

如果有需要一次計算大量的8 Puzzle Problem,那麼可以考慮從排列整齊的狀態當作起始狀態,建立搜尋樹,並將搜尋過的狀態、路徑、成本都紀錄起來,存於表格當中,以後便可以從表格內直接找到各種盤面的答案,不需再計算。

UVa 652 10181 10085