搜索¶

一、定义（有点像图灵机）¶

状态空间
行为（动作）
路径/代价
状态转移
后继函数
起始和目标函数

二、评价标准¶

完备性：存在解时，能保证找到解（即使不是最优）
最优性：找到的第一个解是最优解

三、一致代价搜索（UCS）¶

1. 优势¶

完备：
最优

2. 劣势¶

...
$\Downarrow$

四、启发式搜索¶

1. 启发函数 $\ h(x)$ ¶

功能:估计某一个状态到目标状态的距离
设计:对原有条件进行松弛（即解决松弛后的问题）

2. 贪心搜索¶

扩展看起来最近的节点，即评价函数 $f(n) = h(n)$

3. A*搜索¶

启发函数: $f(n) = g(n) + h(n)$ ，其中
$g(n)$ ：从起始状态到n的实际代价(由UCS得到)
$h(n)$ ：从n到目标状态的估计代价（由启发函数得到）
$\Rightarrow h(n)\equiv 0$ 时，即为一致代价搜索
可采纳性
$0\leq h(n)\leq h^*(n)$ 估计的距离总是比实际短

4. 图搜索¶

避免重复操作/访问的出现

思路：设置额外的存储空间，记录已经访问过的节点
条件：h的一致性 $h(A)-h(C)\leq cost(A\ to\ C)$ （比可采纳性强）
```
graph LR
A((A)) --> C((C))
```

五、对抗搜索¶

1. 博弈¶

1.1 定义¶

在结束之前的动作往往没有代价，即效用只在搜索结束时才得到

1.2 价值¶

从某个状态开始的最大效益， $V(s) = \max\limits_{s'\in children(s)} V(s')$

2. Minimax Value¶

2.1 适用范围¶

两个玩家的搜索树，交替进行动作
其中红色的节点由对手控制，希望使自己的收益最小，成为最小值节点，以▽表示， $V(s) = \min\limits_{s'\in children(s)} V(s')$ 。

2.2 伪代码¶

# min-value同理
def max-value(state):
    init v = -∞
    for each successor in state:
        v = max(v, min-value(successor))  
        #子节点是min-value，对手会尽可能让自己收益最小
# 将两者结合
def value(state):
    if state is terminal:
      # 返回价值
        return utility(state)
    if state is max:
    #如果是极大值节点
        return max-value(state)
    else:
        return min-value(state)

2.3 效率¶

由于需要搜索到所有叶节点才能得到结果，所以时间复杂度为 $O(b^m)$ ，其中b为分支因子，m为深度（exhausted DFS）
空间复杂度为 $O(bm)$

2.4 有限深度搜索¶

思路：在搜索树的某一深度停止搜索，返回当前状态的估计值（牺牲了最优性）

3. Alpha-Beta 剪枝¶

3.1 定义¶

$\alpha$ :当前最大节点所能得到的最大值
$\beta$ :当前最小节点所能得到的最小值

3.2 代码¶

def max-value(state, α, β): 
  initialize v = -∞
  for each successor of state:
    v = max(v, value(successor, α, β))
    if v ≥ β return v
    α = max(α, v)
  return v

3.3 分析¶

对于一个极小值节点n，若已有一个 $\alpha$ ，如果在对n的子节点遍历的过程中，出现了一个比 $\alpha$ 更小的值，那么这个节点的父节点就不会选择这个节点，因为这个节点的父节点已经有一个更好的选择了。此时即可不继续遍历（剪枝）

3.4 性质¶

不影响最优性
时间复杂度为 $O(b^{m/2})$

4.期望最大搜索（待记）¶

4.1 期望节点的价值¶

def exp-value(state):
  initialize v = 0
  for each successor of state:
  p = probability(successor)
  v += p * value(successor)
  return v

4.2 性质¶

不适用于 $\alpha-\beta$ 剪枝
截断搜索仍然适用

六、效用Ultility¶

对于Minmax搜索，只关注大小关系，值本身不重要，而对于期望最大搜索，效用的值很重要

1. 理性偏好（待记）¶

满足一下公理： $\begin{aligned} & \text{有序性}\\ & (A\succ B)\lor(B\succ A)\lor(A\sim B)\\ & \text{传递性}\\ & (A\succ B)\land(B\succ C)\Rightarrow(A\succ C)\\ & \text{连续性}\\ & A\succ B\succ C\Rightarrow\exists p\left[p;A;1-p;C\right]\sim B\\ &\text{可替代性} & \\ & A\sim B\Rightarrow[p,A;1-p,C]\sim[p,B;1-p,C]\\ & \text{单调性}\\ & A\succ B\Rightarrow\\ & (p\geq q\Leftrightarrow[p,A;1-p,B]\succeq[q,A;1-q,B])\end{aligned}$

2. 人类的效用：风险厌恶¶

七、马尔科夫决策过程（MDP）¶

策略仅与当前状态有关，与历史无关
每一步都有效用

1. 序列效用¶

MDP的搜索树可能会无限大，为了防止无限搜索，引入了折扣因子 $\gamma$ ，即未来的效用会被折扣

MDP搜索树

搜索¶