过河问题
那么4个商人4个随从呢?.......N个商人N个随从又怎样解决呢?
最新回答
花开不败才是姿态
2024-11-06 08:57:25
野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
初始状态：甲岸，3野人，3牧师；
乙岸，0野人，0牧师；
船停在甲岸，船上有0个人；
目标状态：甲岸，0野人，0牧师；
乙岸，3野人，3牧师；
船停在乙岸，船上有0个人；
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：
渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师
算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。
搜索中采用的一些规则如下：
1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；
乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；
2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；
4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。
5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。
只影
2024-11-06 02:15:59
方案2:他可以先带兔子过河，然后空手回来。第二步，带白菜到对岸，再把兔子带回来。第三步，把小狗带过河，然后空手回来把兔子带到对岸。
纠结小青春丶
2024-11-06 03:19:38
地主划船回来下船，再让另两个奴隶过河去，（这样对岸就有三个奴隶，这边就是三个地主）
然后让一个奴隶回来下船，让两个地主过河去，（这样对岸有两个奴隶和两个地主子）
然后让一个地主和一个奴隶回来，
然后让
奴隶下船，两个地主上船到对岸去，（这时对岸有三个地主一个奴隶）
然后让一个奴隶回来接一个奴隶上船到对岸去，（这时对岸有三个地主两个奴隶）
然后一个奴隶回来接最后一个奴隶过河去，这样对岸有三个奴隶三个地主
你好调皮
2024-11-06 00:40:03
1.一个道士一个魔鬼过河，放下魔鬼，道士驾船回来。
2.两个魔鬼过河，放下其中一个魔鬼，另一个魔鬼驾船回来。
3.两个道士过河，放下一个道士，再让一个魔鬼和一个道士一起回来。
4.两个道士一起过河，将两个道士都放下，由一只魔鬼驾船回来。（完成后，岸得一边有一只魔鬼一个道士，另一边有两个道士两只魔鬼）
5.让两个道士过河，有那一只魔鬼驾船回去。
6.两只魔鬼过河，然后放下一只，另一只驾船回去。
7.两只魔鬼过河，最后两只魔鬼都放下，过关！！
繁花晕染
2024-11-06 04:21:29
2，2从过河，1回，
3，2商过河，1商1从回，
4，2商过河，从回，
5，2从过河，
6，再回，接最后一个随从过河。
热门标签
