複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/策略搜索/22717770
複製
複製成功

策略搜索

鎖定
策略搜索指的是深度學習中利用廣度優先搜索、深度優先搜索等策略來進行數據搜索的過程。
中文名
策略搜索
應用領域
深度學習

目錄

  1. 1 樹的搜索策略
  2. ▪ 廣度優先搜索（BFS）
  3. ▪ 深度優先搜索（DFS）
  4. 2 最佳優先搜索
  5. 3 策略搜索算法

策略搜索樹的搜索策略

策略搜索廣度優先搜索（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] 

策略搜索最佳優先搜索

結合了深度優先搜索和廣度搜索的優點，使用堆：
  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。 [2] 
參考資料
  • 1.    王學寧,陳偉,張錳,徐昕,賀漢根.增強學習中的直接策略搜索方法綜述[J].智能系統學報,2007(01):16-24.
  • 2.    程玉虎,馮渙婷,王雪松.基於參數探索的期望最大化策略搜索[J].自動化學報,2012,38(01):38-45.