课程

非启发式搜索

为了实现贪心，需要有某个启发函数 $h(n)$。每次做出选择的时候，优先从可以选择的节点中，选择启发函数最小的点。

在二维迷宫中，这个启发函数可以是曼哈顿距离。

然而，这种做法保证了局部最优，但是无法保证找到全局最优解。因为没有考虑到达局部最优的节点需要的成本，导致绕弯路。

这时候考虑拥有最低 $g(n)+h(n)$ 的节点。其中，$g(n)$ 是到达这个节点需要的成本。

启发函数需要满足条件：

满足这些条件，A*搜索就可以找到最优解。

这里拥有对抗性，例如画圈画叉的游戏。

首先，对于不同的最终情况赋值，赋值为 1、0 和-1 。Max 玩家想要最大化得分，Min 玩家想要最小化得分。

建立了基本的模型之后，Min 玩家会做出当下所有可能的决策，然后就是 Max 玩家最大化。这样递归考虑。最后 Min 玩家选择当下可以让得分最低的选择。

其中，有些地方可以剪枝。例如，当前是 Max 玩家，第一层是 Min 玩家。第一层中已经有 4 。当第二层中出现 3 的时候，说明对应第一层的值小于等于 3，然而最后 Max 只会选择 4，所以可以剪枝。

到达某一个深度后，就停止。不过这需要一个函数，来预测每一个状态对应的好坏。

这个问题就是从演员出发，最少经过多少个电影的联系，才能抵达另一个演员。这是典型的最短路问题，可以使用 BFS 解决。代码的其他部分都写好了，只用完成核心逻辑。

使用 Utils 当中的 Node 类，在每个节点储存父节点和采取了哪个行动到达这个点。这样到达目标之后，根据父节点遍历，就可以找到到达该节点，需要的所有行动，以及路径。

圈叉游戏。通过 Minimax 方法来实现。代码拥有大体框架，实现起来不难。最后的 minimax 实现需要两个辅助函数——max_value 和 min_value。核心思想就是递归。课堂的 Notes 中也有伪代码可以参考。