三个传教士和三个妖怪过河问题的完整解析与求解

三个传教士和三个妖怪过河问题的完整解析与求解

引用

CSDN

1.

https://m.blog.csdn.net/auto_yiersan/article/details/143581856

三个传教士和三个妖怪需要过河，但只有一条能容纳两个人的船。在任何情况下，如果妖怪的数量超过传教士，传教士就会有危险。如何安排过河顺序，才能确保所有人都安全过河？这是一个经典的逻辑思维题，通过建立多步决策模型和状态转移律，可以找到所有可行的解决方案。

问题描述

三个传教士和三个妖怪需要过河，只有一条能容纳两个人（传教士或妖怪）的船。在河的任何一方或者船上，如果妖怪的数量超过传教士，那么传教士就会有危险。如何安排过河顺序，才能确保所有人都安全过河？

问题建模和求解

① 问题分析

Ⅰ. 问题要求在传教士没有危险的条件下六个人全部过河，我们将河岸简记为左岸与右岸，即初始状态为所有人与船都在左岸，而终止状态为所有人与船都在右岸。

Ⅱ. 针对问题描述，我们可以总结以下约束条件：

• 左岸与右岸的妖怪人数≤传教士人数
• 因为必须有人要操控船只，因此船上人数∈[1,2]

Ⅲ. 我们还可以总结出船上应存在的五种状态，我们定义传教士为0，妖怪为1的话应存在(0),(1),(0,1),(1,1),(0,0)这五种状态。

综上所述，我们只要在满足Ⅱ条件的情况下，穷举Ⅲ的状态转移过程，最后列出穷举过程能得到Ⅰ中终止状态的结果即可解决问题。

② 问题建模

据问题分析我们可以看到，我们在为了获得终止状态，从初始状态开始不断进行决策，确定渡河策略，在满足约束条件的情况下进行下一步求解，因此我们具以上分析将问题归结为一个多步决策模型：

记第k次渡河前此岸的传教士数为

，妖怪数为
,其中
,将二维向量
定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S：
(1)
可以看到S集合包含的状态都是安全状态。

记第k次渡船上的传教士数为
，随从数为
，将二维向量
定义为决策，允许决策集合记作D，由小船容量可得
(2)
因为k为奇数时船从左岸驶向右岸，k为偶数时船从右岸驶向左岸，所以状态
随决策
变换的规律为
(3)
我们将(3)式称为状态转移律，综上所述可得安全渡河的多步决策模型：
求决策
,使状态
按照转移律(3),由初始状态
经过有限步n到达状态

③ 问题求解

根据(1) ~ (3)式通过编程进行求解，算法流程图见图1：

图1 渡河问题算法流程图

流程图的计算过程基本与我们建立的多步决策过程一致，且图中可以看出因为每一步的渡河策略不同但状态转移过程是一致的，因此我们使用递归的方式对问题进行求解。此外，在求解过程中为了防止状态出现重复与左右岸人数超过题目要求，我们通过判断语句对其进行了限制，具体求解程序见附录一。

结果与结论

① 结果

问题求解结果见表1，共有四种渡河策略，表中各行数组代表：[左岸传教士, 左岸妖怪, 右岸传教士, 右岸妖怪, 船的状态]。

表1 求解结果表

② 结论

针对渡河问题，我们先建立了多步决策模型，再通过状态树搜索算法将渡河过程的所有可能解列出，通过题目给出的约束条件对解空间树进行搜索，最终获得了四种可行的渡河策略。

以上求解过程的解空间树见图2：

图2 渡河问题的解空间树

从图2中我们可以看出每一次的渡河策略都会给解空间树增加新的状态，在搜索过程中通过约束条件进行选择，最终我们对获得的最终状态再进行筛选，从而获得满足题目要求的四种可行解。

此外，从表1中我们也可以看到我们得到的四种解中间部分的渡河策略基本一致，这一点也许可以成为算法进一步化简的方法。

附录一：源程序

#!/usr/bin/python
# -*- coding: UTF-8 -*-
class river:
    list_out = []  # 放输出的列表
    # 对状态的编码为：
    # [左岸传教士, 左岸妖怪, 右岸传教士, 右岸妖怪, 船的状态] 船的状态： 1为在左岸 0为在右岸
    # 即初始状态为 [3, 3, 0, 0, 1]
    # 结束状态为 [[0, 0, 3, 3, 0]
    def __init__(self, list_bank: list, list_father: list):
        # 初始化函数
        # 输入 （当前的状态， 上一个状态的状态变化记录）
        # 当 当前的状态为结束状态时（[0, 0, 3, 3, 0]） 输出 记录列表 到 输出列表
        self.list_record = []  # 记录状态的变化的列表
        self.list_record.extend(list_father)
        self.list_record.append(list_bank)
        # 成功状态输出
        if self.list_record[-1] in [[0, 0, 3, 3, 0], ]:
            self.list_out.append(self.list_record)  # 把完成的加入 输出列表 里
    def ship_move(list_bank, list_ship):  # 状态的变化 即船的移动
        list_result = [0, 0, 0, 0, 0] #状态变换的结果
        for i in range(len(list_bank)):
            list_result[i] = list_bank[i]+((-1)**(list_bank[4]))*list_ship[i]
        return list_result
    def check_eat(list_bank):  # 判断妖怪会不会吃人
        return list_bank[0] >= list_bank[1] and list_bank[2] >= list_bank[3] or (list_bank[1] >= 0 and list_bank[0] == 0) or (list_bank[3] >= 0 and list_bank[2] == 0)
    def check_num(list_bank):  # 判断 妖怪和传教士的人数是否 在 0-3 间
        return list_bank[0] >= 0 and list_bank[0] <= 3 and list_bank[1] >= 0 and list_bank[1] <= 3 and list_bank[2] >= 0 and list_bank[2] <= 3 and list_bank[3] >=0 and list_bank[3] <= 3 
    def across_river(self, list_ship):  # 过河函数
        for ship in list_ship:
            new_list_bank = river.ship_move(self.list_record[-1], ship)#list_record[-1]表示最新状态(最后一个值)
            if (not (new_list_bank in self.list_record)) and river.check_eat(new_list_bank) and river.check_num(new_list_bank):
                # not (new_list_bank in self.list_record) 为防止状态变化出现重复
                son = river(new_list_bank, self.list_record)# 树的分支
                son.across_river(list_ship)# 递归调用
list_ship = [
        [0, 1, 0, -1, 1], 
        [1, 0, -1, 0, 1], 
        [0, 2, 0, -2, 1], 
        [2, 0, -2, 0, 1], 
        [1, 1, -1, -1, 1]]
bank = [3, 3, 0, 0, 1] 
a = river(bank, [])
a.across_river(list_ship)
# print(a.list_out)
for i in range(len(a.list_out)):
    # print(list_out[i])
    for k in a.list_out[i]:
        print(k)
    print('\n')