有三个和尚（或传教士）和三个妖怪（或食人怪）过河，只有一条能装下两个人（和尚或妖怪）的 船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你 能不能找出一种安全的渡河方法呢？
这是一个很有意思的智力题，但是并不难，每次可以选择 一个人或者两个人过河，只要保证在河的任何一边的和尚数量总是大于或等于妖怪的数量即可。这里 先给出一种过河方法：
两个妖怪先过河，一个妖怪回来；
再两个妖怪过河，一个妖怪 回来；
两个和尚过河，一个妖怪和一个和尚回来；
两个和尚过河，一个妖怪回来；
两个妖怪过河，一个妖怪回来；
两个妖怪过河。
过河的方法其实不止这一种， 本文给出了一种求解全部过河方法的算法程序，可以通过穷举（状态树搜索）的方法得到全部四种过 河方法。
解决问题的思路
题目的初始条件是三个和尚和三个妖怪在河的一边（还有一 条船），解决问题后的终止条件是三个和尚和三个妖怪安全地过到河的对岸，如果把任意时刻妖怪和 和尚的位置看作一个“状态”，则解决问题就是找到一条从初始状态变换到终止状态的路径。从初始 状态开始，每选择一批妖怪或和尚过河（移动一次小船），就会从原状态产生一个新的状态，如果以 人类思维解决这个问题，每次都会选择最佳的妖怪与和尚组合过河，使得它们过河后生成的新状态更 接近最终状态，不断重复上述过程，直到得到最终状态。
用计算机解决妖怪与和尚过河问题的 思路也是通过状态转换，找到一条从初始状态到结束状态的转换路径。计算机不会进行理性分析，不 知道每次如何选择最佳的过河方式，但是计算机擅长快速计算且不知疲劳，既然不知道如何选择过河 方式，那就干脆把所有的过河方式都尝试一遍，找出所有可能的结果，当然也就包括成功过河的结果 。
这个思路其实和《三只水桶等分水问题》的解法类似，从初始状态开始，通过构造特定的穷 举算法，对解空间中的所有状态进行穷举，就得到一棵以初始状态为根的状态树。如果状态树上某个 叶子节点是题目要求的最终状态，则从根节点到此叶子节点之间的所有状态节点就是一个过河问题的 解决过程。
状态的数学模型
本节探讨一下如何建立状态的数学模型。题目要求并不强调三个妖怪之间或三个和尚之间的差异， 只是关注它们在和河两岸的数量，因此无需赋予和尚和妖怪过多的属性，只要用数值分别表示它们在 和两岸的数量即可确定某个时刻的状态。除了和尚与妖怪的数量，还有一个很关键的因素也会影响到 数学模型，那就是船的状态。例如某一时刻，本地河边有两个和尚和两个妖怪，对岸有一个和尚和一 个妖怪，此时船在河这边和在河对岸就分别是两个完全不同的状态。和尚与妖怪的状态就是数值，船 有两个状态，在本地河边（LOCAL）和在对岸（REMOTE），我们用一个五元组来表示某个时刻的过河状 态：[本地和尚数，本地妖怪数， 对岸和尚数，对岸妖怪数，船的位置]。用五元组表示的初始状态就 是[3, 3, 0, 0, LOCAL]，问题解决的过河状态是[0, 0, 3, 3, REMOTE]。用C/C++定义此状态模型如 下：
28 struct ItemState
29 {
30 ......
31 int local_monster;
32 int local_monk;
33 int remote_monster;
34 int remote_monk;
35 BoatLocation boat; /*LOCAL or REMOTE*/
36 ......
37 };
本题的状态空间就是以[3, 3, 0, 0, LOCAL]为根的一棵状态树，如果某个叶子节点表 示的状态是求解状态[0, 0, 3, 3, REMOTE]，则从根节点到此节点之间的直系关系节点，就是过河过 程中的所有中间状态，将这些中间状态按照父子关系依次输出，就是一个求解过程。以本文开始给出 的一个求解过程为例，其状态转换过程如下图所示：
图（1）一个求解的状态转换过程
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索问题
， c语言问题 新手求解
， 节点
， 状态
， 两个
， 数学 二元树算法
， 求解释求解决
， 农夫过河
， 一个
初始
老和尚背女人过河、和尚背女人过河的故事、老和尚和小和尚过河、和尚过河、四个道士四个和尚过河，以便于您获取更多的相关知识。