陈述式问题求解

CIE A-Level 计算机科学· 20 分钟阅读

1. 陈述式与命令式范式的核心区别★★☆☆☆⏱ 6 min

📘 定义

陈述式问题求解

一种问题求解范式，你只需要定义问题事实、期望的最终状态，以及所有必须满足的规则/约束条件。由通用求解器推导得到解，不需要你编写明确的求解步骤。

例:

描述谜题的规则，而不需要编写如何求解谜题的代码

相比之下，命令式问题求解要求你明确定义将输入转换为期望输出的每一个步骤。每一个决策和操作都由问题求解者排序。陈述式问题求解将寻找解路径的工作从人类问题求解者转移到了通用求解器。

陈述式回答问题是什么；命令式回答如何求解问题
修改陈述式方案只需要更新事实/规则；修改命令式方案需要改变步骤顺序
陈述式求解器是通用的；命令式解是特定于问题的

📐 例题

比较两种范式下求解「找出1到10之间所有偶数」的区别

1
命令式方法：明确的逐步指令：
2
1. 初始化一个空结果列表
2. 从1迭代到10
3. 对每个数字，检查它除以2的余数是否为0
4. 将符合条件的数字添加到结果列表
5. 返回结果列表
3
陈述式方法：仅描述问题：
4
$A = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$
5
将偶数定义为满足 $n mod 2 = 0$ 的 $n$ 。解是所有满足该规则的 $n \in A$ 。求解器不需要被告知如何迭代就能找到结果。
6
两种方法得到相同的结果 $[2, 4, 6, 8]$ ，但问题建模方法有本质区别。

2. 约束满足：陈述式问题结构★★★☆☆⏱ 8 min

📘 定义

约束满足问题 (CSP)

标准的陈述式问题结构，由三个核心组件组成：一组变量、每个变量的可能取值范围，以及有效解必须满足的一组约束条件。

例:

数独：每个单元格是一个变量，取值范围1-9，约束条件是行/列/宫格内数字不重复

大多数适合陈述式求解的复杂现实问题都可以建模为CSP。一旦问题被正确定义，通用CSP求解器就可以找到有效解或确认无解，不需要编写自定义求解代码。

📐 例题

将八皇后问题建模为陈述式CSP

1
1. 定义变量：在8×8棋盘上每行放置一个皇后。令 $Q_{i}$ 为第 $i$ 行皇后所在的列号，其中 $i = 1$ 到 $8$ 。
2
1. 定义取值范围：每个皇后可以放在1到8的任意一列，因此：
3
$\text{dom}(Q_i) = \{1, 2, 3, 4, 5, 6, 7, 8\} \quad \forall i$
4
1. 定义约束条件：任意两个皇后不能互相攻击：
5
$Q_i \neq Q_j \quad \forall i \neq j \text{ (no shared column)} \\ |Q_i - Q_j| \neq |i - j| \quad \forall i \neq j \text{ (no shared diagonal)}$
6
求解器使用这些约束条件为所有 $Q_{i}$ 找到一组有效值，不需要指定回溯或搜索步骤。

Exam tip:

如果考试中要求你构建一个CSP，你只需要描述约束条件，不需要描述如何检查约束条件。

3. 优势、劣势与应用场景★★☆☆☆⏱ 6 min

陈述式问题求解并不适用于所有问题。它在某些问题类型上有明显优势，但相比命令式方法在另一些问题类型上存在显著局限性。

优势：更容易对有多个约束的复杂问题建模，开发速度更快，调试更简单（只需要检查事实/规则），通用求解器可复用
劣势：效率低于自定义命令式解，求解器性能依赖问题复杂度，更难对边界情况进行优化

📐 例题

判断陈述式方法是否适用于：1）网店的商品排序程序，2）学校课程表排课系统

1
1. 排序程序：排序是已经被充分研究、存在优化的逐步算法的过程。陈述式方法（仅描述输出必须有序）的效率远低于自定义命令式算法。因此这里不适合使用陈述式方法。
2
1. 学校排课：排课有数十个固定约束：一位教师不能同时出现在两个地方，学生班级不能有重叠课程，教室容量限制。用陈述式描述这些约束比编写自定义排课代码简单得多。因此这里非常适合使用陈述式方法。
3
结论：对于存在大量明确定义的约束、解路径很难手动编码实现的问题，陈述式方法效果最好。

4. 常见陷阱

错误做法:

当要求构建陈述式问题模型时，描述逐步求解指令

原因:

陈述式问题求解只需要描述问题约束和最终目标，不需要描述求解器应该如何得到解

正确做法:

列出所有有效解必须满足的变量、取值范围和约束条件，将求解过程留给求解器

错误做法:

声称陈述式问题求解在所有问题类型上都优于命令式

原因:

对于已经充分研究的问题，陈述式方法相比自定义优化的命令式解存在显著的性能开销

正确做法:

根据问题选择合适的范式：复杂约束问题使用陈述式，常规算法使用命令式

错误做法:

遗漏约束满足问题的所有三个核心组件

原因:

没有变量、取值范围和约束条件，求解器无法得到完整定义的问题

正确做法:

当要求构建CSP时，始终明确列出所有三个组件

错误做法:

将陈述式问题求解与陈述式编程语言混淆

原因:

虽然像Prolog这样的陈述式语言常被用于实现陈述式解，但该范式独立于所使用的编程语言

正确做法:

记住陈述式问题求解是一种问题建模方法，可以用任何编程语言实现

5. 速查表

概念	核心描述	关键特征
陈述式问题求解	描述问题是什么	关注事实/约束，而非步骤
命令式问题求解	描述如何求解问题	明确的逐步指令
约束满足问题	标准陈述式问题结构	由变量、取值范围、约束组成
最适合使用陈述式	多约束的复杂问题	开发更快，求解器可复用
最适合使用命令式	充分研究的常规算法	性能更高，可自定义优化

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 11
比较陈述式/命令式方法
2023 · 12
将数独建模为陈述式问题
2024 · 13
陈述陈述式问题求解的优势

深入阅读

syllabusCIE 9618 A-Level 计算机科学大纲

下一步

陈述式问题求解是一种核心计算思维范式，是许多现代人工智能和知识表示技术的基础。它为难以逐步编码的复杂现实问题提供了灵活的建模方式，涵盖排课、谜题求解到路径规划等领域。理解陈述式和命令式方法的区别，能帮助你在CIE 9618考试和实际软件开发中，为遇到的任何问题选择正确的工具。这个基础为你探索本单元后续介绍的更专业的问题求解范式做好准备。