简介野人与传教士经典逻辑谜题的C实现代码包面向算法学习者与C编程初学者可用于理解状态空间搜索、约束满足、图论建模以及递归与队列两种核心实现技巧。压缩包共14个文件主要包含C源码、可执行程序、Visual C工程配置dsp/dsw、编译调试辅助文件pdb/ilk/idb以及DOC说明文档整体体积仅185KB层级分明便于按需查阅。已有263人浏览学习。资源中的程序通过状态三元组表示两岸人数与船的位置分别演示深度优先搜索和广度优先搜索的求解过程并引入剪枝条件过滤无效分支同时利用结构体或类封装状态转换逻辑。随包文档详细梳理了问题描述、算法原理、代码注释及运行方法可为课程设计、算法实验或初学者自备实践提供完整参考帮助读者直观理解经典人工智能搜索问题的编码落地与调试优化。1. 野人与传教士一个用C讲清状态搜索的经典约束题三个传教士和三个野人站在河左岸只有一条能坐两个人的船。规则只有一条任何时刻任一岸边野人数多于传教士数就会出事。目标是把六个人全部运到右岸。看起来是智力游戏但它本质上是一个有限状态空间上的搜索问题图论建模、DFS/BFS、剪枝和状态去重在这里全都能落地。man.rar 里那份 Visual C 6.0 时代的工程把完整求解过程压成了一个可单步调试的C/C程序解压后不仅有 yeren.c 源码还有一份《野人与传教士问题.doc》适合一边看代码一边把搜索树画出来。这个题对想弄懂状态搜索的读者来说比八数码更友好因为状态少、规则简单但能讲的坑一个不少。2. 状态空间建模用结构体约束河岸的合法局面初写这道题的人最容易犯的错是只记录左右岸的传教士和野人人数忘了记录船在哪边。船的位置决定了下一步动作是“从左往右”还是“从右往左”漏掉它会导致搜索在同一个局面里来回打转。所以先定义一个状态节点再把合法性和转移规则写清楚后面所有算法都建立在这层抽象上。2.1 状态定义三变量就够别搞八变量因为总人数固定为 3 个传教士和 3 个野人右岸人数可以由左岸人数推出所以只要三个变量就能表示完整局面左岸传教士数、左岸野人数、船的位置。C 里用结构体最直观// 状态节点左岸人数 船位 struct State { int leftM; // 左岸传教士人数0~3 int leftC; // 左岸野人人数0~3 int boat; // 0: 船在左岸, 1: 船在右岸 };leftM 和 leftC 的取值范围都是 0 到 3boat 只有 0 和 1 两种取值。因为人是不可分割的所以这三个整数就能枚举全部可能的组合粗略算一下是 4×4×232 个候选状态实际合法状态还要再过滤。如果用四变量甚至八变量建模同一个实际状态会被重复表示visited 集合也跟着变大搜索时容易出现“看起来是两个状态、其实是一种局面”的重复展开。变量含义取值范围leftM左岸传教士数0~3leftC左岸野人数0~3boat船所在岸0 左岸1 右岸合法性判断是搜索的第一道剪枝。规则是“野人数不能超过传教士数”但有个容易被忽略的例外如果该岸传教士数为 0那么野人多几个也不构成威胁因为没有对象可以吃。写成函数// 判断一个状态是否合法 bool valid(const State s) { // 左岸人数必须在合法范围内 if (s.leftM 0 || s.leftM 3) return false; if (s.leftC 0 || s.leftC 3) return false; int rightM 3 - s.leftM; // 右岸传教士数 int rightC 3 - s.leftC; // 右岸野人数 bool leftOK (s.leftM 0) || (s.leftM s.leftC); bool rightOK (rightM 0) || (rightM rightC); return leftOK rightOK; }这个函数在每次状态转移后都会调用一次。参数用 const 引用避免复制整个结构体返回值直接表示该局面能不能继续走下去。注意 rightM 和 rightC 的关系很多实现只检查左岸不检查右岸结果搜索出一堆右岸已经出事的中间状态最后路径打印出来才发现传教士被吃掉了。合法状态数量远小于 32筛完之后只剩大约 16 个左右这是后面搜索能在毫秒级完成的基础。2.2 状态转移把“船载两人”翻译成动作表船每次可以载 1 人或 2 人不能超载。从当前岸边选择上船的人然后整体移动到对岸。这里不需要动态生成所有人员组合直接枚举五个固定动作即可1 个传教士、2 个传教士、1 个野人、2 个野人、1 传教士加 1 野人。// 动作表每行表示上船的(传教士数, 野人数) const int actions[][2] { {1, 0}, // 船上只有1个传教士 {2, 0}, // 船上2个传教士 {0, 1}, // 船上只有1个野人 {0, 2}, // 船上2个野人 {1, 1} // 传教士和野人各1个 };为什么不需要“2传教士1野人”因为船最多坐两个人超载了。这个动作表天然排除了超载情况。接下来是状态转移函数给定当前状态和动作计算下一个状态// 从当前状态 cur 执行一个动作成功则写入 next bool moveState(const State cur, int actM, int actC, State next) { State s cur; if (cur.boat 0) { // 船在左岸人从左岸减掉船开到右岸 s.leftM - actM; s.leftC - actC; s.boat 1; } else { // 船在右岸人加到左岸船开回左岸 s.leftM actM; s.leftC actC; s.boat 0; } if (valid(s)) { next s; return true; } return false; }这里的关键是方向判断。boat 等于 0 表示船在左岸动作是“从左边带走人”所以左岸人数减少boat 等于 1 表示船在右岸动作是“从右边带人回来”所以左岸人数增加。船上的临时组合不需要单独检查因为五个动作里唯一可能“传教士和野人同船”的是 {1,1}两边人数相等不违反“野人不能多于传教士”的语义。如果题目规则同时约束船上这个动作表也只需要额外加一次判断即可。有了状态定义、合法性判断和动作表搜索算法的输入输出就齐了。这里顺带说一个建模上的常见误区有人会把左右两岸各用一组变量存然后单独记录船的位置变成四个变量甚至七个变量比如“左M、左C、右M、右C、船位”。这样表示更直白但因为左右岸人数总和恒定属于冗余建模。冗余状态会让 visited 集合变大而且很容易出现同一个实际状态被当成两个不同状态处理导致搜索重复。用三变量建模后编码和去重都会简单很多第 5 章会专门讲状态编码。3. 搜索策略DFS 与 BFS 在同一个图上相遇状态空间模型建好后问题就变成了在一张有向图中找从初始状态到目标状态的一条路径。这张图的节点是合法状态边是五个动作。求解的核心动作是搜索而 DFS 和 BFS 各自的特点在这个小规模问题上体现得非常清楚。3.1 深度优先递归栈里的人工推理DFS 的策略是一条路走到黑走不通再回头。它和人工推理很接近先试着把两个野人送过去不行就换一个组合。用递归实现时系统调用栈天然承担了路径栈的角色只需要额外维护一个 visited 集合防止状态循环。#include vector #include set bool dfs(State cur, vectorState path, setint visited) { // 目标所有人到右岸且船在右岸 if (cur.leftM 0 cur.leftC 0 cur.boat 1) { path.push_back(cur); return true; } // 尝试五个上船动作 for (auto act : actions) { State next; if (moveState(cur, act[0], act[1], next)) { int code next.leftM * 8 next.leftC * 2 next.boat; if (visited.find(code) visited.end()) { visited.insert(code); path.push_back(cur); if (dfs(next, path, visited)) return true; path.pop_back(); } } } return false; }这段代码有几个细节值得说明。visited.insert(code) 发生在递归进入之前而且递归返回失败后不删除这是为了避免同一个状态被重复扩展。在这个问题里同一个状态无论通过哪条路径到达后续可走的动作完全相同所以保留 visited 是安全的。path.push_back(cur) 放在递归调用前表示把当前节点记录进路径找到目标后逐层返回最终 path 里就是从起点到终点的完整路径。如果递归深度过大可以考虑把递归改成显式栈但这个问题最大状态数只有 32递归深度不会超过几十层直接用递归没问题。DFS 找到的第一个解不一定是步数最少的它只保证“存在解”。如果你只是想验证题目有解DFS 够用如果想知道最短需要几步必须换 BFS。3.2 广度优先队列保证最短步数BFS 按层扩展第一次遇到目标状态时的路径一定是最短的。实现上用 queue 保存“当前状态 到当前状态的历史路径”。由于每个节点都要保存一份路径内存开销比 DFS 大但这道题状态空间小完全承受得起。#include queue struct Node { State s; vectorState path; // 从起点到当前节点的路径 }; bool bfs(State start) { queueNode q; setint visited; visited.insert(start.leftM * 8 start.leftC * 2 start.boat); Node startNode; startNode.s start; startNode.path.push_back(start); q.push(startNode); while (!q.empty()) { Node cur q.front(); q.pop(); // 判断目标状态 if (cur.s.leftM 0 cur.s.leftC 0 cur.s.boat 1) { // 输出 cur.path即为最短路径 return true; } for (auto act : actions) { State next; if (moveState(cur.s, act[0], act[1], next)) { int code next.leftM * 8 next.leftC * 2 next.boat; if (visited.insert(code).second) { Node n; n.s next; n.path cur.path; n.path.push_back(next); // 注意这里存的是下一状态 q.push(n); } } } } return false; }注意路径存储的细节cur.path 保存的是到当前状态为止的路径扩展时把下一状态 next 追加到副本里而不是直接 push 到 cur.path否则会污染当前节点的多条出边。BFS 的 visited 在入队时立即标记防止同一状态被多个分支重复入队。如果等出队时再标记队列里会积压大量重复节点虽然结果一样但内存和时间都会明显上涨。3.3 剪枝与去重的边界条件有了合法状态过滤和 visited 去重搜索空间已经很小了但还有两个可以进一步压缩的点。第一个是剪掉“对岸状态非法”的中间状态这已经在 valid 里做了第二个是剪掉船空驶的情况动作表里没有 {0,0}天然排除了船自己移动的可能性。下面用表格对比 DFS 和 BFS 在本问题中的实际表现比较项DFSBFS是否需要 visited需要防止递归死循环需要防止队列膨胀路径长度保证不保证最短第一次找到就是最短空间复杂度O(深度)约几十个状态O(层数)需要保存路径副本实现难度递归简单队列结构稍复杂适合场景只求有解、快速验证求最短步数、教学演示剪枝还有一个常见误区有人会在 visited 之外再加一个“深度上限”超过 20 步就终止。这是不必要的因为状态空间只有 32 个节点合法路径再长也不会无限延伸加深度上限反而可能漏解。遇到搜索异常慢的时候优先检查 visited 插入位置和状态转移方向而不是盲目限深度。4. 从 man.rar 解压到可运行工程VC6 工程文件的含义man.rar 这个名字容易让人联想到 Linux 的 man 命令但这里只是压缩包名字和命令行文档没有关系。解压后你会看到一组 Visual C 6.0 时代的工程文件yeren.c、yeren.opt、yeren.plg、yeren.dsw、yeren.ncb、Debug 目录外加一份《野人与传教士问题.doc》。文件不多但每个后缀背后都有值得解释的用途。4.1 文件清单谁是源码谁是工程元数据文件作用yeren.c实际算法源码核心逻辑都在这里yeren.dspVC6 的工程文件记录源文件列表和编译选项yeren.dsw工作区文件可同时管理多个 dsp 工程yeren.opt编辑器状态如断点、窗口位置可删除yeren.plg编译日志索引可删除yeren.ncb智能感知缓存可删除Debug编译输出目录里面是中间文件和 exe野人与传教士问题.doc问题描述与算法说明文档这里有个容易误导人的地方摘要说它是 C 实现但实际文件名是 yeren.c。在 VC6 里.c 文件会按 C 语言语法编译.cpp 才会启用 C 特性。这个工程本身用的是结构体和函数属于典型的 C 风格但用 C 编译器也能编译因为代码里没有用到与 C 冲突的语法。你可以直接改名成 yeren.cpp或者用现代编译器统一按 C 编译效果一样。4.2 用现代环境替换 VC6 编译运行VC6 是 1998 年的编译器在今天的 Windows 上直接运行经常出现兼容性报错。常见做法是直接用 gcc 或新版 Visual Studio 编译 yeren.c工程文件只当阅读参考。# 用 gcc 编译并运行 gcc yeren.c -o yeren.exe ./yeren.exe # 如果想按 C 方式编译改个后缀或加 -x c 参数 gcc yeren.c -x c -o yeren_cpp.exe ./yeren_cpp.exe如果你的环境里有 Visual Studio也可以打开 yeren.dsw。VS 会自动提示升级工程确认后重新编译即可。编译时留意几个典型问题一是 VC6 允许不声明就用的函数现代编译器会直接报错二是隐式类型转换提示级别更高比如把 int 直接赋给 bool 可能出 warning但不影响结果。Debug 目录里如果有 yeren.exe那是 VC6 当年编译的产物在较新的系统上很可能闪退原因多半是工程配置里用了静态连接 CRT而不是算法本身的问题。4.3 最常踩的坑栈溢出和死循环都来自 visited 漏插我在调试类似工程时见过最多的问题是DFS 递归不设 visited或者 visited 只标记当前路径上的节点导致搜索在几个状态之间无限循环。表现是程序运行后长时间不退出CPU 占满。解决办法是先打印每个入队/递归的状态编码把搜索序列 dump 到文件里很快就能看到循环节。另一个坑是船位的初始值。初始状态所有人都在左岸船也在左岸所以 boat 应该为 0。有人把船位写成 1搜索直接从“船在右岸”开始此时左岸没有人但目标状态也是所有人在右岸程序会误判为一步都不需要走直接输出空路径。验证的办法是打印初始状态和目标状态确认两者不是一个状态。文档《野人与传教士问题.doc》里一般会画状态转移图或者给出一个可行解。如果你运行结果和文档里的步数不一致先检查 BFS 是否真正按层扩展而不是队列写成了栈。把 queue 换成 stack 并不会让程序崩溃只是会得到一个非最短路径这种错误非常隐蔽。5. 状态哈希化把结构体压成 int 的下标访问前面代码里两次出现leftM * 8 leftC * 2 boat这种编码不是随手写的它是这道题最高效的状态去重方式。三个变量的取值范围分别是 0~3、0~3、0~1因此可以按二进制位拼接leftM 占 2 位leftC 占 2 位boat 占 1 位总共 5 位正好覆盖 32 个状态。// 把状态编码为 0~31 的整数 inline int encode(const State s) { return (s.leftM 3) | (s.leftC 1) | s.boat; }用移位写法更贴近位运算风格结果和乘法一样leftM 乘以 8leftC 乘以 2再加 boat。0 到 3 的二进制是 00 到 11左移 3 位后占据编码的高两位leftC 左移 1 位占据中间两位boat 占据最低位。这样每个编码都互不冲突可以用长度为 32 的 bool 数组替代 set。bool visited[32] {false}; int code encode(next); if (!visited[code]) { visited[code] true; // 入队或递归 }bool 数组访问是 O(1) 且没有哈希计算开销比 set 快得多。虽然这道题只有 32 个状态性能差异不明显但这个小技巧可以迁移到任何“状态分量取值范围有限”的搜索题上比如八数码、华容道。甚至你可以用编码直接当数组下标来预计算每个状态的合法性把 valid 调用从搜索循环里移除。验证编码正确性的方法很简单打印所有合法状态的编码检查是否有重复或遗漏。合法状态大约只有 16 个逐一对照左右岸人数与船位就能发现编码公式是否写错。我就是用这个方法查出来一次 leftC 忘记左移导致所有野人人数为奇数的状态全部撞在同一个编码上。本文还有配套的精品资源点击获取 用C++破解野人与传教士：状态搜索、DFS/BFS与剪枝实战
简介野人与传教士经典逻辑谜题的C实现代码包面向算法学习者与C编程初学者可用于理解状态空间搜索、约束满足、图论建模以及递归与队列两种核心实现技巧。压缩包共14个文件主要包含C源码、可执行程序、Visual C工程配置dsp/dsw、编译调试辅助文件pdb/ilk/idb以及DOC说明文档整体体积仅185KB层级分明便于按需查阅。已有263人浏览学习。资源中的程序通过状态三元组表示两岸人数与船的位置分别演示深度优先搜索和广度优先搜索的求解过程并引入剪枝条件过滤无效分支同时利用结构体或类封装状态转换逻辑。随包文档详细梳理了问题描述、算法原理、代码注释及运行方法可为课程设计、算法实验或初学者自备实践提供完整参考帮助读者直观理解经典人工智能搜索问题的编码落地与调试优化。1. 野人与传教士一个用C讲清状态搜索的经典约束题三个传教士和三个野人站在河左岸只有一条能坐两个人的船。规则只有一条任何时刻任一岸边野人数多于传教士数就会出事。目标是把六个人全部运到右岸。看起来是智力游戏但它本质上是一个有限状态空间上的搜索问题图论建模、DFS/BFS、剪枝和状态去重在这里全都能落地。man.rar 里那份 Visual C 6.0 时代的工程把完整求解过程压成了一个可单步调试的C/C程序解压后不仅有 yeren.c 源码还有一份《野人与传教士问题.doc》适合一边看代码一边把搜索树画出来。这个题对想弄懂状态搜索的读者来说比八数码更友好因为状态少、规则简单但能讲的坑一个不少。2. 状态空间建模用结构体约束河岸的合法局面初写这道题的人最容易犯的错是只记录左右岸的传教士和野人人数忘了记录船在哪边。船的位置决定了下一步动作是“从左往右”还是“从右往左”漏掉它会导致搜索在同一个局面里来回打转。所以先定义一个状态节点再把合法性和转移规则写清楚后面所有算法都建立在这层抽象上。2.1 状态定义三变量就够别搞八变量因为总人数固定为 3 个传教士和 3 个野人右岸人数可以由左岸人数推出所以只要三个变量就能表示完整局面左岸传教士数、左岸野人数、船的位置。C 里用结构体最直观// 状态节点左岸人数 船位 struct State { int leftM; // 左岸传教士人数0~3 int leftC; // 左岸野人人数0~3 int boat; // 0: 船在左岸, 1: 船在右岸 };leftM 和 leftC 的取值范围都是 0 到 3boat 只有 0 和 1 两种取值。因为人是不可分割的所以这三个整数就能枚举全部可能的组合粗略算一下是 4×4×232 个候选状态实际合法状态还要再过滤。如果用四变量甚至八变量建模同一个实际状态会被重复表示visited 集合也跟着变大搜索时容易出现“看起来是两个状态、其实是一种局面”的重复展开。变量含义取值范围leftM左岸传教士数0~3leftC左岸野人数0~3boat船所在岸0 左岸1 右岸合法性判断是搜索的第一道剪枝。规则是“野人数不能超过传教士数”但有个容易被忽略的例外如果该岸传教士数为 0那么野人多几个也不构成威胁因为没有对象可以吃。写成函数// 判断一个状态是否合法 bool valid(const State s) { // 左岸人数必须在合法范围内 if (s.leftM 0 || s.leftM 3) return false; if (s.leftC 0 || s.leftC 3) return false; int rightM 3 - s.leftM; // 右岸传教士数 int rightC 3 - s.leftC; // 右岸野人数 bool leftOK (s.leftM 0) || (s.leftM s.leftC); bool rightOK (rightM 0) || (rightM rightC); return leftOK rightOK; }这个函数在每次状态转移后都会调用一次。参数用 const 引用避免复制整个结构体返回值直接表示该局面能不能继续走下去。注意 rightM 和 rightC 的关系很多实现只检查左岸不检查右岸结果搜索出一堆右岸已经出事的中间状态最后路径打印出来才发现传教士被吃掉了。合法状态数量远小于 32筛完之后只剩大约 16 个左右这是后面搜索能在毫秒级完成的基础。2.2 状态转移把“船载两人”翻译成动作表船每次可以载 1 人或 2 人不能超载。从当前岸边选择上船的人然后整体移动到对岸。这里不需要动态生成所有人员组合直接枚举五个固定动作即可1 个传教士、2 个传教士、1 个野人、2 个野人、1 传教士加 1 野人。// 动作表每行表示上船的(传教士数, 野人数) const int actions[][2] { {1, 0}, // 船上只有1个传教士 {2, 0}, // 船上2个传教士 {0, 1}, // 船上只有1个野人 {0, 2}, // 船上2个野人 {1, 1} // 传教士和野人各1个 };为什么不需要“2传教士1野人”因为船最多坐两个人超载了。这个动作表天然排除了超载情况。接下来是状态转移函数给定当前状态和动作计算下一个状态// 从当前状态 cur 执行一个动作成功则写入 next bool moveState(const State cur, int actM, int actC, State next) { State s cur; if (cur.boat 0) { // 船在左岸人从左岸减掉船开到右岸 s.leftM - actM; s.leftC - actC; s.boat 1; } else { // 船在右岸人加到左岸船开回左岸 s.leftM actM; s.leftC actC; s.boat 0; } if (valid(s)) { next s; return true; } return false; }这里的关键是方向判断。boat 等于 0 表示船在左岸动作是“从左边带走人”所以左岸人数减少boat 等于 1 表示船在右岸动作是“从右边带人回来”所以左岸人数增加。船上的临时组合不需要单独检查因为五个动作里唯一可能“传教士和野人同船”的是 {1,1}两边人数相等不违反“野人不能多于传教士”的语义。如果题目规则同时约束船上这个动作表也只需要额外加一次判断即可。有了状态定义、合法性判断和动作表搜索算法的输入输出就齐了。这里顺带说一个建模上的常见误区有人会把左右两岸各用一组变量存然后单独记录船的位置变成四个变量甚至七个变量比如“左M、左C、右M、右C、船位”。这样表示更直白但因为左右岸人数总和恒定属于冗余建模。冗余状态会让 visited 集合变大而且很容易出现同一个实际状态被当成两个不同状态处理导致搜索重复。用三变量建模后编码和去重都会简单很多第 5 章会专门讲状态编码。3. 搜索策略DFS 与 BFS 在同一个图上相遇状态空间模型建好后问题就变成了在一张有向图中找从初始状态到目标状态的一条路径。这张图的节点是合法状态边是五个动作。求解的核心动作是搜索而 DFS 和 BFS 各自的特点在这个小规模问题上体现得非常清楚。3.1 深度优先递归栈里的人工推理DFS 的策略是一条路走到黑走不通再回头。它和人工推理很接近先试着把两个野人送过去不行就换一个组合。用递归实现时系统调用栈天然承担了路径栈的角色只需要额外维护一个 visited 集合防止状态循环。#include vector #include set bool dfs(State cur, vectorState path, setint visited) { // 目标所有人到右岸且船在右岸 if (cur.leftM 0 cur.leftC 0 cur.boat 1) { path.push_back(cur); return true; } // 尝试五个上船动作 for (auto act : actions) { State next; if (moveState(cur, act[0], act[1], next)) { int code next.leftM * 8 next.leftC * 2 next.boat; if (visited.find(code) visited.end()) { visited.insert(code); path.push_back(cur); if (dfs(next, path, visited)) return true; path.pop_back(); } } } return false; }这段代码有几个细节值得说明。visited.insert(code) 发生在递归进入之前而且递归返回失败后不删除这是为了避免同一个状态被重复扩展。在这个问题里同一个状态无论通过哪条路径到达后续可走的动作完全相同所以保留 visited 是安全的。path.push_back(cur) 放在递归调用前表示把当前节点记录进路径找到目标后逐层返回最终 path 里就是从起点到终点的完整路径。如果递归深度过大可以考虑把递归改成显式栈但这个问题最大状态数只有 32递归深度不会超过几十层直接用递归没问题。DFS 找到的第一个解不一定是步数最少的它只保证“存在解”。如果你只是想验证题目有解DFS 够用如果想知道最短需要几步必须换 BFS。3.2 广度优先队列保证最短步数BFS 按层扩展第一次遇到目标状态时的路径一定是最短的。实现上用 queue 保存“当前状态 到当前状态的历史路径”。由于每个节点都要保存一份路径内存开销比 DFS 大但这道题状态空间小完全承受得起。#include queue struct Node { State s; vectorState path; // 从起点到当前节点的路径 }; bool bfs(State start) { queueNode q; setint visited; visited.insert(start.leftM * 8 start.leftC * 2 start.boat); Node startNode; startNode.s start; startNode.path.push_back(start); q.push(startNode); while (!q.empty()) { Node cur q.front(); q.pop(); // 判断目标状态 if (cur.s.leftM 0 cur.s.leftC 0 cur.s.boat 1) { // 输出 cur.path即为最短路径 return true; } for (auto act : actions) { State next; if (moveState(cur.s, act[0], act[1], next)) { int code next.leftM * 8 next.leftC * 2 next.boat; if (visited.insert(code).second) { Node n; n.s next; n.path cur.path; n.path.push_back(next); // 注意这里存的是下一状态 q.push(n); } } } } return false; }注意路径存储的细节cur.path 保存的是到当前状态为止的路径扩展时把下一状态 next 追加到副本里而不是直接 push 到 cur.path否则会污染当前节点的多条出边。BFS 的 visited 在入队时立即标记防止同一状态被多个分支重复入队。如果等出队时再标记队列里会积压大量重复节点虽然结果一样但内存和时间都会明显上涨。3.3 剪枝与去重的边界条件有了合法状态过滤和 visited 去重搜索空间已经很小了但还有两个可以进一步压缩的点。第一个是剪掉“对岸状态非法”的中间状态这已经在 valid 里做了第二个是剪掉船空驶的情况动作表里没有 {0,0}天然排除了船自己移动的可能性。下面用表格对比 DFS 和 BFS 在本问题中的实际表现比较项DFSBFS是否需要 visited需要防止递归死循环需要防止队列膨胀路径长度保证不保证最短第一次找到就是最短空间复杂度O(深度)约几十个状态O(层数)需要保存路径副本实现难度递归简单队列结构稍复杂适合场景只求有解、快速验证求最短步数、教学演示剪枝还有一个常见误区有人会在 visited 之外再加一个“深度上限”超过 20 步就终止。这是不必要的因为状态空间只有 32 个节点合法路径再长也不会无限延伸加深度上限反而可能漏解。遇到搜索异常慢的时候优先检查 visited 插入位置和状态转移方向而不是盲目限深度。4. 从 man.rar 解压到可运行工程VC6 工程文件的含义man.rar 这个名字容易让人联想到 Linux 的 man 命令但这里只是压缩包名字和命令行文档没有关系。解压后你会看到一组 Visual C 6.0 时代的工程文件yeren.c、yeren.opt、yeren.plg、yeren.dsw、yeren.ncb、Debug 目录外加一份《野人与传教士问题.doc》。文件不多但每个后缀背后都有值得解释的用途。4.1 文件清单谁是源码谁是工程元数据文件作用yeren.c实际算法源码核心逻辑都在这里yeren.dspVC6 的工程文件记录源文件列表和编译选项yeren.dsw工作区文件可同时管理多个 dsp 工程yeren.opt编辑器状态如断点、窗口位置可删除yeren.plg编译日志索引可删除yeren.ncb智能感知缓存可删除Debug编译输出目录里面是中间文件和 exe野人与传教士问题.doc问题描述与算法说明文档这里有个容易误导人的地方摘要说它是 C 实现但实际文件名是 yeren.c。在 VC6 里.c 文件会按 C 语言语法编译.cpp 才会启用 C 特性。这个工程本身用的是结构体和函数属于典型的 C 风格但用 C 编译器也能编译因为代码里没有用到与 C 冲突的语法。你可以直接改名成 yeren.cpp或者用现代编译器统一按 C 编译效果一样。4.2 用现代环境替换 VC6 编译运行VC6 是 1998 年的编译器在今天的 Windows 上直接运行经常出现兼容性报错。常见做法是直接用 gcc 或新版 Visual Studio 编译 yeren.c工程文件只当阅读参考。# 用 gcc 编译并运行 gcc yeren.c -o yeren.exe ./yeren.exe # 如果想按 C 方式编译改个后缀或加 -x c 参数 gcc yeren.c -x c -o yeren_cpp.exe ./yeren_cpp.exe如果你的环境里有 Visual Studio也可以打开 yeren.dsw。VS 会自动提示升级工程确认后重新编译即可。编译时留意几个典型问题一是 VC6 允许不声明就用的函数现代编译器会直接报错二是隐式类型转换提示级别更高比如把 int 直接赋给 bool 可能出 warning但不影响结果。Debug 目录里如果有 yeren.exe那是 VC6 当年编译的产物在较新的系统上很可能闪退原因多半是工程配置里用了静态连接 CRT而不是算法本身的问题。4.3 最常踩的坑栈溢出和死循环都来自 visited 漏插我在调试类似工程时见过最多的问题是DFS 递归不设 visited或者 visited 只标记当前路径上的节点导致搜索在几个状态之间无限循环。表现是程序运行后长时间不退出CPU 占满。解决办法是先打印每个入队/递归的状态编码把搜索序列 dump 到文件里很快就能看到循环节。另一个坑是船位的初始值。初始状态所有人都在左岸船也在左岸所以 boat 应该为 0。有人把船位写成 1搜索直接从“船在右岸”开始此时左岸没有人但目标状态也是所有人在右岸程序会误判为一步都不需要走直接输出空路径。验证的办法是打印初始状态和目标状态确认两者不是一个状态。文档《野人与传教士问题.doc》里一般会画状态转移图或者给出一个可行解。如果你运行结果和文档里的步数不一致先检查 BFS 是否真正按层扩展而不是队列写成了栈。把 queue 换成 stack 并不会让程序崩溃只是会得到一个非最短路径这种错误非常隐蔽。5. 状态哈希化把结构体压成 int 的下标访问前面代码里两次出现leftM * 8 leftC * 2 boat这种编码不是随手写的它是这道题最高效的状态去重方式。三个变量的取值范围分别是 0~3、0~3、0~1因此可以按二进制位拼接leftM 占 2 位leftC 占 2 位boat 占 1 位总共 5 位正好覆盖 32 个状态。// 把状态编码为 0~31 的整数 inline int encode(const State s) { return (s.leftM 3) | (s.leftC 1) | s.boat; }用移位写法更贴近位运算风格结果和乘法一样leftM 乘以 8leftC 乘以 2再加 boat。0 到 3 的二进制是 00 到 11左移 3 位后占据编码的高两位leftC 左移 1 位占据中间两位boat 占据最低位。这样每个编码都互不冲突可以用长度为 32 的 bool 数组替代 set。bool visited[32] {false}; int code encode(next); if (!visited[code]) { visited[code] true; // 入队或递归 }bool 数组访问是 O(1) 且没有哈希计算开销比 set 快得多。虽然这道题只有 32 个状态性能差异不明显但这个小技巧可以迁移到任何“状态分量取值范围有限”的搜索题上比如八数码、华容道。甚至你可以用编码直接当数组下标来预计算每个状态的合法性把 valid 调用从搜索循环里移除。验证编码正确性的方法很简单打印所有合法状态的编码检查是否有重复或遗漏。合法状态大约只有 16 个逐一对照左右岸人数与船位就能发现编码公式是否写错。我就是用这个方法查出来一次 leftC 忘记左移导致所有野人人数为奇数的状态全部撞在同一个编码上。本文还有配套的精品资源点击获取