早教吧 育儿知识 作业答案 考试题库 百科 知识分享

一个简单的人工智能题:用问题归约法求解野人与修道士的问题野人与修道士的问题:河的左岸有3个野人和3个修道士以及一条小船,修道士们想用这条小船把所有的人都运到河的右岸,但又受

题目详情
一个简单的人工智能题:用问题归约法求解野人与修道士的问题
野人与修道士的问题:
河的左岸有3个野人和3个修道士以及一条小船,修道士们想用这条小船把所有的人都运到河的右岸,但又受到以下限制:
1、修道士和野人都会划船,但船一次只能载2人;
2、在任何岸边,野人数不能超过修道士数,否则修道士将会被野人吃掉.
假定野人愿意服从任何一种过河的安排,请规划出一种确保修道士安全的过河方案.
注意:用问题归约法来实现!
▼优质解答
答案和解析
问题归约法从目标(要解决的问题)出发,逆向推理,通过一系列变换把初始问题变换为子问题集合和子子问题集合,直至最后归约为一个平凡的本原问题集合.
已知条件1:最后一次乘船的一定是两人.
已知条件2:往与返的组合不能重复,否则没有意义.
已知条件3:左岸人数除最末次外,不为零.
目标0:
右岸有3个野人3个修道士,船在右.
逆向推理:
最后一次乘船到右岸的组合有以下几种:
1个野人1个修道士;2个野人.
目标-1:
a、左岸1野1修,右岸2野2修,船在左;
b、左岸2野,右岸1野3修,船在左.
逆向推理:
a、左岸1野,1修驶向左岸,右岸2野2修;
b、左岸1野,1野驶向左岸,右岸1野3修.
目标-2:
左岸1野,右岸2野3修,船在右.
逆向推理:
c、左岸1野,1修驶向右岸,右岸2野2修;
d、左岸1野,1野驶向右岸,右岸1野3修;
e、左岸1野,2野驶向右岸,右岸3修.
目标-3:
左岸3野,右岸3修,船在左.
逆向推理:
f、左岸1野,2野驶向左岸,右岸3修;
g、左岸2野,1野驶向左岸,右岸3修.
目标-4:
左岸2野,右岸1野3修,船在右.
逆向推理:
h、左岸2野,1野驶向右岸,右岸3修;
i、左岸2野,2修驶向右岸,右岸1野1修.
目标-5:
左岸2野2修,右岸1野1修,船在左.
逆向推理:
j、左岸2野,2修驶向左岸,右岸1野1修;
k、左岸1野1修,1野1修驶向左岸,右岸1野1修.
目标-6:
左岸1野1修,右岸2野2修,船在右.(与目标-5对称)
逆向推理:
l、左岸1野1修,2修驶向右岸,右岸2野.
目标-7:
左岸1野3修,右岸2野,船在左.(与目标-4对称)
逆向推理:
m、左岸3修,1野驶向左岸,右岸2野.
目标-8:
左岸3修,右岸3野,船在右.(与目标-3对称)
逆向推理:
n、左岸3修,2野驶向右岸,右岸1野.
目标-9:
左岸3修2野,右岸1野,船在左.(与目标-2对称)
逆向推理:
左岸3修1野,1野驶向左岸,右岸1野.
目标-10:
左岸3修1野,右岸2野,船在右.
逆向推理:
左岸3修1野,2野驶向右岸,右岸无人.
达到期望的初始状态^^
结论:
1、2野向右:结果左3修1野,右2野,船在右.(目标-10)
2、1野向左:结果左3修2野,右1野,船在左.(目标-9)
3、2野向右:结果左3修,右3野,船在右.(目标-8)
4、1野向左:结果左3修1野,右2野,船在左.(目标-7)
5、2修向右:结果左1修1野,有2修2野,船在右.(目标-6)
6、1修1野向左:结果左2修2野,右1修1野,船在左.(目标-5)
7、2修向右:结果左2野,右3修1野,船在右.(目标-4)
8、1野向左:结果左3野,右3修,船在左.(目标-3)
9、2野向右:结果左1野,右2野3修,船在右.(目标-2)
10、1野向左:结果左2野,右1野3修,船在左.
或1修向左:结果左1野1修,右2野2修,船在左.(目标-1)
11、2野向右,或1修1野向右,达到目的.
看了 一个简单的人工智能题:用问题...的网友还看了以下:

人为什么不能在野外救动物比如说,在野外见到了一个野狗在追一个小鹿,为什么我们不能撵走野狗呢?就像这  2020-06-08 …

课文《变色龙》主要从哪三个方面展示了变色龙的特点一天清早,大雾弥漫,我们正和几个中非工人在紧张地采  2020-06-16 …

一个简单的人工智能题:用问题归约法求解野人与修道士的问题野人与修道士的问题:河的左岸有3个野人和3  2020-06-27 …

设有3个传教士和3个野人,同在河的左岸,他们都要到对岸去,河里只有一条船,他们都会划船,但每次渡船至  2020-11-11 …

为开拓学生视野,激发学生兴趣,提升学生能力,某中学开展了“五个一百工程”鼓励同学们在校期间读一百本名  2020-11-15 …

六年级仿句哦```超难的```嘻嘻``随着雄浑的歌声响彻雪山旷野,有人献出钱财,有人布施铁块,有人送  2020-11-21 …

课文《变色龙》主要从哪三个方面展示了变色龙的特点一天清早,大雾弥漫,我们正和几个中非工人在紧张地采摘  2020-11-27 …

一个砌墙工程造价9900元.由6个瓦工和5个小工来完成,其中瓦工日工资150元.小工每天120元.工  2020-12-01 …

普氏野马重归自然的实验,标志着我国野生动物保护工作已经从单纯的物种异地保护阶段迈向物种回归自然阶段。  2020-12-09 …

师父和徒弟各加工相同数量的零件,师父每小时加工35个,徒弟每小时加工30个,他们同时开始加工,当师父  2020-12-25 …