这个问题本来是《人工智能技术导论》第三章的课后题，今天上午考试正巧考到了这道题，要我们画状态转换图，我之前思考过一点，所以写出的状态表示应该没有问题，但这些状态太多了.......,十来种状态直接给我干懵逼了，两个小时的考试，差不多得有一个小时在推导状态转换关系，最后整个考场就剩下我和谭神两个人了，这里写下博客，整理一下这个问题。
网上搜索发现这个博主的做法和我的做法大致一样的，他最后给出了C++的实现方式。这篇博客状态分析部分就主要参考/guanghe/p/5485800.html
后面再附上PROLOG程序的解决方案。
一、问题重述
在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制：
(1)修道士和野人都会划船，但船每次最多只能运K个人；
(2)在任何岸边野人数目都不能超过修道士，否则修道士会被野人吃掉。
假定野人会服从任何一种过河安排，请规划出一个确保修道士安全过河的计划。
二、问题分析
1、约束条件
①M≧C任何时刻两岸、船上都必须满足传教士人数不少于野人数(M=0时除外，既没有传教士)
②M+C≦K船上人数限制在K以内
2、求解
传教士与野人全部安全渡到对岸的解决方案
三、状态表示
设N=3，K=2(三个M和三个C，每次渡河二人以下)
L：左岸，R：右岸，
B：是否有船(0：无船，1：有船)
定义：用三元组(ML，CL，BL)表示左岸状态，其中：
0≦ML,CL≦3，BL∈｛0,1｝
如：(0，3，1)表示左岸有三个野人，船在左岸。
从(3，3，1)到(0，0，0)的状态转换
状态空间：32 种状态，其中：
12种不合理状态：如(1，0，1)说明右岸有2个M，3个C；
4种不可能状态：如(3，3，0)说明所有M和C都在左岸，而船在右岸
∴可用的状态共16种，组成合理的状态空间
状态空间具体描述
四、操作集
定义：Pmc操作：从左岸划向右岸
Qmc操作：从右岸划向左岸
船上人数组合(m，c)共5种(1，0),(1，1),(2，0),(0，1),(0，2)
∵每一种船上的人数组合同时对应P，Q二种操作
∴系统共有5×2＝10种操作(规则)
如：P10：if (ML，CL，BL=1) then (ML-1，CL，BL-1)
如果船在左岸，那么一个传教士划船到右岸
Q01：if (ML，CL，BL=0) then (ML，CL+1，BL+1)
如果船在右岸，那么一个野人划船回到左岸
总共有10种操作
F={P10,P20, P11, P01, P02, Q 10, Q 20, Q 11, Q 01, Q 02}
P10if( ML ,CL , BL=1 )then ( ML–1 , CL , BL–1 )
P01 if( ML ,CL , BL=1 ) then ( ML , CL–1 , BL–1 )
P11 if( ML ,CL , BL=1 ) then ( ML–1 , CL–1 ,BL –1 )
P20 if( ML ,CL , BL=1 ) then ( ML–2 , CL , BL–1 )
P02 if( ML ,CL , BL=1 ) then ( ML , CL–2 , BL–1 )
Q10 if( ML ,CL , BL=0 ) then ( ML+1 , CL ,BL+1 )
Q01 if( ML ,CL , BL=0 ) then ( ML , CL+1 , BL+1 )
Q11 if( ML ,CL , BL=0 ) then ( ML+1 , CL +1,BL +1 )
Q20if( ML ,CL , BL=0 ) then ( ML+2 , CL +2,BL +1 )
Q02 if( ML ,CL , BL=0 ) then ( ML , CL +2, BL+1 )
控制策略
最短路径有4条，由11次操作构成。
(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02)
(P11、Q10、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11)
(P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q01、P02)
(P02、Q01、P02、Q01、P20、Q11、P20、Q01、P02、Q10、P11)
五、状态空间图
状态空间图是一个有向图，图中的节点代表状态，节点之间的连线代表操作，箭头代表状态的转换方向。
六、PROLOG程序设计
% start([3,3,near]).% goal([0,0,far]).
change(near,far).
change(far,near).% boat must be invalid location%valid number of missionaries and cannibals on each shore% no morethan three and no fewer than zero
valid([Missionaries,Cannibals,near]) :-Missionaries=<3,
Cannibals=<3,
Missionaries>=0,
Cannibals>=0.
valid([Missionaries,Cannibals,far]) :-Missionaries=<3,
Cannibals=<3,
Missionaries>=0,
Cannibals>=0.%oneEq(X,X,_).%oneEq(X,_,X).% no missionaries are indanger of being eaten
safe([Missionaries,Cannibals,_]) :-
% oneEq(3,3,_),oneEq(2,2,_),oneEq(1,1,_),oneEq(0,0,_),oneEq(0,1,_),oneEq(0,2,_),oneEq(0,3,_),oneEq(3,0,_),oneEq(3,1,_),oneEq(3,2,_).% (Missionaries=
(Missionaries>=Cannibals ; Missionaries=0),
FarMis is3 - Missionaries, FarCan is 3 -Cannibals,
(FarMis>= FarCan; FarMis=0).%onemissionary
move([M1,C1,B1],onemissionary,[M2,C2,B2]) :-change(B1, B2),
C1=C2,
(B1=near -> DM is M1-1 ; DM is M1+1),
M2=DM.%twomissionaries
move([Missionaries1,Cannibals1,Boat1],twomissionaries,[Missionaries2,Cannibals2,Boat2]) :-change(Boat1,Boat2),
Cannibals1=Cannibals2,
(Boat1=near -> DummyMissionary is Missionaries1-2 ; DummyMissionary is Missionaries1+2),
Missionaries2=DummyMissionary.%onecannibal
move([Missionaries1,Cannibals1,Boat1],onecannibal,[Missionaries2,Cannibals2,Boat2]) :-
% boat1==near,boat2==far,Cannibals2 is Cannibals1 - 1;% boat1==far,boat2==near,Cannibals2 is Cannibals1 + 1.
change(Boat1,Boat2),
Missionaries1=Missionaries2,
(Boat1=near -> DummyCannibal is Cannibals1-1 ; DummyCannibal is Cannibals1+1),
Cannibals2=DummyCannibal.%twocannibal
move([Missionaries1,Cannibals1,Boat1],twocannibals,[Missionaries2,Cannibals2,Boat2]) :-change(Boat1, Boat2),
Missionaries1=Missionaries2,
(Boat1=near -> DummyCannibal is Cannibals1-2 ; DummyCannibal is Cannibals1+2),
Cannibals2=DummyCannibal.%oneofeach
move([Missionaries1,Cannibals1,Boat1],oneofeach,[Missionaries2,Cannibals2,Boat2]) :-change(Boat1,Boat2),
(Boat1=near -> DummyCannibal is Cannibals1-1, DummyMissionary is Missionaries1-1 ; DummyCannibal is Cannibals1+1, DummyMissionary is Missionaries1+1),
Cannibals2=DummyCannibal,
Missionaries2=DummyMissionary.
solution([0,0,far],[]).
solution(State,[Move|Rest]) :-move(State,Move,NextState),
valid(NextState),
safe(NextState),
solution(NextState,Rest).
solve(X) :-length(X,11),
solution([3,3,near],X).
如果觉得《野人与传教士过河java_传教士和野人过河（经典MC问题）》对你有帮助，请点赞、收藏，并留下你的观点哦！
