State(Under Construction!)

道生之,德畜之,物形之,勢成之。《老子》

State

一件事物,以宏觀、全知的角度望去,當前的模樣稱作「狀態」。比方說:影片拍攝著一臺行駛中的車輛,底片的一格畫面,就是一個狀態。

狀態可以是一盤棋的局面,也可以是今天下午五點整的車輛分布情況。狀態與狀態之間,可以是離散的(棋盤局面),也可以是連續的(車潮)。

每一個狀態都可以經過特定動作,改變現有狀態、轉移到下一個狀態。例如象棋,我們可以移動一顆棋子到其他空地、移動一顆棋子收拾對手的棋子。例如車潮,每一輛車可以踩油門、煞車、轉彎。這樣的動作叫做「轉移函數Transition Function」。

所有狀態依照衍生關係互相連結,形成了有向圖。狀態就是點,轉移函數就是邊,轉移的成本就是邊的權重。

State Space Tree(Under Construction!)

State Space Tree

選定一個狀態,衍生各式各樣的狀態,形成一棵樹,便是「狀態空間樹」。

狀態空間樹無窮無盡衍生。同一個狀態很可能重複出現、重複衍生。

用途:Single Source Shortest Paths

狀態空間樹的主要用途是:從「起始狀態」到其他狀態,求得轉移過程。每當轉移狀態,就要累加成本。

狀態空間樹無窮無盡衍生,無法預先建立,只好一邊建立、一邊搜尋。使用遍歷演算法DFS、BFS,建立暨搜尋狀態空間樹。

用途:Point-to-Point Shortest Path

狀態空間樹的另一個用途是:從「起始狀態」到「目標狀態」,求得成本最少的轉移過程。

一般來說,是以起始狀態建立狀態空間樹。狀態空間樹無窮無盡衍生,於是目標狀態很可能重複出現,散布在狀態空間樹當中。

搜尋順序

如何迅速找到目標狀態呢?優先建立離目標狀態比較近的狀態。

     cost function g(x):起始狀態到當前狀態x,已知的、真正的轉移成本。
heuristic function h(x):當前狀態x到目標狀態,未知的、預估的轉移成本。
admissible heuristic:h(x)小於等於真正的轉移成本(不高估)。
consistent heuristic:h(x)滿足單調性。h(x) ≤ c(x→y) + h(y)。

以g(x)由小到大的順序建立狀態空間樹,首次遇到的目標狀態,就是g(x)最小的目標狀態。

以h(x)由小到大的順序建立狀態空間樹,首次遇到的目標狀態,不一定就是g(x)最小的目標狀態。因為h(x)不準確。

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

以g(x) + h(x)由小到大的順序建立狀態空間樹,並且h(x)小於等於真正的轉移成本(不高估),首次遇到的目標狀態,就是g(x)最小的目標狀態。當h(x)估計的很精準,可以迅速走到目標狀態,而不會四處閒逛、四處兜圈。時間複雜度難以分析。

以g(x) + h(x)由小到大的順序建立狀態空間樹,並且h(x)滿足單調性,首次遇到的每種狀態,都是g(x)最小的狀態。也就是說,每種狀態只需拜訪一次,等同圖論的最短路徑演算法。時間複雜度為O(ndk),其中狀態種類為n,分枝為d,狀態轉移需時O(k)。

UVa 529 851 10073 10422 10798 11163 11376 10314

搜尋演算法

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實作。

Iterative Lengthening Search(ILS)
g(x)由小到大建立。以IDS實作,逐次放寬g(x)的限制。
若每次放寬的量極少時,可達到類似UCS的功能。

Best-first Search
h(x)由小到大建立。以BFS實作。

Recursive Best-first Search(RBFS)
h(x)由小到大建立。以IDS實作,逐次放寬h(x)的限制。
若每次放寬的量極少時,可達到類似Best-first Search的功能。

A* Search(A*)
g(x)+h(x)由小到大建立。以BFS實作。

Iterative Deepening A* Search(IDA*)
g(x)+h(x)由小到大建立。以IDS實作,逐次放寬g(x)+h(x)的限制。
若每次放寬的量極少時,可達到類似A*的功能。

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

名稱天花亂墜,令人眼花撩亂。其實只是搜尋順序的差別:Ø、g(x)、h(x)、g(x) + h(x),以及遍歷演算法的差別:BFS、IDS。

搜尋順序,習慣採用g(x)或g(x) + h(x),以求得最佳成本。

遍歷演算法,BFS系列,效率較差;IDS系列,效率較好。

假設狀態空間樹剛好是一棵二元樹,而目標狀態位於第N層的狀態。BFS搜尋的狀態數目是(1+2+4+8+...+2ᴺ),IDS搜尋的狀態數目是1 + (1+2) + (1+2+4) + ... + (1+2+4+8+...+2ᴺ),大約是前者的兩倍。如果狀態空間樹是K元樹,則大約是前者的K倍。

儘管BFS搜尋的狀態數目比起IDS少了許多倍,然而BFS必須維護priority queue,還得indexing,因此BFS的執行速度通常比起IDS慢上許多,而且記憶體用量也大上許多。

IDS逐步放寬g(x)或g(x) + h(x)的限制,不必在意每次DFS的遍歷順序。這使得IDS不需要priority queue。

搜尋策略

forward search:正向搜尋。起始狀態建立狀態空間樹,從中搜尋目標狀態。

backward search:反向搜尋。目標狀態建立狀態空間樹,從中搜尋起始狀態。

bidirectional search:雙向搜尋。起始狀態、目標狀態分別建立狀態空間樹,搜尋共同狀態。

實作時,通常是輪流衍生。狀態空間樹輪流增加一層,直到兩邊出現共同狀態。

perimeter search:周界搜尋。起始狀態建立狀態空間樹,儲存所有狀態,直到記憶體幾乎用光。然後目標狀態建立狀態空間樹,直到出現儲存過的狀態。

實作時,通常起始狀態採用BFS,目標狀態採用DFS、IDS、IDA*等節省記憶體的遍歷演算法。

beam search:柱狀搜尋。限制狀態空間樹每一層的狀態數目。當某一層抵達上限後,該層後來產生的狀態皆捨棄。

random search:隨機搜尋。隨機決定衍生哪些狀態。

heuristic search:啟發搜尋。按照經驗法則,決定衍生哪些狀態。例如台灣的交通網,西部比東部密集。從基隆到屏東,首先去台北,而不是去宜蘭,因為根據交通網密度,台北可能更快到達屏東。

實作時,通常是將經驗法則化為heuristic function,藉此調整搜尋順序。

ICPC 5098

搜尋技巧

branching:由於狀態空間樹可以漫無止境的滋長,而電腦記憶體有限、人類時間有限,所以只好一邊走訪狀態空間樹,一邊衍生分枝、建立狀態空間樹,走到哪,建到哪。逐漸增加成本下限,逼近正確答案;一旦超過成本上限,立即停止分枝。

pruning:參照題目給定的特殊限制,裁剪狀態空間樹,去掉多餘子樹。好處是減少搜尋時間。

bounding:搜尋時,隨時檢查目前的成本。目前成本太壞,就不再往深處搜尋;目前的成本足夠好,也不必往深處搜尋。好處是減少搜尋時間。

memoization:記錄所有遭遇到的狀態,避免狀態空間樹重複衍生相同狀態。當記憶體不足時,也可以只記錄一部分的狀態。當起始狀態固定不變時,可以充作lookup table。

indexing:所有狀態進行編號,以整數、二進位碼等形式呈現。好處是方便memoization。當記憶體不足時,indexing可以改為hashing,達到壓縮功效。

tie-breaking:priority queue於平手時,額外比較h(x)的大小,優先彈出h(x)較小的狀態。某些特殊情況下,可以提早抵達目標狀態,減少狀態數量:http://movingai.com/astar.html

UVa 233 10536 10941 690 ICPC 6010

應用:3 Jugs Problem

3 Jugs Problem

手邊有三個裝水的容器,容量由大到小分別是X公升、Y公升、Z公升,都沒有刻度。其中X公升的容器已經裝滿水了。

問題:如何在這三個容器之中,將水倒來倒去,使得其中一個容器恰有W公升的水?

資料結構

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

三個容器的裝水情況,視做一個狀態。

起始狀態:一個滿容器、兩個空容器

一開始只有X公升的容器裝滿水,另外兩個容器沒有裝水。

目標狀態:其中一個容器裝了W公升的水量

轉移函數:把A容器的水倒入到B容器中

兩種情形:

一、A水量不夠、B剩餘容量太多,倒不滿B,A沒有剩水。

二、A水量太多、B剩餘容量不夠,B被倒滿,A還有剩水。

不能只倒一些!原因是容器沒有刻度,無法精準的控制水量,無法保證最終結果正是W公升。

成本

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

空間複雜度

為了避免同樣的狀態重複出現、重複衍生,只好記錄所有遭遇過的狀態。三個容器的水量範圍是0~X公升、0~Y公升、0~Z公升,所有狀態總共(X+1)(Y+1)(Z+1)個。空間複雜度是O(XYZ)。

時間複雜度

倒水方式總共3⋅2種。也就是說,一個狀態衍生O(3⋅2)個狀態。時間複雜度是O(XYZ ⋅ 3⋅2) = O(XYZ)。

遍歷演算法:BFS

判斷起始狀態是否能夠轉移到目標狀態。

加碼求得起始狀態到目標狀態的轉移過程。

UVa 10603

應用:8 Puzzle Problem

8 Puzzle Problem

3×3方塊拼圖,缺了一格。上下左右推動方塊,讓它排列整齊。

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

4×4叫做15 Puzzle。N×M叫做Sliding Puzzle。

檢查不合理的盤面:Permutation Inversion

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

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

heuristic function

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

1. 不在正確位置上的方塊個數。
2. 每個方塊與其正確位置的 taxicab distance 的總和。

遍歷演算法:IDA*

UVa 652 10181 10085

應用:Rat in a Maze

老鼠走迷宮

老鼠很聰明,進入死胡同就會馬上回頭,不會傻傻的一直進入同一個死胡同。老鼠每一次重跑,都會越來越快。老鼠也會選擇看起來離乳酪比較近的路線。

一開始就已經背熟地圖,隨意找出一條路線。

由於原本的線條牆壁迷宮難以實作,不太適合初學者,所以這裡採用方塊牆壁迷宮,走一格當作是一步。

                  #########
                          #
_________         # ### ###
   __  __|        # #     #
| |____  |  --->  # ##### #
|  __  |_|        #     # #
|____|____        # ### ###
                  #   #    
                  #########

前面的程式碼只求出了老鼠的行走距離。想要印出老鼠走過的路線,必須新增一條陣列,記錄老鼠的軌跡。

一開始就已經背熟地圖,找出最佳路線。

使用BFS遍歷狀態空間樹,先遇到的目標狀態,會是成本最小的目標狀態。

搜尋過的狀態都會存放在queue裡面。要印出最佳路徑,可以在節點裡面新增加一個變數,記錄狀態的來源。

一開始不知道地圖,第一次走,隨意找出一條路線。

以下介紹兩種走迷宮的智慧:

有一種走迷宮的方式,叫做右手原則。當迷宮的入口、出口都在外牆,而且迷宮裡面沒有環狀路線,此時只要用右手一直摸著牆走,一定可以走出迷宮。右手原則其實就是一種DFS。各位可以仔細觀察影片,說不定老鼠真的懂右手原則喔!

在迷宮上隨意框一塊區域,如果只剩一個以下開口,則不必走進去,因為一定出不來;如果仍有兩個以上開口,則可以考慮走進去,有可能走得出來,也可能走不出來。如果老鼠一開始知道迷宮大小,也知道自己行走的方向、走了幾步路,如此老鼠隨時可以推敲出自己是不是走入了一個沒有出口的區域。

各位應該也能設計出許多種走迷宮的智慧。如果有興趣,可以上網搜尋一些老鼠走迷宮的影片來研究。

一開始不知道地圖,再走幾次,逐次找出更佳路線。

如果老鼠記憶力很強,記得走過的地點(甚至是路),我們在實作時,就可以運用memoization,把搜尋過程中遭遇到的地點統統記錄起來。老鼠的記憶力,就變成了電腦的記憶體。

老鼠行動時,會有一定機率去探索未知的區域,並且會將探索結果記在腦海中。然而現實中,老鼠的記憶力有限,也就是電腦的記憶體有限,不能記得所有地點。想要模擬老鼠的記憶力,可以限制電腦的記憶體用量,當記憶體用罄時,就忘掉一些地點。例如queue、hash table都是不錯的選擇。

製造迷宮(Wilson's Algorithm)

http://daviddr.blogspot.com/2009/12/blog-post_10.html

http://maskray.me/blog/2012-11-02-perfect-maze-generation

http://weblog.jamisbuck.org/2011/1/20/maze-generation-wilson-s-algorithm

http://bl.ocks.org/mbostock/c03ee31334ee89abad83

延伸閱讀:步伐儲存方式

西洋棋騎士。

UVa 10426 10463 10477 633

方塊滾動。

UVa 10021

應用:Pathfinding

Pathfinding

即時戰略遊戲,用滑鼠點選角色的目的地,角色自動繞過障礙物,找到最短路徑。

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Game Tree(Under Construction!)

Game Tree

兩人對陣,輪流動作。

所有的狀態形成二分圖。不過這不是我們要討論的重點。

兩人對陣,輪流動作。這樣的狀態空間樹,稱作「遊戲樹」。

遊戲樹的主要用途是:從「起始狀態」到「勝負已分狀態」,求得轉移過程。

通常我們想求最佳轉移過程。先手嘗試勝利;就算先手不能勝利,也要盡量拖延、讓後手難以勝利。相對地,後手也是這樣想。

max層是從下層各個數字中取最大值所算出來的層
min層是從下層各個數字中取最小值所算出來的層
也有顛倒定義的。兩種都有人用。

遊戲樹比狀態空間樹所算的東西還多。狀態空間樹每個節點的成本,是由樹根往樹葉方向慢慢推導出來的。遊戲樹除了要算狀態空間樹的成本之外,另外在回溯時還要再算min值(或max值)的結果──更詳細的說,遍歷到樹葉(勝負已定)並得到樹葉的成本之後,回溯時還要利用樹葉的成本算出樹上各個節點的min值(或max值)。

求最少步數的狀況下
先手贏了當然取min較好 先手在min層
可是要是先手輸了...先手得盡量拖步數...此時沒辦法取min...反而要取max
解決方法是
輸的時候的把步數設定成由很大的數字開始減少
例如N步是零步 N-1步是一步
取min時會先取到贏的步數,取不到贏的才會取到輸的步數

搜尋技巧:α-β Pruning

使用條件是遍歷時必須採用DFS。

有兩部分 兩部分可獨立coding

1. 相鄰的兩層: (alpha pruning)

 若這層是max,上層是min
 -> max層數字大於min層數字就沒意義 砍

 coding時傳一個參數是上層的數字 一般稱alpha

2. 隔一層的兩層:  (beta pruning)

 若這層是max,上上層是max
 搜這層時 其數字底限可由上上層目前之數字決定
 大於上上層才會有機會更新上上層的數字
  (同理上上...上上層也一樣,不過只要作到上上層就有連鎖效果了)
 實際上沒砍到啥東西...但是配合alpha後就可以砍到東西

 coding時傳一個參數是上上層的數字  一般稱beta
一層min一層max  不好coding 變成要寫兩個function
可以改成都是max  然後在算min層的的時候數字都先加負號 取min後再用負號還原
如此只要寫一個function
假設這層是max
此時alpha的意義是成本上限,beta的意義是成本下限。

alpha-beta pruning的精髓,就是求得每個節點的成本上下限。
每當遭遇樹葉(勝負已分),回溯,求得成本,順手更新節點的成本上下限。
如果從葉子開始回溯時累加步數  就沒辦法用beta  而且也很難coding
從根往下走時就開始計步  世界就變得簡單些了
可以逐步增加成本,把alpha和beta設定為相同,
達到類似IDS的效果。

甚至可以二分搜尋成本,
並且配合memoization。

UVa 682 10111 10838 ICPC 4451

搜尋演算法:Monte-Carlo Tree Search

隨機搜尋,設定為勝率。

應用:Tic-tac-toe

Tic-tac-toe