---
title: 启发式方法论
date: "2015-12-20 21:40"
tags: ["方法论","算法"]
published: true

---

启发式（Heuristic）是一套在信息不完备或计算不可行时，用经验规则快速逼近可行解的方法。它不追求数学最优，目标是在合理时间内找到足够好的解。

## 一、词源

这个词来自希腊语 heuriskein（εὑρίσκειν），意思是发现、找到。"尤里卡"（Eureka）也来自同一个词根，阿基米德在浴缸里喊的就是这句话。这两个词共享的词源，反映出启发式最初指向的是直觉式发现，而不是演绎式证明。

## 二、与算法的区别

启发式和算法（Algorithm）的差异体现在几个维度上：

| 维度 | 算法（Algorithm） | 启发式（Heuristic） |
|------|------------------|-------------------|
| **目标** | 精确、最优、可证明 | 快速、可行、够好 |
| **完备性** | 保证找到解（如果存在） | 不保证 |
| **最优性** | 保证最优 | 不保证 |
| **代价** | 时间/空间成本可能极高 | 可控的低成本 |
| **来源** | 数学演绎、形式逻辑 | 经验观察、直觉规则、领域知识 |

算法通过穷举保证正确性，启发式通过经验规则减少计算量，但不保证结果最优。

N 皇后和数独可以说明这个差异：

- 纯回溯是算法：它完备，会遍历所有可能，但速度慢。
- MRV（最小剩余值）是启发式：它不完备，不保证一定更快，但优先填候选数最少的格子，通常能大幅减少搜索空间。

## 三、来自三个学科的用法

"启发式"不是计算机科学独创的词，数学、心理学和人工智能三个学科分别在不同时期赋予了它具体含义。

### 1. 数学与运筹学：启发式算法

面对 NP-hard 问题（如 TSP 旅行商问题），精确算法需要指数级时间。数学家转而使用贪心、局部搜索、模拟退火、遗传算法等方法，不保证最优解，但计算成本可控，这类方法称为计算启发式。

### 2. 心理学与认知科学：启发式思维

1950 到 1970 年代，诺贝尔经济学奖得主 Herbert Simon 研究人类在复杂决策中的行为，发现人脑不会计算最优解，而是依赖满意性原则（Satisficing）：找到一个够好的选项就停止搜索。

此后 Kahneman 和 Tversky 的"启发式与偏见"（Heuristics and Biases）研究进一步说明，人脑用代表性启发、可得性启发、锚定效应等捷径做决策，这类现象称为认知启发式。

### 3. 人工智能：启发式搜索

1960 年代人工智能研究初期，Newell 和 Simon 的"逻辑理论家"（Logic Theorist）程序最早用启发式规则引导搜索树。此后的 A* 算法、Minimax 加 α-β 剪枝、博弈树的启发式评估函数，都是把领域知识编码成规则用于剪枝。

## 四、为什么需要启发式

精确算法在几类场景下不可行：

1. 组合爆炸：数独有 9^81 种可能状态，穷举在可接受的时间内算不完。
2. 信息不完备：围棋、德州扑克中看不到对手的全部信息，无法精确计算。
3. 实时性约束：自动驾驶需要在 10ms 内做出决策，等不及 Dijkstra 算出全局最优路径。
4. 问题本身缺少数学定义："设计一个好看的 UI"没有最优解，只能依赖经验判断。

这几类限制的共同点是：精确计算的成本或前提条件不满足，启发式提供了一种在限制下仍能给出可用结果的方式。

## 五、常见题目中的对应

下面几道题都能看到精确算法和启发式优化的对应关系：

| 题目 | 精确算法 | 启发式优化 |
|-----------|---------|-----------|
| 组合求和 | 纯回溯枚举 | 排序后 `break` 剪枝（利用单调性） |
| N 皇后 | 逐行暴力试 | MRV 优先填约束最多的位置 |
| 数独 | 顺序填空格 | 候选最少优先＋唯一候选数（Naked Single） |
| A* 寻路 | Dijkstra 全局最优 | 加 `h(n)` 启发函数引导搜索方向 |

## 六、小结

启发式的共同点是把领域经验编码成规则，用来减少搜索空间或决策成本，代价是放弃完备性和最优性保证。选择启发式还是精确算法，取决于问题规模、时间约束和是否能接受次优解。

---

**相关阅读**：
- [如何分析问题](./12-12-如何分析问题.md)
- [回溯算法：从组合问题到数独的决策树艺术](./02-14-回溯算法-从组合问题到数独的决策树艺术.md)