Missionaries and cannibals problem

By Von Neumann

最近爱上了python,作业好多,没时间刷题了。
Missionaries and cannibals problem,also known as jealous husbands problem。
这个问题是一个很经典的AI问题,搜索问题。
问题是,有三个传教士和三个食人族在一条河的左边,有一条能载客两人的船,当食人族的数量超过传教士的时候,传教士就会被吃掉,现在要求如何将传教士和食人族安全的运到对岸。
问题分析:搜索问题一般有以下几个组成部分。
状态空间(state space)
转换方程(successor function)
初始状态(initial state)
目标(goal)
从开始状态开始,依次执行以下步骤:
1.判断当前状态是否为目标状态
2.若当前状态不是目标状态,将当前状态标记为已访问
3.通过转换方程计算出当前状态的有效(是否已访问,传教士是否会被吃掉)后续状态集
4.依次访问后续状态

使用一个五元组来表示当前环境的状态,(canLeft, missLeft, boat, canRight, missRight)依次为(左岸食人族数量,左岸传教士数量,船的位置,右岸食人族数量,右岸传教士数量)
转换方程,首先判断船的位置,如果船在左岸,后续状态为:
(canLeft – 1, missLeft, ‘right’, canRight + 1, missRight)
(canLeft – 2, missLeft, ‘right’, canRight + 2, missRight)
(canLeft – 1, missLeft – 1, ‘right’, canRight + 1, missRight + 1)
(canLeft, missLeft – 1, ‘right’, canRight, missRight + 1)
(canLeft, missLeft – 2, ‘right’, canRight, missRight + 2)

如果船在右岸,后续状态为:
(canLeft + 1, missLeft, ‘left’, canRight – 1, missRight)
(canLeft + 2, missLeft, ‘left’, canRight – 2, missRight)
(canLeft + 1, missLeft + 1, ‘left’, canRight – 1, missRight – 1)
(canLeft, missLeft + 1, ‘left’, canRight, missRight – 1)
(canLeft, missLeft + 2, ‘left’, canRight, missRight – 2)

依次判断这十个状态是否有效 if state not in visited and if state.isValid(),有一种特殊情况,就是目标状态,由于到达目标状态的路径可能有多个,所以要特殊处理if (state not in visited or state.isGoal()) and state.isValid()
将有效的状态添加到后续状态集

代码没怎么注释,但是应该很容易就懂了。

Comments: 0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: