传教士野人过河问题-两种解法思路 下载本文

实验 传教士野人过河问题

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) 确定状态组,分别列出初始状态集和目标状态集

用三元组来表示Sf:(ML , CL , BL)(均为左岸状态) 其中0?ML?3,0?CL?3,BL ∈{ 0 , 1} S0:(3 , 3 , 1) Sg: (0 , 0 , 0)

初始状态表示全部成员在河的的左岸;

目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合

仍然以河的左岸为基点来考虑,把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数,第二下标j表示船载的食人者数;同理,从右岸将船划回左岸称之为Qij操作,下标的定义同前。则共有10种操作,操作集为

F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20}

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 )

(4) 当状态数量不是很大时,画出合理的状态空间图

图1 状态空间图

箭头旁边所标的数字表示了P或Q操作的下标,即分别表示船载的传教士数和食人者数。

三、算法设计 方法一: 树的遍历

根据规则由根(初始状态)扩展出整颗树,检测每个结点的“可扩展标记”,为“-1”的即目标结点。由目标结点上溯出路径。 见源程序1。

方法二:启发式搜索 构造启发式函数为:

?6.01?ML?CL???满足规则时 f???-???????????????????????????其它选择较大值的结点先扩展。 见源程序2。

四、实验结果

方法一的实验结果: 传教士野人过河问题 第1种方法:

第1次:左岸到右岸,传教士过去1人,野人过去1人 第2次:右岸到左岸,传教士过去1人,野人过去0人 第3次:左岸到右岸,传教士过去0人,野人过去2人 第4次:右岸到左岸,传教士过去0人,野人过去1人 第5次:左岸到右岸,传教士过去2人,野人过去0人 第6次:右岸到左岸,传教士过去1人,野人过去1人 第7次:左岸到右岸,传教士过去2人,野人过去0人 第8次:右岸到左岸,传教士过去0人,野人过去1人 第9次:左岸到右岸,传教士过去0人,野人过去2人 第10次:右岸到左岸,传教士过去0人,野人过去1人 第11次:左岸到右岸,传教士过去0人,野人过去2人

第2种方法:

第1次:左岸到右岸,传教士过去1人,野人过去1人 第2次:右岸到左岸,传教士过去1人,野人过去0人 第3次:左岸到右岸,传教士过去0人,野人过去2人 第4次:右岸到左岸,传教士过去0人,野人过去1人 第5次:左岸到右岸,传教士过去2人,野人过去0人 第6次:右岸到左岸,传教士过去1人,野人过去1人 第7次:左岸到右岸,传教士过去2人,野人过去0人 第8次:右岸到左岸,传教士过去0人,野人过去1人 第9次:左岸到右岸,传教士过去0人,野人过去2人 第10次:右岸到左岸,传教士过去1人,野人过去0人 第11次:左岸到右岸,传教士过去1人,野人过去1人

第3种方法:

第1次:左岸到右岸,传教士过去0人,野人过去2人 第2次:右岸到左岸,传教士过去0人,野人过去1人 第3次:左岸到右岸,传教士过去0人,野人过去2人 第4次:右岸到左岸,传教士过去0人,野人过去1人 第5次:左岸到右岸,传教士过去2人,野人过去0人 第6次:右岸到左岸,传教士过去1人,野人过去1人