实验 传教士野人过河问题
37030602 王世婷
一、实验问题
传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。
二、解答步骤
(1) 设置状态变量并确定值域
M为传教士人数，C 为野人人数，B为船数，要求M>=C且M+C <= 3，L表示左岸，R表示右岸。
初始状态 目标状态
L R L R
M 3 0 M 0 3
C 3 0 C 0 3
B 1 0 B 0 1
(2) 确定状态组，分别列出初始状态集和目标状态集
用三元组来表示
：（ML , CL , BL）（均为左岸状态）
其中
,BL ∈{ 0 , 1}
：(3 , 3 , 1)
： (0 , 0 , 0)
初始状态表示全部成员在河的的左岸；
目标状态表示全部成员从河的左岸全部渡河完毕。
(3) 定义并确定规则集合
仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为
