[科普中国]-策略搜索

策略搜索指的是深度学习中利用广度优先搜索、深度优先搜索等策略来进行数据搜索的过程。

树的搜索策略广度优先搜索（BFS）使用队列(Queue)

构造仅含树根节点的队列Q;

若队列Q的第一个节点x是目标节点，则输出节点x对应的解，算法结束

删除队列Q的第一个节点x，如果绑定删除B(x)判定以x为根的子树可能存在解，则将x的所有孩子节点加入队列Q的末尾；

如果队列Q为空，则问题无解，算法结束，否则，转到第2步；

深度优先搜索（DFS）使用栈(Stack)

构造仅含树根节点的栈S;

如果栈顶元素x是目标节点，则输出节点x对应的解，算法结束；

弹出栈顶元素x，如果绑定函数B(x)判定以x为根的子树可能存在解，则将x的所有孩子一次压入栈

如果栈S为空，则问题无解，算法结束，否则，转到第2步；1

最佳优先搜索结合了深度优先搜索和广度搜索的优点，使用堆：

构造仅含树根节点的堆Q;

如果堆顶元素x是目标节点，则输出节点x对应的解，算法结束；

抽取堆顶元素x，如果绑定函数B(x)判定x以x为根的子树可能存在解，则将x的所有孩子节点插入堆

如果堆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

本词条内容贡献者为:

李晓林 - 教授 - 西南大学