高木鎮樓
這東西我從去年看到時就有點興趣,當個筆記和整理把它寫下來。主要就是問題描述和自己爬爬文章的一些看法和認識。
更多的是想和大家分享,並在後面希望能和我討論討論 :>
搜尋(Search)演算法顧名思義,是指用來解決搜尋問題的演算法。
在定義的問題空間中尋找一個、多個符合條件的解。
最簡單的例子就是在一個數列中尋找某個指定值。
廣泛來說,類似計算最小生成樹(Minimum Spanning Tree)算是一種搜尋問題。
—在給定的圖中尋找一個特定的子圖。
狀態空間(State Space)則是一種抽象概念,它是描述一個問題所有可能的狀態建構的空間。
因此狀態空間搜尋演算法,也就是應用在狀態空間中的搜尋演算法。
問題是這樣的,給定一個起始狀態、目標狀態與可操作集合。
在狀態空間中找出一條路徑,可以將起始狀態變成目標狀態。
我在查資料的過程中看到不少描述這種問題的名稱。
有組合最佳化(Combinatorial Optimization)、約束規劃問題(Constrained Programming)等等...
上面比較偏名詞解釋,接下來舉個比較實際的例子。
這也是我去年在寫UVa. 11007的時候遇到的問題。
題目也很好理解,總之就是給了你一個魔術方塊,然後把它解出來。
當下的第一個想法是源自我有玩過魔術方塊的經驗。
我可以直接將公式建出來並帶入就行了。
雖然是這樣說...但誰會想要做這種苦力。![]()
不過理論上來說這應該是我在那時候知道的時間複雜度最低的解法才是
因此也大概有頭緒大概是廣度優先搜尋(Breadth-First Search, BFS)之類的作法。
建立在魔術方塊在一個步數內必有解的前提上。
假設魔術方塊有六種操作,BFS的做法如下。
初始化:
1. 將初始狀態放入佇列(Queue)當中。
搜尋:
1. 將「狀態」從 Queue 取出
2. 計算「狀態」的六種操作
3. 判斷使否達成目標狀態
4. 將未經歷過的狀態放入 Queue
5. 重複 1. 直到經歷目標狀態
這是一個簡單的BFS的做法,以圖來示的話大致上可以表示成這樣。
而我當初在查題解的時候看到了雙向搜尋的優化方法。
透過同時從起始狀態與目標狀態搜尋,可以得到更加快速的效率。
從上圖可以清楚的看到。
假設圓面積是時間複雜度的話。
明顯的用雙向搜尋可以有效的加快搜尋效率。
用數學的方式來計算的話,假設操作集合的大小為P、距離為d。
那麼原先的時間複雜度會是
,而雙向搜尋優化後從目標狀態和初始狀態搜尋皆是
。 即使相加後還是與原先差距非常的大。
(上圖的面積雖然分別是
與
的差別。 不過那只是將狀態以點表示在二維歐幾里得空間,實際上並不是如此。)
到這邊基本上是我與這個問題相遇的過程。
實際上,當我看完題解後的第一個想法是,
— 基於上面的優化方式,是否存在一個方法能夠直接計算出解呢?
我相信這也是搜尋演算法的最理想方法吧
求直線不比什麼方法都快多了?
但這種彷彿宇宙奧秘的答案我自然不會知道。
但我知道用不論是BFS還是雙向BFS,它們總歸是暴力搜尋法。
啟發式演算法。
以在該特定問題的Domain knowledge來搜尋,透過定義啟發式與特定知識來評估路徑的成本。
透過某種機制限制了一個狀態的操作集合的分支,降低了分支也就意味著提升了效率。
在上面那篇文章中也提到了一個好的啟發式設計在最極端、理想的情況下。
就是只包括從初始狀態到目標狀態最優路徑上的節點。
(原來大家都在想同一件事阿)
接下來我想起了以前做的DQN貪吃蛇小專題。
Deep-Q-Learing(DQN),它是建立在Q-learing之上的強化學習方法。
Q-learing 是一種做出最佳決策的強化學習演算法。
透過維護一個 Q - table,儲存各種狀態(State)下做某個行為(Action)所得到的獎勵(Reward)。
這個 Q - table 是為了判斷當下的狀態應該要做什麼行為。
而方法是藉由不斷的嘗試,將各種可能的狀態與獎勵記下來。
以達到下次遇到同樣狀態時能夠直接地做出最佳解的行為。
如果要比喻的話,就像是把電腦丟進去狀態空間,讓它不停的走來走去。
直到把這個空間的訊息都記熟。
但是,某些情況下的狀態空間並非有限的抑或是有限卻龐大的。
維護 Q-table 似乎是困難抑或是不合理的。
因此衍生出了以類神經網路模型來代替 Q-table 作用的深度學習方法 — Deep-Q-Learing。
在遊戲AI的領域有著不錯的效果。
這種方法與搜尋法的終極目標似乎有些共通點。
一個能正常運作的 Q-table 能夠提供某個狀態的最佳解。
那是否意味著能夠直接找到一條從初始狀態直達目標狀態的路徑?
但還要考慮的是模型推論的運算量、以及模型並不是完全準確的前提。
是否會比其他演算法來的好,沒做實驗也無從得知。
另外一個是從論文中找到的深度學習方法。
透過變分自動編碼器(Variational autoencoder,VAE)。
訓練用於建構PDDL模型的潛在空間(latent space),並由現成的規劃器求解。
PDDL 似乎是規劃問題中用於描述問題的一種方法。
而規劃器則是以狀態來分析狀態空間並建構成Planning Graph。
以搜尋計畫空間的方式節省了搜尋的時間與規模。
而使用規劃器似乎是應用於實際規劃問題中最常見的方法(穩定、可靠)。
除此之外還有許多搜尋演算法。
Monte Carlo Tree Search(MCST)、Simulated Annealing(SA)、Constraint-based Search(CBS)
等等...
要不是我沒看懂就是沒仔細看怎麼應用在這問題上,因此沒特別提到。
最後是我在明年之前想試試看的一個想法。
即使我認為尋找一個直接解在目前是困難的。
但基於理論,我覺得這個方法可行。
多點搜尋(multi-point search) ,基於雙向搜尋,將同時搜尋的狀態增加以達到更好的效率。
目的就是想是想建立最上面那個直線解。
這聽起來是一個很明顯的搜尋優化方法,同時也有著明顯的待解決問題。
1. 最明擺著的就是中間狀態的選擇,若是無法正確的決定中間狀態,那只會導致搜尋往不正確的方向進行,最差的情況與暴力搜尋沒什麼差別了。
2. 多點搜尋需要維護更多的儲存狀態的資料結構(需要儲存狀態與搜尋過程),會有更多的時間在操作與驗證這些資訊。
而解決方法我想要透過深度學習的方法,學習一個映射函式將狀態空間映射到某個維度的歐幾里得空間,並以歐幾里得距離作為判斷中間狀態依據。具體執行步驟如下。
1. 定義一種模型,將狀態空間中的狀態映射到歐幾里得空間中的點。
2. 選擇一個或多個介於起始狀態和目標狀態的中間狀態。
3. 計算起始狀態、目標狀態和中間狀態的歐幾里得距離。
4. 透過維護多個狀態空間樹來實現多點搜尋演算法,直到所有狀態重複。
映射的想法就像是,假設我在三維歐幾里得空間中有兩點。
那麼我們可以將其映射在一個二維平面上面,而紅線則是他們在平面上的距離。
在這裡,我們可以很簡單的透過歐幾里得距離來定義中間狀態。
更簡單的就是直接透過座標來指定直線上每個點為中間狀態,這樣似乎就能得到直線解了?
想得很美。
但由於映射的關係,我們不能保證相鄰兩點間是可以透過操作集合轉換的狀態。
不過我們依舊能以暴力搜尋的方法來尋找該點,就像是下面這張圖一樣。
不過在實作上也似乎有一些問題。
狀態空間屬於抽象的概念,描述一個問題所有可能的狀態。
而歐幾里得空間則是一種數學概念,他用於描述距離的結構。
因此在理論上是可以將狀態空間映射到歐幾里得空間的。
但實際上是否能有效映射是這個演算法的重點。
而如何去設計這個映射函式也是該注意的一個點。
就像下圖,若是映射到的空間使得初始狀態與目標狀態非常接近。
那實際上與暴力搜尋法的時間複雜度毫無差別了。
這差不多是我現在所有的想法了。
寫出來不知道有沒有人能和我討論看看。
下學期開始要準備考研究所
還有畢業專題要忙
(我預計是想要做這個題目 但又怕做不出來很尷尬)
不過指導教授是把畢業專題同意書先簽名
告訴我讓我自己決定題目然後交去系辦就好了
除了這個方法的可行性、還有應用場景之類的
有時候不知道是我想的太過不切實際還是我真的能行
歐乾 又要早上了
來個光源