策略搜尋

策略搜尋指的是深度學習中利用廣度優先搜尋、深度優先搜尋等策略來進行數據搜尋的過程。

基本介紹

• 中文名：策略搜尋
• 套用領域：深度學習

樹的搜尋策略

廣度優先搜尋（BFS）

使用佇列(Queue)

1. 構造僅含樹根節點的佇列Q;
   
2. 若佇列Q的第一個節點x是目標節點，則輸出節點x對應的解，算法結束
   
3. 刪除佇列Q的第一個節點x，如果綁定刪除B(x)判定以x為根的子樹可能存在解，則將x的所有孩子節點加入佇列Q的末尾；
   
4. 如果佇列Q為空，則問題無解，算法結束，否則，轉到第2步；
   

深度優先搜尋（DFS）

使用棧(Stack)

1. 構造僅含樹根節點的棧S;
   
2. 如果棧頂元素x是目標節點，則輸出節點x對應的解，算法結束；
   
3. 彈出棧頂元素x，如果綁定函式B(x)判定以x為根的子樹可能存在解，則將x的所有孩子一次壓入棧
   
4. 如果棧S為空，則問題無解，算法結束，否則，轉到第2步；
   

最佳優先搜尋

結合了深度優先搜尋和廣度搜尋的優點，使用堆：

1. 構造僅含樹根節點的堆Q;
   
2. 如果堆頂元素x是目標節點，則輸出節點x對應的解，算法結束；
   
3. 抽取堆頂元素x，如果綁定函式B(x)判定x以x為根的子樹可能存在解，則將x的所有孩子節點插入堆
   
4. 如果堆Q為空，則問題無解，算法結束，否則，轉到第2步；
   

策略搜尋算法

為了得到狀態轉化的方程，構建了函式St+1 = ASt + Bat + wt，我們重點講解了如何得到擬合係數的過程，但為了解決POMDPs問題，由於其是一個NP-hard問題，我們不能通過計算獲得擬合的係數，此時我們通過策略搜尋算法獲得求解。

在策略搜尋算法中，我們提出兩個新的定義：

（1）我們定義一個策略集Π作為所有可能集合的合集，我們通過對集合Π進行搜尋，找到其中可以獲得最優結果的策略π（這一思想類似於我們在監督學習中定義將涉及H的過程，我們在H中搜尋最優的假設函式h使監督學習產生的誤差最小）

（2）一個隨機策略是一個由狀態和策略到一個實數的影響，即π：S*A->R，其中π(s, a)表示在狀態s下執行動作a的機率，故Σπ(s, a)=1, π(s,a)≥0。