【人工智能学习-AI-MIT公开课-第8. 约束：搜索、域缩减】
为了应对大学院考试，我们来学习相关人工智能相关知识，并且是基于相关课程。使用课程为MIT的公开课。通过学习，也算是做笔记，让自己更理解些。要素含义变量（Variables）要决定的对象域（Domain）每个变量可以取的值约束（Constraints）哪些取值组合是不允许的数独课程表安排地图着色机器人任务分配在还没真正搜索之前，先把“不可能成功的值”从域里删掉这样做的目的只有一个：👉让搜索更快知识
人工智能学习-AI-MIT公开课-第8. 约束：搜索、域缩减
1-前言
为了应对大学院考试，我们来学习相关人工智能相关知识，并且是基于相关课程。使用课程为MIT的公开课。
通过学习，也算是做笔记，让自己更理解些。
2-课程链接
3-具体内容解释说明
一、这节课在讲什么（一句话版）
在“有约束条件”的情况下，如何用搜索更快、更聪明地找到解。
和普通搜索的区别是：
❌ 不是“盲目地试所有可能”
✅ 而是一边搜索，一边删掉不可能的选择（域缩减）
二、什么是「约束满足问题（CSP）」
1️⃣ 基本构成（考试必会）
一个 CSP 由三部分组成：
| 要素 | 含义 |
|---|---|
| 变量（Variables） | 要决定的对象 |
| 域（Domain） | 每个变量可以取的值 |
| 约束（Constraints） | 哪些取值组合是不允许的 |
📌 经典例子：
- 数独
- 课程表安排
- 地图着色
- 机器人任务分配
三、搜索（Search）在 CSP 中怎么用？
2️⃣ 回溯搜索（Backtracking Search）
最基本的方法：
- 给第一个变量选一个值
- 检查是否违反约束
- 若违反 → 回退（backtrack）
- 否则继续下一个变量
👉 这是“搜索”的核心
📌 但问题是：
如果每个变量的域很大，搜索会爆炸
四、域缩减（Domain Reduction）是这节课的重点
3️⃣ 什么是「域缩减」
在还没真正搜索之前，
先把“不可能成功的值”从域里删掉
这样做的目的只有一个：
👉 让搜索更快
4️⃣ 最重要的概念：一致性（Consistency）
■ 弧一致性（Arc Consistency, AC）
如果：
- 变量 X 的某个取值
- 在 Y 的域中 找不到任何能满足约束的对应值
👉 那这个取值 直接删掉
📌 这就是 AC-3 算法 的思想（入试常考名字）
五、这节课和「路径搜索」的关系（重点理解）
你之前学的：
| 内容 | 属于 |
|---|---|
| BFS / Dijkstra / A* | 状态空间搜索 |
| CSP | 约束空间搜索 |
两者共同点：
- 都是搜索
- 都在减少无效探索
不同点：
- 路径搜索：减少 走错路
- CSP：减少 选错值
👉 思想是完全一致的
六、这节课在大学院入试里怎么考？
常见出题方式（不是写代码）
- CSP 的三个要素是什么？
- 域缩减的目的是什么？
- 弧一致性在做什么？
- 为什么域缩减能提高搜索效率？
- CSP 与単纯搜索的区别是什么？
📌 全是“理解型选择题 / 解释题”
七、和你现在做的 AI 入试的直接关系
这节课：
- ✔ 正好覆盖 「搜索」这个大考点
- ✔ 是 路径探索（A）的思想延伸*
- ✔ 是 AI 入试里 最容易出概念题的一章
你只要记住一句话就够了：
CSP = 搜索 + 提前剪枝（域缩减）
4-课后练习（日语版本）
【問題1】CSP の基本構成
制約充足問題（CSP）を構成する要素の組として正しいものはどれか。
A. 状態・行動・評価関数
B. ノード・エッジ・重み
C. 変数・ドメイン・制約
D. 入力・出力・学習データ
【問題2】ドメイン縮小の目的
CSP においてドメイン縮小を行う主な目的として最も適切なものはどれか。
A. すべての解を列挙するため
B. 制約そのものを削除するため
C. 探索空間を削減し，探索効率を向上させるため
D. 評価関数の精度を高めるため
【問題3】弧一貫性（Arc Consistency）
弧一貫性に関する説明として正しいものはどれか。
A. 各変数が唯一の値を持つ状態を指す
B. ある変数の値に対して，他の変数のドメインに制約を満たす値が存在することを保証する
C. すべての制約を同時に満たす完全解であることを保証する
D. 探索後にのみ適用される評価基準である
【問題4】探索と CSP の関係
探索問題と CSP の関係についての説明として最も適切なものはどれか。
A. CSP は探索を用いず，数式のみで解かれる
B. 探索問題では制約は一切考慮されない
C. CSP は探索に加えて制約を用いた枝刈りを行う問題である
D. CSP は A* 探索と完全に同一の問題設定である
回答方法
次の形式でまとめて答えてください：
1：
2：
3：
4：
5-课后答案解析（日语版本）
【採点結果】
1：C ✅
2：C ✅
3：B ✅
4：C ✅
👉 4 / 4 正解（满分）
【問題1】CSP の基本構成
正解：C（変数・ドメイン・制約）
入试官在看什么？
- 你是否真的知道 CSP 是什么
- 有没有把它和「图」「搜索树」「学习问题」混在一起
为什么这是“送分题”？
-
A / B / D 分别是
- 搜索问题
- 图问题
- 机器学习问题
👉 一看就该排除
你选 C = 概念清晰。
【問題2】ドメイン縮小の目的
正解：C（探索空間削減）
入试官在筛什么？
- 懂不懂 “为什么要做域缩减”
- 能不能说出一句像研究生的话
你选 C 说明你理解：
域缩减不是为了“求解”，而是为了“加速搜索”。
这正是 研究生思维。
【問題3】弧一貫性（Arc Consistency）
正解：B
入试官在防谁？
- 只会背名词、不懂含义的人
- 把“局部一致性”误以为“全局解”的人
你选 B，说明你知道：
- 弧一致性 ≠ 解
- 只是 删不可能的值
👉 这是 CSP 的核心理解点。
【問題4】探索と CSP の関係
正解：C
这是“综合理解题”
- 你是否能把 搜索 和 约束 放在一个框架里理解
你选 C 表明你已经形成了这句话：
CSP = 搜索 + 约束による枝刈り
这句话 在面试和笔试都可以直接用。
6-总结
知识一点点记录吧，最后应对考试，打下基础
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
9
0- 0
已为社区贡献3条内容
所有评论(0)