野人传教士过河问题

一、对N＝5、k≤3时，求解传教士和野人问题的产生式系统各组成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态和目标条件的描述），并画出状态空间图。 答： 用M表示传教士，C表示野人，B表示船，L表示左岸，R表示右岸。 初始状态：

M C B 目标状态：

M C B L 0 0 0 R 5 5 5 L 5 5 1 R 0 0 0 1，综合数据库 定义三元组：（M,C,B）

其中：0=

Bl属于集合(0,1)，Bl=1，表示船在左岸，Bl=0，表示船在右岸。 2，规则集

规则集可以用两种方式表示，两种方法均可。

按每次渡河的人数分别写出每一个规则，共(3 0)、(0 3)、(2 1)、(1 1)、(1 0)、(0 1)、(2 0)、(0 2)八种渡河的可能（其中(x y)表示x个传教士和y个野人上船渡河），因此共有16个规则（从左岸到右岸、右岸到左岸各八个）。注意：这里没有(1 2)，因为该组合在船上的传教士人数少于野人人数。 规则集如下：

IF (Ml, Cl, 1) THEN (Ml -3, Cl, 0) p30 IF (Ml, Cl, 1) THEN (Ml, Cl -3, 0) p03 IF (Ml, Cl, 1) THEN (Ml -2, Cl -1, 0) p21 IF (Ml, Cl, 1) THEN (Ml -1, Cl -1, 0) p11 IF (Ml, Cl, 1) THEN (Ml -1, Cl, 0) p10 IF (Ml, Cl, 1) THEN (Ml, Cl -1, 0) p01 IF (Ml, Cl, 1) THEN (Ml -2, Cl, 0) p20 IF (Ml, Cl, 1) THEN (Ml, Cl -2, 0) p02 IF (Ml , Cl, 0) THEN (Ml +3, Cl, 1) q30 IF (Ml, Cl, 0) THEN (Ml, Cl +3, 1) q03 IF (Ml, Cl, 0) THEN (Ml +2, Cl +1, 1) q21 IF (Ml, Cl, 0) THEN (Ml +1, Cl +1, 1) q11 IF (Ml, Cl, 0) THEN (Ml +1, Cl, 1) q10 IF (Ml, Cl, 0) THEN (Ml, Cl +1, 1) q01 IF (Ml, Cl, 0) THEN (Ml +2, Cl, 1) q20 IF (Ml, Cl, 0) THEN (Ml, Cl +2, 1) q02

第二种方法： 将规则集综合在一起，简化表示。规则集如下：

r1：IF (Ml, Cl, 1) and 0< i+j〈=3 and (i>= j or i=0) THEN (Ml -i, Cl -j, 0) r2：IF (Ml, Cl, 0) and 0< i+j〈=3 and (i>= j or i=0) THEN (Ml +i, Cl +j, 1)

3，状态空间图 （5，5，1） p01 （5，4，0） p02 （5，3，0） q02 q01 （5，4，1） P21 p03 （3，3，0） q11 （4，4，1） p03 P11 （5，2，0） q01 q10 （4，4，0） （5，3，1） P20 p03 （5，0，0） q02 q01 （5，1，1） （5，1，0） q01 （5，2，1） P30 （2，2，0） q11 （3，3，1） P30 （0，3，0） q01 （0，4，1） P02 （0，2，0） q01 （0，3，1） P03 （0，0，0） P02 P03 （0，1，0） q01 （0，2，1）

本文来源：https://www.bwwdw.com/article/gr5v.html