传教士野人过河问题-两种解法思路(共13页).doc

精选优质文档-倾情为你奉上实验 传教士野人过河问题 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem）。在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。二、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C 为野人人数，B为船数，要求M=C且M+C = 3，L表示左岸，R表示右岸。初始状态目标状态LRLRM30M03C30C03B10B01(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示：（ML , CL , BL）（均为左岸状态）其中,BL