跳转至

搜索求解

搜索求解

0.搜索算法基础

最短路径搜索的相关术语

  • 状态：当前情况的信息
  • 动作：状态间转移所采取的行为
  • 状态转移：选择一个动作之后所处状态改变的过程
  • 路径和代价：不断转移得到的状态序列称为路径；每条路径对应一个代价
  • 目标测试：判断状态是否是目标状态。目标测试通过代表搜索算法的完成。搜索算法完成不代表已经找到了最短路径

搜索算法的评价指标

  • 完备性：算法是否保证能找到一个解（不一定最优）
  • 最优性：算法是否能保证找到的第一个解是最优解

搜索算法的框架

  • 边缘集合（开表）：可用于下一步探索的所有候选结点
  • 扩展：从边缘集合中移出元素，接着将该结点的后继结点放入边缘集合
    • 广度优先搜索：每次扩展从边缘结合中取出最浅的结点
    • 深度优先搜索：每次扩展从边缘集合中取出搜索树最下层（最深）的结点
  • 剪枝：放弃部分扩展结点

图搜索算法和树搜索算法

图搜索算法和树搜索算法的区别在于：图搜索算法维护了一个集合C用于存储所已经被扩展过结点的状态，C被称为闭表。

1.启发式搜索

定义
在问题定义提供的信息之外还有一些能辅助算法做出决策的额外信息。利用这些辅助信息的搜索算法被称为有信息搜索或启发式搜索。

分类
DFS和BFS不利用额外信息，为无信息搜索；贪婪最佳优先搜索和A*搜索是具有代表性的启发式搜索算法。

启发函数
启发信息通常形式化为一个关于结点的函数h(n)，其用于估计结点n距离达到目标还需付出多少代价，这个函数称为启发函数。例如在最短路径问题中启发函数可以定义为任两个城市间的直线距离。

评价函数
对于边缘集合中的任意结点n，函数发f(n)决定了搜索算法扩展结点的优先度，f(n)称为评价函数。规定：边缘集合中某个结点的评价函数值越小，其被挑选的优先级越高。特别地，DFS的f(n)可定义为该结点深度的倒数，BFS的f(n)可定义为该结点的深度。

启发搜索举例

  • 贪婪最佳优先搜索

    使评价函数h(n)取值等于启发函数f(n)的算法称为贪婪最佳优先搜索算法

  • A*搜索

    定义评价函数等于起始结点到结点n的路径代价g(n) + h(n)（引入了任意城市到目标城市的辅助信息）

2.对抗搜索

定义
对抗搜索是一种特殊情况下的多智能体搜索问题：信息确定、全局可观察、竞争对手轮流行动、输赢收益零和前提下的两人博弈问题。求解这种问题的算法称为对抗搜索算法。

相关术语

  • 状态：状态s包括当前游戏局面和当前行动的智能体，初始状态为游戏开始时的状态。player(s) 表示状态s下行动的智能体
  • 动作：动作是指player(s)在当前局面下可以采取的操作a，记动作集合为actions(s)
  • 状态转移：状态转移函数result(s,a)表示在状态s下采取动作a后的下一个状态
  • 终局状态测试：终局状态测试函数terminal_test(s) 用于测试游戏是否在状态s下结束
  • 终局得分：终局得分函数utility(s,p)表示在状态s下玩家p的得分

对抗搜索举例

  • 最大最小搜索

    • 交替探索两名玩家的决策，并假定两名玩家在决策时总追求最大化自己的得分（在零和博弈中这等价于最小化对手的得分）。
    • 将以最大化得分为目标的玩家称为MAX，将以最小化得分为目标的玩家称为MIN，二者交替行动，每次行动对应一个选择下一层结点的动作a。
    • 算法通过递归来实现，例如本层的玩家为MAX，那么他需要求最小值中的最大值来选择结点，因为在下一层中MIN会选择最小值的结点。模拟到终局的最终得分在经过比较后回溯地赋给上一层相应的结点。
    • minimax函数的输入是状态（结点），输出是此节点在两名玩家均按照最优策略行动下的终局得分，每个结点的得分是通过下一个结点的选择来赋予的。在计算完每个结点的分数后每一步由玩家自己的角色来选择使得分最大或最小的行动。

    image-20240306184424066

    • 最大最小算法对游戏搜索树执行了一个完整的深度优先搜索。

  • Alpha-Beta剪枝算法

    • 由于最大最小搜索本质上是深度优先搜索，则当搜索树极大时无法在规定时间内返回结果。使用Alpha-Beta剪枝算法可以减少搜索空间。
    • 结点的先后顺序会影响剪枝效率。
    • Alpha初始化为负无穷大，Beta初始化为正无穷大。

    • 在保证与原最大最小算法搜索结果相同的前提下减去了不影响最终结果的搜索分支。

      image-20240306184616075

3.蒙特卡洛树搜索

定义
智能体对环境没有完整的认识，事先不知道每种行动的优劣及后果，只有尝试后才能确定

多臂赌博机问题
有K个赌博机，每次转动一个赌博机的臂膀，赌博机会随机地吐出x个硬币（得分）。假设给智能体t次转动赌博机的机会，该如何选择赌博机来获得尽量多的得分？

基于多臂赌博机问题的相关术语

  • 奖励：每个赌博机都有获得收益的分布与均值。某次行动选择转动了某个赌博机的臂膀，那么其在本次行动中获得的收益对应着此赌博机的收益分布，此次得分即称为奖励
  • 悔值函数：根据智能体前n次操作定义的函数

解决思路
与对抗搜索不同，智能体不能预先计算好最优策略，然后实行，而是需要一边探索一边调整自己的策略，争取获得更好的收益。

贪心算法思路
若使用贪心算法，计算出过去摇动每个赌博机收益的均值，再选择均值最大的赌博机进行摇动，则会体现“探索”和“利用”之间的对立关系。

上限置信算法（UCB1）
既考虑了每个结点的效益，又考虑了每个结点的访问次数。
在探索中，应优先探索估计值不确定度高的动作。另外，如果从已有探索样本中知道一个动作的奖励估计极端值偏小，那么即使该动作的估计值不确定度很大，算法也没有必要将其作为优先探索对象。
上限置信算法（UCB1算法）：为每个动作的奖励期望计算一个估计范围，优先采用估计范围上限较高的动作。

蒙特卡洛树搜索算法
算法事先不知道每个结点将会得到怎样的代价分布，只能通过采样式探索来得到计算奖励的样本，这个算法利用“蒙特卡洛法”通过采样来估计每个动作的优劣。算法的目标是得到一个近似最优解。
通过采样避免了剪枝。

  • 选择：从搜索树的根节点开始，递归地向下选择子节点，直到到达叶结点或还未被扩展过的子结点L。向下递归选择过程可由UCB1算法来实现。在递归选择过程中记录每个结点的被选择次数和奖励均值
  • 扩展：如果结点L不是一个终止结点（或对抗搜索的终局结点），则随机扩展它的一个未被扩展过的后继边缘结点M
  • 模拟：从结点M出发，模拟扩展搜索树，直到找到一个终止结点（游戏结束）。
  • 反向传播：用模拟所得的结果（终止结点的代价或终局游戏的分数）回溯更新模拟路径中M以上（含M）结点的奖励均值和被访问次数。

上限置信区间树搜索（UCT）
对于对抗搜索问题，以最小最大算法为基础的蒙特卡洛树搜索也被称为UCT算法

  • 未被扩展的结点UCB值为正无穷
  • MAX层结点的总得分需要取反，这是为了统一使用UCB1算法求解
    • 每个结点的UCB值=mean+UCB1
    • 其中mean=+/-收益分数之和/访问次数之和

4.总结

image-20240108230748161