探索与利用
• Re-Le
探索与利用 1. 相关概念 在强化学习中，智能体的目标是学习一个最优策略来最大化长期回报。为了达成此目标，智能体必须在两个核心行为之间做出权衡： - 探索 (Exploration): 尝试当前看起来并非最优的动作，目的是为了收集更多关于环境的信息，发现潜在的、更优的行动选择。 - 利用...
Posts in "Introduction to Artificial Intelligence"
基于模型的学习
• Re-Le
基于模型的学习 1. 相关概念 在强化学习中，基于模型的学习（Model-Based Learning）是一种方法，其核心思想是让智能体通过与环境的交互来学习环境的动态模型。这个模型通常包括两个关键部分： - 转移函数 (Transition Function) $T(s, a, s')$：预测在状态 $s$...
无模型学习
• Re-Le
无模型学习 无模型学习（Model-Free Learning）是一类无需了解环境模型（转移函数 $T$ 和奖励函数 $R$）的强化学习算法。代理直接通过与环境的交互经验来学习价值函数或策略。 无模型学习主要分为两大类： - 被动强化学习 (Passive Reinforcement...
强化学习
• Re-Le
强化学习 1. 相关概念 与马尔可夫决策过程（不同，强化学习是一种在线规划（Online Planning）方法。在传统的MDP（离线规划）中，智能体完全了解环境的转移函数和奖励函数，并以此为基础预先计算出最优策略。 在强化学习中，智能体对环境的奖励或状态转移没有任何先验知识。它必须通过探索（Exploration）...
MDP-calculation-exercise
• MDP, Re-Le
$discussion3$ $exercise1$ > In micro-blackjack, you repeatedly draw a card (with replacement) that is equally likely to be a 2, 3, or 4. You can either Draw or...
策略迭代
• MDP, Re-Le
策略迭代 策略迭代是一种用于在马尔可夫决策过程中寻找最优策略 $\pi^$ 的算法。与值迭代相比，策略迭代通常能够更快地收敛，因为它直接优化策略，而策略的收敛速度往往比值的收敛速度快得多。 该算法的核心思想是：从一个任意的初始策略开始，通过一个迭代循环不断优化它，直到策略不再发生变化为止。每一次迭代都包含两个核心步骤...
价值迭代
• MDP, Re-Le
价值迭代 价值迭代 (Value Iteration) 是一种经典的动态规划算法，用于在已知的马尔可夫决策过程中，计算所有状态的最优价值函数 $V^(s)$。其核心思想是通过迭代的方式，不断更新每个状态的价值，直到价值收敛为止。 1. 核心思想 算法通过引入“时间限制”的概念，从一个有限的未来开始，逐步扩展到无限的未...
贝尔曼方程
• MDP, Re-Le
贝尔曼方程 1. 马尔可夫决策过程 与在确定的搜索问题中寻找一个通往目标状态的最优“计划”不同，解决一个马尔可夫决策过程意味着寻找一个最优策略 (Optimal Policy)。 策略 $\pi$ 是一个从状态 $s \in S$ 到动作 $a \in A$ 的映射，即 $\pi: S \to...
马尔可夫决策过程
• MDP, Re-Le
马尔可夫决策过程 1. 相关概念 马尔可夫决策过程（Markov Decision Processes, MDP）为智能体在不确定性环境中进行决策提供了一个数学模型。其核心思想是，智能体的下一个状态只与当前状态和所选动作有关，而与之前的历史无关。 一个MDP由以下几个关键部分定义： -...
蒙特卡洛树搜索
• Adversarial Search, Games
蒙特卡洛树搜索 1. MCTS 核心思想 对于像围棋这样分支因子极大的应用，传统的Minimax及其变种算法因计算量过大而不再适用。蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS） 为此类问题提供了强大的解决方案。 MCTS基于两个核心理念： 1. 通过模拟进行评估 (Evaluation...
Expectimax 算法
• Adversarial Search, Games
Expectimax 算法 1. Expectimax 概念 Minimax算法的核心假设是对手总是做出最优选择，这使其在面对非最优或随机对手时显得过于悲观。例如，在棋牌或骰子游戏中，结果本身具有不确定性，Minimax的“最坏情况”分析不再适用。 Expectimax搜索是Minimax的泛化，专门用于处理这类不确定...
Minimax算法
• Adversarial Search, Games
Minimax 算法 1. Minimax 核心思想 Minimax（极小化极大）是一种在零和博弈中做出决策的经典算法。其核心思想是，在一个回合制、信息完全的对抗游戏中，我方（MAX玩家）总是希望最大化自己的收益，而对手（MIN玩家）则总是希望最小化我方的收益。算法假定对手每一步都会做出最优选择。 $a.$ 状态值...
对抗性搜索与游戏理论
• Adversarial Search, Games
对抗性搜索与游戏理论 1. 相关概念 在传统搜索问题中，智能体可以使用搜索算法确定最佳计划并直接执行以达到目标。但在对抗性环境中，智能体面临一个或多个试图阻止其达成目标的对手。由于无法确定性地预知对手的策略和反应，传统搜索算法不再适用，我们需要新的算法类别来解决对抗性搜索问题，也就是游戏。 2. 确定性零和游戏...
CSP排序
• CSP
CSP排序 1. 排序启发式概念 在约束满足问题的回溯搜索中，排序启发式（Ordering Heuristics）决定了搜索过程中变量选择和值选择的顺序。好的排序策略可以显著减少搜索空间的探索，将指数级的搜索问题转化为多项式时间可解的问题。 排序启发式的核心思想是通过智能的选择顺序来尽早发现冲突或找到解，避...
CSP过滤
• CSP
CSP过滤 1. 相关概念 在约束满足问题中，过滤（Filtering） 是通过约束传播来缩小变量域的技术。过滤的核心思想是在搜索过程中主动推理，提前发现和消除不可能的赋值，从而显著减少搜索空间。 过滤不同于盲目的回溯搜索，它利用约束的结构信息进行局部推理，在赋值之前就排除明显不可行的选择，避免了大量无意义的搜索尝试。...
CSP算法
• CSP
> 下面是对CSP的相关概念的接口预实现，之后会用到 ``python class CSP: """Constraint Satisfaction Problem class""" def __init__(self, variables: List[str], domains:...
约束满足问题
• CSP
约束满足问题 1. 约束满足问题概念 约束满足问题（Constraint Satisfaction Problem, CSP）是一类特殊的搜索问题，它提供了一种结构化的方式来表示和解决组合问题。与传统搜索问题不同，CSP关注的是找到变量赋值的组合，使之满足所有约束条件，而不是寻找从起始状态到目标状态的路径。...
本地搜索
• Search
本地搜索 1. 相关概念 $a.$本地搜索概念 在某些问题中，我们只关心找到目标状态而并不需要知道达到这个状态的优化路径，并不需要通过设计算法来让路径成本优化。局部搜索算法允许我们找到目标状态而无需优化到达那里的路径成本。 在局部搜索问题中，状态空间由“完整”解的集合组成。我们使用这些算法来尝试找到满足某些约束或优化某...
有信息搜索
• Search
有信息搜索 1. 有信息搜索概念 在无信息搜索中，我们会从起始点开始、展开当前边界的所有可能后继状态。但是这样的搜索效率很低，会导致进行很多没必要的搜索。如果我们了解了当前环境的信息、对当前的空间的搜索方向有一定概念，就可以显著提高性能、快速到达目标。 2. 启发式搜索...
无信息搜索
• Search
无信息搜索 1. 无信息搜索概念 $a.$边界（$frontier$） 边界是当前已发现，但是还未被拓展的节点的集合，是搜索的边界。 $b.$边界的拓展（$expand$） 在搜索过程中，我们会展开当前边界的所有可能的后继状态，并把它加入边界中。这相当于下一步Search的探索动作。然后当前的边界就会被丢弃。...
搜索概念
• Search
搜索概念 1. 状态空间大小 如果在一个给定的世界中有$n$个变量对象，它们可以分别取$x_1, x_2, \ldots, x_n$个不同的值，那么状态的总数就是$x_1 \cdot x_2 \cdot \ldots \cdot x_n$。 2. 状态空间图与搜索树 $a.$状态搜索图...