对于像围棋这样**分支因子**极大的应用，传统的Minimax及其变种算法因计算量过大而不再适用。**蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）** 为此类问题提供了强大的解决方案。 MCTS基于两个核心理念： 1. **通过模拟进行评估 (Evaluation by Rollouts)**：从一个状态 $s$...

策略迭代是一种用于在马尔可夫决策过程中寻找最优策略 $\pi^*$ 的算法。与值迭代相比，策略迭代通常能够更快地收敛，因为它**直接优化策略**，而策略的收敛速度往往比值的收敛速度快得多。 该算法的核心思想是：从一个任意的初始策略开始，通过一个迭代循环不断优化它，直到策略不再发生变化为止。每一次迭代都包含两个核心步骤：**策略评估**和**策略改进**。 | 特性 | 价值迭代...

价值迭代 (Value Iteration) 是一种经典的动态规划算法，用于在已知的马尔可夫决策过程中，计算所有状态的最优价值函数 $V^*(s)$。其核心思想是通过迭代的方式，不断更新每个状态的价值，直到价值收敛为止。 算法通过引入“时间限制”的概念，从一个有限的未来开始，**逐步扩展到无限的未来**，最终得到最优价值。 我们定义 $V_k(s)$ 为在状态 $s$ 出发，且**还剩下...

在约束满足问题中，**过滤（Filtering）** 是通过约束传播来缩小变量域的技术。过滤的核心思想是**在搜索过程中主动推理，提前发现和消除不可能的赋值**，从而显著减少搜索空间。 过滤不同于盲目的回溯搜索，它利用约束的结构信息进行**局部推理**，在赋值之前就排除明显不可行的选择，避免了大量无意义的搜索尝试。...

在约束满足问题的回溯搜索中，排序启发式（Ordering Heuristics）决定了**搜索过程中变量选择和值选择的顺序**。好的排序策略可以**显著减少搜索空间的探索**，将指数级的搜索问题转化为多项式时间可解的问题。...

> 下面是对CSP的相关概念的接口预实现，之后会用到 ```python class CSP: """Constraint Satisfaction Problem class""" def __init__(self, variables: List[str], domains: Dict[str, Set[Any]], constraints: List[Constraint]):...

约束满足问题（Constraint Satisfaction Problem, CSP）是一类特殊的搜索问题，它提供了一种**结构化的方式来表示和解决组合问题**。与传统搜索问题不同，CSP关注的是**找到变量赋值的组合，使之满足所有约束条件**，而不是寻找从起始状态到目标状态的路径。...

在无信息搜索中，我们会从起始点开始、展开当前边界的所有可能后继状态。但是这样的搜索效率很低，会导致进行很多没必要的搜索。如果我们了解了当前环境的信息、对当前的空间的搜索方向有一定概念，就可以显著提高性能、快速到达目标。 启发式函数是实现到目标状态距离的核心驱动力——它们是**接收一个状态作为输入并输出相应估计值的函数**。 -...

在某些问题中，我们**只关心找到目标状态而并不需要知道达到这个状态的优化路径**，并不需要通过设计算法来让路径成本优化。局部搜索算法允许我们找到目标状态而无需优化到达那里的路径成本。 在局部搜索问题中，状态空间由“完整”解的集合组成。我们使用这些算法来尝试找到满足某些约束或优化某个目标函数的配置。...

如果在一个给定的世界中有$n$个变量对象，它们可以分别取$x_1, x_2, \ldots, x_n$个不同的值，那么状态的总数就是$x_1 \cdot x_2 \cdot \ldots \cdot x_n$。 状态空间图的构建方式是：状态代表节点，从一个状态到其子状态存在有向边。这些边代表动作，任何相关的权重代表执行相应动作的成本。注意，**在状态空间图中，每个状态只被表示一次**。 >...