启发式搜索基础：图搜索与树搜索、深度优先与广度优先、启发式函数的概念与作用
好，咱们正式开始聊A*的核心——启发式搜索。说实话，很多初学者一上来就啃A*的代码，结果被open list和close list搞得晕头转向。我个人习惯是，先搞清楚它背后的搜索逻辑，再动手写代码。今天这一讲，咱们就把地基打牢。
图搜索 vs 树搜索：你面对的是迷宫还是森林？
先问个问题：你搜索的时候，会不会走回头路？
树搜索，说白了就是「不回头」。它假设每个节点只被访问一次，从根节点一路往下走，遇到重复状态？不管它，继续往下走。我早期做路径规划时，就犯过这个错——用树搜索处理带环的地图，结果程序直接跑飞了。你想想看，地图上有个环路，树搜索会沿着环路一直转圈，永远找不到终点。
图搜索就不一样了。它会记录哪些节点已经访问过，遇到重复的直接跳过。嗯，这里要注意：图搜索多了一个「closed set」的概念。我建议你在嵌入式平台上，优先用图搜索。为什么？因为嵌入式资源有限，树搜索那种无脑的重复探索，分分钟把内存吃光。
核心区别一句话：树搜索不查重，图搜索查重。A*用的是图搜索，千万别搞混。
我在项目中遇到过这样一个坑：用树搜索做无人机航线规划，结果无人机在一个山谷里来回震荡，就是飞不出去。后来换成图搜索，加上closed set，问题立刻解决。说白了，现实世界的地图到处都是环路，图搜索才是正道。
深度优先 vs 广度优先：先挖到底还是先铺开？
这两种策略，我习惯用「挖井」和「铺路」来理解。
深度优先（DFS），就是认准一条路走到黑。不撞南墙不回头。它的优点是内存占用小——只需要记住当前路径上的节点。但缺点也很明显：如果目标在另一条分支上，你得把整条死路走完才能回头。我记得有一次调试机器人避障，用DFS搜索，结果机器人先钻进了死胡同，绕了一大圈才出来，电池都耗掉一半。
广度优先（BFS），则是层层推进。像水波一样扩散。它的优点是保证找到最短路径（在无权图中）。但代价是内存爆炸——你要同时记住当前层的所有节点。在嵌入式平台上，BFS很容易把堆栈撑爆。
| 特性 | 深度优先（DFS） | 广度优先（BFS） |
|---|---|---|
| 内存占用 | 低（只存当前路径） | 高（存整层节点） |
| 最短路径 | 不保证 | 保证（无权图） |
| 适用场景 | 解空间巨大，目标明确 | 地图小，需要最优解 |
| 嵌入式风险 | 可能陷入死循环 | 内存溢出 |
那么A*是怎么做的？它结合了两者的优点。A*用启发式函数引导搜索方向，既不像DFS那样盲目钻牛角尖，也不像BFS那样无差别扩散。说白了，A*是个「有脑子的搜索」。
启发式函数：给搜索装上导航
启发式函数，英文叫heuristic function，我习惯叫它「估价函数」。它的作用就是告诉你：当前节点离目标还有多远。
你可能会问：既然不知道真实距离，怎么估？嗯，这里有个关键点：启发式函数必须是一个估计值，而且这个估计值不能超过真实值。这叫「可采纳性」（admissibility）。
我的经验：在嵌入式平台上，最常用的启发式函数就是曼哈顿距离和欧几里得距离。曼哈顿距离计算快（只用加减法），适合单片机。欧几里得距离精度高，但涉及开方运算，在低端MCU上慎用。
我曾经在一个STM32项目上，用欧几里得距离做启发式，结果每次计算都要调用sqrt()，整个搜索速度慢了3倍。后来换成曼哈顿距离，速度上去了，路径质量也没差多少。所以我的建议是：在嵌入式平台上，优先用曼哈顿距离。
启发式函数的作用，说白了就是给搜索算法一个「方向感」。没有它，A*就退化成Dijkstra算法（也就是BFS的加权版本）。有了它，A*才能直奔目标，而不是在地图里瞎逛。
一个简单的例子：8数码问题
咱们拿经典的8数码问题来演示。假设你有一个3x3的棋盘，数字1-8乱序排列，你要通过移动空格，把数字排成目标顺序。
树搜索的做法：从初始状态开始，每次移动空格生成新状态，不管这个状态之前有没有出现过。结果？状态数爆炸，几分钟都算不完。
图搜索的做法：记录所有访问过的状态，遇到重复的直接跳过。这样状态数大大减少，但搜索方向还是盲目的。
A*的做法：加上启发式函数。比如用「错位数」作为启发式——统计当前棋盘上有多少个数字不在正确位置上。这个值越小，说明越接近目标。A*会优先扩展启发式值小的节点，直奔目标。
// 伪代码：8数码问题的启发式函数
int heuristic(int board[3][3], int target[3][3]) {
int h = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] != 0 && board[i][j] != target[i][j]) {
h++; // 错位数加1
}
}
}
return h;
}你看，这个启发式函数简单到只有几行代码，但效果立竿见影。我在一个Cortex-M4上跑过，用错位启发式，8数码问题平均0.5秒解出。而不用启发式？跑了5分钟还没出结果。
注意：启发式函数不是越复杂越好。在嵌入式平台上，计算复杂度每增加一点，搜索速度就下降一截。我见过有人用「曼哈顿距离+线性冲突检测」做启发式，精度是高了，但计算量翻倍，整体搜索时间反而变长了。记住：够用就好。
总结一下
这一讲咱们聊了三个核心概念：
- 图搜索 vs 树搜索：图搜索查重，适合嵌入式；树搜索不查重，容易死循环。
- 深度优先 vs 广度优先：DFS省内存但盲目，BFS保证最优但吃内存。A*用启发式取两者之长。
- 启发式函数：给搜索装导航，必须可采纳，嵌入式优先用曼哈顿距离。
下一讲，咱们就要正式进入A*的核心逻辑了——open list、close list、f(n)=g(n)+h(n)这些概念，我会用实际代码一步步拆解。到时候你会发现，A*其实没那么神秘。
公众号:蓝海资料掘金营，微信deep3321