一个简单的人工智能题:用问题归约法求解野人与修道士的问题

发布网友 发布时间：2022-05-22 05:22

我来回答

共1个回答

热心网友 时间：2024-03-06 17:34

问题归约法从目标(要解决的问题)出发，逆向推理，通过一系列变换把初始问题变换为子问题集合和子子问题集合，直至最后归约为一个平凡的本原问题集合。

已知条件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野向右，达到目的。