传教士-野人问题
有 N 个传教士和 N 个野人要过河，现在有一条船只能承载 K 个人（包括野人），K<N，在
任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。
设 M 为传教士的人数，C 为野人的人数，用状态空间发求解此问题的过程如下：
M、C = N，boat = k，要求 M>=C 且 M+C <= K
初始状态 目标状态
L R L R
M 3 0 M 0 3
C 3 0 C 0 3
B 1 0 B 0 1
(1) 用三元组来表示（ML , CL , BL）
其中 0<=ML , CL <= 3 , BL ∈{ 0 , 1}
(3 , 3 , 1) (0 , 0 , 0)
(2) 规则集合
P10 if ( 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 )
Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )
Q02 if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )
(3) 寻找一个启发式函数引导规则的选用
右岸总人数 6 – ML – CL 两岸中传教士数目>=野人数目
f =
–∞ 其它
