搜索¶

动作(Action): func Action(State): Return 可执行的动作(Action)列表
转移模型(Transition Model): func Result(State, Action): Return 在执行动作(Action)之后的新状态(State)
状态空间(State Space): 通过Action可达的State的集合
路径代价(Path Cost): func PathCost(CurrentCost, State1, Action, State2): Return 新的路径代价(Path Cost)
节点(Node): 包含State、Parent Node、Action、Path Cost(From initial state)的数据结构

搜索算法¶

无信息搜索算法(Uninformed Search)：在搜索过程中不利用任何关于问题的额外信息，仅依赖于问题的定义和结构来进行搜索的算法。这类算法通常会遍历整个状态空间，直到找到解决方案为止。常见的无信息搜索算法包括深度优先搜索(DFS)和广度优先搜索(BFS)。

深度优先搜索(Depth-First Search, DFS)¶

我们可以首先定义一个初始节点，探索包含该节点的Frontier（前沿），初始化一个Frontier栈，对于初始节点，Frontier就是该节点；同时，定义一个Explored（已探索）集合，初始为空。然后，我们重复以下步骤:

此时Frontier为空：无解
此时Frontier不为空：从Frontier中出栈一个节点
如果该节点是目标状态：成功，返回解决方案
否则，扩展该节点，生成其子节点，并将不在Explored集合和Frontier中的子节点入栈到Frontier中
将该节点添加到Explored集合中

实际上，DFS是首先深入搜索到一个分支的尽头，然后回溯到最近的分叉点，继续探索其他分支，直到找到目标状态或所有可能的路径都被探索完毕。

广度优先搜索(Breadth-First Search, BFS)¶

我们可以首先定义一个初始节点，探索包含该节点的Frontier（前沿），初始化一个Frontier队列，对于初始节点，Frontier就是该节点；同时，定义一个Explored（已探索）集合，初始为空。然后，我们重复以下步骤:

此时Frontier为空：无解
此时Frontier不为空：从Frontier中出队一个节点
如果该节点是目标状态：成功，返回解决方案
否则，扩展该节点，生成其子节点，并将不在Explored集合和Frontier中的子节点入队到Frontier中
将该节点添加到Explored集合中

实际上，BFS是逐层搜索（搜索的都是和初始节点距离相同的节点），从初始节点开始，首先探索所有直接相连的节点，然后是这些节点的子节点，依此类推，直到找到目标状态或所有可能的路径都被探索完毕。

启发式搜索算法(Informed Search)：在搜索过程中利用关于问题的额外信息（启发式信息）来指导搜索过程，从而更有效地找到解决方案的算法。启发式搜索算法通常会评估每个节点的潜在价值，并优先探索那些看起来更有希望的节点。常见的启发式搜索算法包括A*搜索和贪心最佳优先搜索。

贪心最佳优先搜索(Greedy Best-First Search, GBFS)¶

贪心最佳优先搜索是DFS的一种改进。

曼哈顿距离(Manhattan Distance)：在一个网格中，两个点之间的距离是它们在水平和垂直方向上距离的总和。计算公式为：h(n) = |x1 - x2| + |y1 - y2|，其中(x1, y1)和(x2, y2)分别是两个点的坐标。

当遇到分叉时，选择启发式函数值h(n)最小的节点进行扩展，即把h(n)最小的节点后加入Frontier（先出栈）。

A* 搜索 (A* Search)¶

A*搜索结合了DFS和GBFS的优点。

评估函数(Evaluation Function)：f(n) = g(n) + h(n)，其中g(n)是从初始节点到当前节点n的实际代价，h(n)是从当前节点n到目标节点的启发式估计代价（曼哈顿距离）。

A*搜索当且仅当以下条件满足时，能够保证找到最优解：

启发式函数h(n)是可采纳的（Admissible）。可采纳的启发式函数意味着它从不高估从当前节点到目标节点的实际代价。例如在使用曼哈顿距离作为启发式函数时，它总是小于或等于实际的路径代价，因为它只考虑水平和垂直移动，而忽略了可能的障碍物或其他路径限制。但如果h(n)取的是曼哈顿距离*10倍，那么它可能会高估实际代价，从而不再是可采纳的启发式函数。
启发式函数h(n)是一致的（Consistent）。一致的启发式函数意味着对于每个节点n及其每个后继节点n'，满足h(n) ≤ c(n, n') + h(n')，其中c(n, n')是从节点n到节点n'的实际代价。

对抗性搜索(Adversarial Search)：用于解决涉及两个或多个对手的决策问题的搜索算法。每个参与者都试图最大化自己的利益，同时最小化对手的利益。常见的对抗性搜索算法包括极大极小算法(Minimax)和α-β剪枝(Alpha-Beta Pruning)。

极大极小算法(Minimax)¶

极大极小算法是一种递归算法，用于在对抗性游戏中确定最佳移动。它假设两个玩家：一个是“极大化者”（Maximizer），试图最大化自己的得分，另一个是“极小化者”（Minimizer），试图最小化对手的得分。

Player(state)：返回在当前状态下行动的玩家（Maximizer或Minimizer）。
Terminal-Test(state)：检查当前状态是否为终止状态（游戏结束）。

例如井字棋游戏：定义一个评估函数Utility(state)，返回终止状态下的得分（Maximizer赢得+1，Minimizer赢得-1，平局为0）。

对于每一个非终止状态，评估Player(state)：

如果当前玩家是Maximizer：递归地选择所有可能的行动中使得值最大的行动Max-Value(Result(state, action))。
如果当前玩家是Minimizer：递归地选择所有可能的行动中使得值最小的行动Min-Value(Result(state, action))。

Max-Value设计： 1. 检查游戏是否结束（Terminal-Test(state)），如果是，返回Utility(state)。 2. 初始化v = -∞。 3. 对于在Action(state)中每个可能的行动action（for循环），计算v = max(v, Min-Value(Result(state, action)))。 4. 返回v。

Min-Value同理。

α-β剪枝(Alpha-Beta Pruning)¶

α-β剪枝是一种优化极大极小算法的技术，通过在搜索过程中剪枝掉不必要的分支，从而减少需要评估的节点数量，提高搜索效率。α是当前已知的对Maximizer最好的选择的下界，β是当前已知的对Minimizer最好的选择的上界。

如果在搜索过程中发现某个节点的值已经超出了α或β的范围，那么可以停止对该节点的进一步评估（剪枝），因为它不会影响最终的决策。

受限深度(Minimax)搜索(Limited Depth Search)¶

评估函数(Evaluation Function)：Eval(state)，用于在受限深度下评估非终止状态的得分。