Problem Solving¶

Basic Search Method¶

良定义 | A well-defined problem¶

假设环境是可观察的（万能传感器）、离散的、已知的（行动造成确定结果）、确定的（行动结果一一对应）

要素

状态空间：初始状态到可以达到的所有状态的集合
- 状态：state \(s\), a node in search tree
- 初始状态：initial state \(s_0\)
- 行动：action \(a\)
- 转移模型(后继状态)：function(\(s\),\(a\))
目标测试：确定当前状态\(s\)是否是目标状态
路径耗散：考虑单步耗散

性能指标

完备性
最优性
时间复杂度
空间复杂度

无信息（盲目式）搜索¶

区别：如何拓展子节点。

搜索算法	算法描述	完备性	最优性	time cost	space cost
宽度优先搜索	先拓展根节点，再拓展后继节点，总是拓展深度最浅的未拓展节点。用队实现。	Y	Y	\(O(b^d)\)	\(O(b^d)\)
一致代价搜索	拓展的是路径损耗\(g(n)\)最小的节点\(n\).最优性成立，如果每一步代价大于某个小正数\(\varepsilon\).	Y	Y	\(O(b^{1+C/\varepsilon})\)	\(O(b^{1+C/\varepsilon})\)
深度优先搜索	总是拓展树的当前边缘节点集中最深的节点。是完备的，但不是最优的，因为遇到解就会返回。	N	N	\(O(bd)\)	\(O(bd)\)
深度受限搜索	设置一个深度界限\(l\), 若 \(l<d\), 不完备；若 \(l>d\), 则不最优	N/Y	N	\(O(b^l)\)	\(O(bl)\)
迭代加深的深度优先搜索	不断地增大深度限制，达到最浅的目标节点所在深度\(d\)时，就能找到目标节点。	Y	N/Y	\(O(b^d)\)	\(O(bd)\)

有信息（启发式）搜索¶

节点是基于评价函数\(f(n)\)被选择拓展的。

搜索算法	算法描述	time cost
贪婪最佳优先搜索	拓展离目标最近的节点，只是用启发式信息，\(f(n)=h(n)\)，但不完备	最坏情况\(O(b^d)\)
A*搜索	对节点的评估包含了到此节点已有的代价，即\(f(n)=g(n)+h(n)\)，\(h(n)\)满足可采纳性和一致性，就能保证问题求解的完备和最优性
递归最佳优先搜索（RBFS）	使用f_limit来跟踪从当前节点的祖先得到的最佳\(f\)，如果某节点超过此值，就递归回溯，对当前路径上的每个节点，用该节点子节点的最佳\(f\)更新其\(f\)值

A*搜索的完备和最优性条件

A*搜索的可采纳性

专注于对树搜索进行A*搜索，要求\(h(n)\)不会过高估计到达目标的代价，从而\(f(n)\)不会超过经过节点\(n\)的解的实际代价。在搜索中，直线距离是可采纳的启发式。

A*搜索的一致性(单调性)

专注于对图搜索进行A*搜索, 要求满足三角不等式。如果对于每个节点\(n\), 通过人以行动\(a\)产生的\(n\)的每个后继节点\(n'\), 从节点\(n\)到达目标的估计代价不大于从\(n\)到\(n'\)的单步代价与从\(n'\)到达目标的估计代价之和

\[ h(n)\leq c(n,a,n')+h(n') \]

可以理解成\(h(n)\)是在图搜索中从\(n\)到目标的路径损耗的下界。估计的下界越靠近下确界，搜索越快。

有上式可以推得\(f(n)\)是非递减的：

\[ f(n')=g(n')+h(n')=g(n)+c(n.a.n')+h(n')\geq g(n)+h(n)=f(n) \]

对抗搜索（博弈）¶

极大极小搜索

使用了简单的递归算法。用栈实现，故是深度优先搜索。故time cost \(O(b^d)\), space cost \(O(bd)\). 时间开销太大。

Minimax Search

action MiniMax_Decision(state)
    return arg_max(Min_Value(Result(state,a)));

value Max_Value(state)
    if(terminal_test(state))return utility(state);//leaf node
    double v=-INFTY; 
    for(auto& a:actions(state))
        v=max(v,Min_Value(result(state,a)));
    return v;

value Min_Value(state)
    if(terminal_test(state))return utility(state);//leaf node
    double v=INFTY; 
    for(auto& a:actions(state))
        v=min(v,Max_Value(result(state,a)));
    return v;

\(\alpha-\beta\) 剪枝

\(\alpha\) 为目前为止路径上发现的MAX的最佳选择（极大值），\(\beta\) 为目前为止路径上发现的MIN的最佳选择（最小值），并不断更新。当某个节点的值比目前的MAX的\(\alpha\)/MIN的\(\beta\)要查时便做裁剪。

Alpha-Beta Search

action Alpha_Beta_Search(state)
    double v = max(state, -INFTY, +INFTY);
    return actions.get(v)

value Max_Value(state, alpha, beta)
    if(terminal_test(state))return utility(state);//leaf node
    double v=-INFTY; 
    for(auto& a:actions(state))
        v=max(v,Min_Value(result(state,a), alpha, beta));
        if(v>=beta) return v;
        alpha = max(alpha, v)
    return v;

value Min_Value(state)
    if(terminal_test(state))return utility(state);//leaf node
    double v=INFTY; 
    for(auto& a:actions(state))
        v=min(v,Min_Value(result(state,a), alpha, beta));
        if(v<=alpha) return v;
        beta = min(alpha, v)
    return v;