序言
在解决复杂问题时，我们需要将流程分解为步骤。这些步骤有些可以并行执行，有些则存在前后依赖关系必须串行处理。
计算机解决问题的核心方法就是将复杂流程抽象成可描述的过程，通常使用状态图或流程图来表示这种抽象。
9.1 从问题到状态
状态思维：为了简化计算，从不同的事物中提炼出共性，把类似的情况合并到同一种状态中处理。
捕鼠问题分析（例题9.1）
例题 9.1 捕鼠问题 P303：解题的关键就是将老鼠的位置抽象成两个状态：1、3、5 和 2、4，老鼠的位置每天一定是在两个状态见切换的。然后再考虑开启策略。
联想：这个概念让人联想到马尔可夫链中描述随机状态转换的方法。
状态抽象的应用
-
自然语言处理中的词性抽象
- N元组文法模型通过统计N元组在语料库中的出现概率来预测单词序列
- 问题：大多数元组出现频率过低导致统计无意义
- 解决方案：使用词性替代具体词汇进行统计
- 例如将条件概率抽象为
- 在有限状态机翻译应用中，可以简化图计算，此方法能减少3-4个数量级的计算量
-
面向对象程序设计
- 面向对象通过类和接口的抽象实现功能复用
- 开发规范要求：重复出现两次的代码就必须抽象成函数
思考题9.1：排豆子问题
这个问题源自《硅谷来信》中的推棋问题（第173封信）
9.2 状态的等价性
找到计算机中信息的等价性，等价的状态间数据是等效的
整数互换问题（例题9.2）
交换两个整数，不使用额外存储空间的经典解法：
- 将x加到y上：y = x + y
- 从新y中减去原始x：x = y - x
- 从新y中减去新x：y = y - x
理解：这个解法基于(x, y)与(x+y, x-y)的信息等价性，考察工程师对信息保护和等价转换的理解。
等价信息的应用场景
-
归类问题：将复杂信息根据数据特征归类
- 矢量量化通过提取数据特征实现抽象表示
- 例如用四元组描述图像的形状、颜色、大小和旋转
- 编码思维：这本质上是数据的另一种编码方式
- 应用案例：矢量图形和字体设计
- 矢量量化通过提取数据特征实现抽象表示
-
傅立叶变换：时域信号到频域信号的转换
- 傅立叶证明了周期性信号在时域和频域的等价性
- 应用领域：音频降噪、JPEG图像压缩
-
硬件设计
- CPU的加减乘除运算实际上仅通过加法、移位和查表实现
9.3 因果关系：状态间的联系
三对老虎过河问题（例题9.3）
理解系统状态，分清合法和非法状态，由此引出解决方案：
- 列举所有可能的状态
- 构建状态转移图
- 为每个状态寻找合法的后续状态
- 通过穷举法找到解决方案
状态因果关系的理解
- 前驱状态是后继状态的原因，后继状态是前驱状态的结果
- 与贝叶斯网络的基本概念相通
实践指导：任何状态，要了解来龙去脉，找到原因和结果
- 测试工作中必须明确区分合法与非法状态
- 调试本质上是逆向推理异常状态的原因