State - 演算法筆記

若每次放寬的量極少時，可達到類似Best-first Search的功能。

A* Search（A*） g(x)+h(x)由小到大建立。

以BFS實作。

Iterative Deepening A* ... State 道生之，德畜之，物形之，勢成之。

《老子》 State 一件事物，以宏觀、全知的觀點望去，當前的模樣稱作「狀態」。

比方說：影片拍攝著一臺行駛中的車輛，底片的一格畫面，就是一個狀態。

狀態可以是一盤棋的局面，也可以是今天下午五點整的車輛分布情況。

狀態與狀態之間，可以是離散的（棋盤局面），也可以是連續的（車潮）。

Transition 每一個狀態都可以經過特定動作，改變現有狀態、轉移到下一個狀態。

例如象棋，我們可以移動一顆棋子到其他空地、移動一顆棋子收拾對手的棋子。

例如車潮，每一輛車可以踩油門、煞車、轉彎。

這樣的動作叫做「轉移」。

StateSpaceTree StateSpaceGraph 「狀態空間圖」。

所有狀態互相轉移，形成了圖論的有向圖。

狀態就是點，轉移就是邊，轉移成本就是邊的權重。

StateSpaceTree 「狀態空間樹」。

選定一個狀態，衍生各式各樣的狀態，形成一棵樹。

狀態空間樹無窮無盡。

狀態可能重複出現、四處散布。

用途：從「起始狀態」到其他狀態，求得轉移過程。

用途：從「起始狀態」到「目標狀態」，求得轉移過程。

搜尋順序 如何迅速找到目標狀態呢？ 狀態空間樹無窮無盡，只好一邊建立、一邊搜尋。

乍看離目標狀態比較近的狀態，優先搜尋。

如何衡量目標狀態的遠近呢？ 已經搜尋的狀態，累計轉移成本；尚未搜尋的狀態，估計轉移成本。

成本較低的狀態，優先搜尋。

costfunctiong(x)：起始狀態到當前狀態x，真正的轉移成本。

c(s⤳x)。

heuristicfunctionh(x)：當前狀態x到目標狀態，預估的轉移成本。

c̃(x⤳t)。

g(x)由小到大搜尋：首次遇到的目標狀態，就是g(x)最小的目標狀態。

h(x)由小到大搜尋：首次遇到的目標狀態，不一定就是g(x)最小的目標狀態。

因為h(x)不準確。

g(x)+h(x)由小到大搜尋：首次遇到的目標狀態，不一定就是g(x)最小的目標狀態。

因為h(x)不準確。

admissibleheuristic：h(x)小於等於真正的轉移成本。

h(x)≤c(x⤳t)。

consistentheuristic：h(x)滿足單調性。

h(x)≤c(x⤳y)+h(y)。

g(x)+h(x)由小到大搜尋，並且h(x)小於等於真正的轉移成本（不高估）：首次遇到的目標狀態，就是g(x)最小的目標狀態。

當h(x)預估精準，得以迅速走往目標狀態，不會四處閒逛。

g(x)+h(x)由小到大搜尋，並且h(x)滿足單調性：首次遇到的各種狀態，都是g(x)最小的狀態。

也就是說，每種狀態只需拜訪一次。

時間複雜度O(NDK)，其中狀態數量為N，分枝數量為D，轉移需時O(K)。

UVa2602983143214295715897049851004710603106531068210923101031070410067 UVa529851100731042210798111631137610314 搜尋演算法 圖論的遍歷演算法，進行改良，建立暨搜尋狀態空間樹。

Breadth-firstSearch（BFS） 忽視g(x)、h(x)，優先建立離起始狀態最近的狀態。

適用於轉移成本是固定值。

Depth-firstSearch（DFS） 忽視g(x)、h(x)，優先建立離起始狀態最遠的狀態。

適用於轉移成本是固定值。

Depth-limitedSearch（DLS）/過去稱作Depth-firstBranch-and-Bound（DFBnB） DFS的改良版本。

限制建立的深度（或成本），當深度（或成本）太深就不再往下分枝衍生。

IterativeDeepeningDFS（IDS） DLS的改良版本。

反覆使用DLS，並逐次放寬深度限制。

若每次放寬的量極少時，可達到類似於BFS的功能。

Uniform-costSearch（UCS） g(x)由小到大建立。

以BFS實作。

IterativeLengtheningSearch（ILS） g(x)由小到大建立。

以IDS實作，逐次放寬g(x)的限制。

若每次放寬的量極少時，可達到類似UCS的功能。

Best-firstSearch h(x)由小到大建立。

以BFS實作。

RecursiveBest-firstSearch（RBFS） h(x)由小到大建立。

以IDS實作，逐次放寬h(x)的限制。

若每次放寬的量極少時，可達到類似Best-firstSearch的功能。

A*Search（A*） g(x)+h(x)由小到大建立。

以BFS實作。

IterativeDeepeningA*Search（IDA*） g(x)+h(x)由小到大建立。

以IDS實作，逐次放寬g(x)+h(x)的限制。

若每次放寬的量極少時，可達到類似A*的功能。

Memory-boundedA*Search（MA*）/SimplifiedMemory-boundedA*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必須維護priorityqueue，還得indexing，因此BFS的執行速度通常比起IDS慢上許多，而且記憶體用量也大上許多。

IDS逐步放寬g(x)或者g(x)+h(x)的限制，不必比較成本大小。

這使得IDS不需要priorityqueue。

搜尋策略 forwardsearch：正向搜尋。

起始狀態建立狀態空間樹，從中搜尋目標狀態。

backwardsearch：反向搜尋。

目標狀態建立狀態空間樹，從中搜尋起始狀態。

bidirectionalsearch：雙向搜尋。

起始狀態、目標狀態分別建立狀態空間樹，搜尋共同狀態。

實作時，通常是輪流衍生。

狀態空間樹輪流增加一層，直到兩邊出現共同狀態。

perimetersearch：周界搜尋。

起始狀態建立狀態空間樹，儲存所有狀態，直到記憶體幾乎用光。

然後目標狀態建立狀態空間樹，直到出現儲存過的狀態。

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

beamsearch：柱狀搜尋。

限制狀態空間樹每一層的狀態數目。

當某一層抵達上限後，該層後來產生的狀態皆捨棄。

randomsearch：隨機搜尋。

隨機決定衍生哪些狀態。

heuristicsearch：啟發搜尋。

按照經驗法則，決定衍生哪些狀態。

例如台灣的交通網，西部比東部密集。

從基隆到屏東，首先去台北，而不是去宜蘭──根據交通網密度，台北可能更快到達屏東。

ICPC5098 搜尋技巧 branching：視情況衍生分枝。

逐漸增加成本下限，逼近正確答案；一旦超過成本上限，立即停止分枝。

pruning：參照問題本身的特殊限制，裁剪狀態空間樹，避開冗餘子樹。

好處是減少搜尋時間。

bounding：搜尋時，隨時檢查成本。

成本太壞，就不再往深處搜尋；成本足夠好，也不必往深處搜尋。

好處是減少搜尋時間。

tie-breaking：搜尋時，當g(x)或者g(x)+h(x)平手，則比較h(x)，優先搜尋h(x)較小的狀態，以便提早抵達目標狀態。

memoization：記錄所有遭遇到的狀態，避免狀態空間樹重複衍生相同狀態。

當記憶體不足時，也可以只記錄一部分的狀態。

indexing：狀態編號，方便memoization。

當記憶體不足時，indexing可以改為hashing。

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

https://www.redblobgames.com/pathfinding/a-star/introduction.html http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html 應用：3JugsProblem 3JugsProblem 手邊有三個裝水的容器，容量由大到小分別是X公升、Y公升、Z公升，都沒有刻度。

其中X公升的容器已經裝滿水了。

問題：如何在這三個容器之中，將水倒來倒去，使得其中一個容器恰有W公升的水？ 資料結構 使用三個變數記錄容器的容量。

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

三個容器的裝水情況，視作一個狀態。

intcapacity[3]={X,Y,Z}; structState{intwater[3];}; 起始狀態：一個滿容器、兩個空容器 一開始只有X公升的容器裝滿水，另外兩個容器沒有裝水。

Stateinit() { States; s.water[0]=capacity[0]; s.water[1]=0; s.water[2]=0; returns; // 簡單的寫法 // return(State){{capacity[0],0,0}}; } 目標狀態：其中一個容器裝了W公升的水量 boolgoal(States) { returns.water[0]==W||s.water[1]==W||s.water[2]==W; } 狀態轉移：把A容器的水倒入到B容器中 兩種情形： 一、A水量不夠、B剩餘容量太多，倒不滿B，A沒有剩水。

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

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

Statepour(States,inta,intb) { intw=min(s.water[a],capacity[b]-s.water[b]); s.water[a]-=w; s.water[b]+=w; returns; } 成本 倒一次水，算一個步驟。

成本定為1。

空間複雜度 為了避免同樣的狀態重複出現、重複衍生，只好記錄所有遭遇過的狀態。

三個容器的水量範圍是0~X公升、0~Y公升、0~Z公升，所有狀態總共(X+1)(Y+1)(Z+1)個。

空間複雜度O(XYZ)。

//假設三個容器都不超過100公升 boolvisit[100][100][100]; 時間複雜度 倒水方式總共3⋅2種。

也就是說，一個狀態衍生O(3⋅2)個狀態。

時間複雜度O(XYZ⋅3⋅2)=O(XYZ)。

搜尋演算法：BFS 判斷起始狀態是否能夠轉移到目標狀態。

voidBFS() { boolvisit[100][100][100]; memset(visit,false,sizeof(visit)); States=init(); visit[s.water[0]][s.water[1]][s.water[2]]=true; if(goal(s)){cout<=0;--j) { States=rev_index(path[j]); cout<=0&&x<3&&y>=0&&y<3; } intIDAstar(intx,inty,intgx,intprev_dir,int&bound,bool&ans) { inthx=h(board); if(gx+hx>bound)returngx+hx; //超過深度，回傳下次的bound if(hx==0){ans=true;returngx;} //找到最佳解 intnext_bound=1e9; for(inti=0;i<4;++i) //四種推動方向 { intnx=x-dx[i],ny=y-dy[i]; //空格的新位置 if(rev_dir[i]==prev_dir)continue; //避免來回推動 if(!onboard(nx,ny))continue; //避免出界 solution[gx]=i; //記錄推動方向 swap(board[nx][ny],board[x][y]); //推動方塊 intc=IDAstar(nx,ny,gx+1,i,bound,ans); if(ans)returnc; next_bound=min(next_bound,c); swap(board[x][y],board[nx][ny]); //回復原本狀態 } returnnext_bound; } void8puzzle() { if(!check_permutation_inversion(board)) { cout<####### |__|_|### |____|____####### ## ######### constintdx[4]={1,0,-1,0}; //四種方向 constintdy[4]={0,1,0,-1}; //記於陣列 constintX=9,Y=9; //迷宮大小。

一個長方形迷宮。

intsx=1,sy=0; //入口座標 inttx=7,ty=8; //出口座標 charmaze[X][Y]; //迷宮 boolvisit[X][Y]; //memoization intans=-1; //記錄是否找到解 //老鼠座標仍在迷宮裡 boolinmaze(intx,inty) { returnx>=0&&x=0&&y=0&&x=0&&y=0&&n.x=0&&n.yd; cout<p) cout<x<y<0 BayesNetwork（BayesianNetwork） 「貝葉斯網路」。

無向圖改成有向圖。

http://www.cs.cmu.edu/~epxing/Class/10708-17/lecture.html MarkovDecisionProcess MarkovDecisionProcess 「馬可夫決策過程」。

已經有詳細教材，就不再重複整理了： http://ai.berkeley.edu/lecture_slides.html http://www.cs.berkeley.edu/~pabbeel/cs287-fa12/slides/mdps-exact-methods.pdf http://rail.eecs.berkeley.edu/deeprlcourse/ 大致上就是MarkovChain額外加上各種動作。

以DynamicProgramming找到兩個狀態之間機率最大的路徑。

類神經網路、馬可夫決策過程（以時刻展開），構造大同小異，於是最近計算學家拿類神經網路的計算設備來研究馬可夫決策過程。

應用：Pac-Man