解决传教士与野人问题

1.初始化问题

用三元组来表示状态[M,C,B]，M：传教士人数，C：野人数，B：船的位置（1表示在左岸，0表示在右岸），假设初始都在左岸。

if __name__ == '__main__':
    N = int(input("传教士和野人的人数（默认相同）："))
    K = int(input("船的最大容量："))
    open = []  # 创建open表
    closed = []  # 创建closed表
    sample = [N, N, 1]  # 初始状态
    goal = [0, 0, 0]  # 目标状态
    open.append([sample])  # 初始状态放入open表
    creatpoint = searchpoint = 0  # 生成节点数和搜索节点数

2.启发函数

用h（n）=M+C-K*B来作为启发函数，每次左岸的总人数尽可能少。

def heuristic(this, k):  # 启发函数计算 h(n) = M + C - K * B
    return this[0] + this[1] - k * this[2]

3.获取后继节点

分为左右两岸两种情况，每种情况又分只过传教士、只过野人、过传教士和野人三种情况，最后用启发函数重新排open表。

			# 扩展节点
            searchpoint += 1
            if this[0][2] == 1:  # 船在左岸时
                for i in range(1, K + 1):  # 只过传教士
                    if creat(this, this[0][0] - i, this[0][1], this[0][2], N):
                        creatpoint += 1
                for i in range(1, K + 1):  # 只过野人
                    if creat(this, this[0][0], this[0][1] - i, this[0][2], N):
                        creatpoint += 1
                for i in range(1, K):  # 过传教士和野人
                    for r in range(1, K - i + 1):
                        if creat(this, this[0][0] - i, this[0][1] - r, this[0][2], N):
                            creatpoint += 1
            else:  # 船在右岸时
                for i in range(1, K + 1):  # 只过传教士
                    if creat(this, this[0][0] + i, this[0][1], this[0][2], N):
                        creatpoint += 1
                for i in range(1, K + 1):  # 只过野人
                    if creat(this, this[0][0], this[0][1] + i, this[0][2], N):
                        creatpoint += 1
                for i in range(1, K):  # 过传教士和野人
                    for r in range(1, K - i + 1):
                        if creat(this, this[0][0] + i, this[0][1] + r, this[0][2], N):
                            creatpoint += 1

            # 启发函数h(n) = M + C - K * B 重排open表
            for x in range(0, len(open) - 1):
                m = x
                for y in range(x + 1, len(open)):
                    if heuristic(open[x][0], K) > heuristic(open[y][0], K):
                        m = y
                if m != x:
                    open[x], open[m] = open[m], open[x]

4.生成节点函数

分为三种情况：左岸传教士数量等于总数、左岸传教士数量基于0到N之间时和左岸传教士为0。又得进行判断，两岸野人数不能大于传教士。

def creat(array, M, C, B, N):  # 判断生成节点是否符合规则、判断是否重复
    P = array[:]
    if M == N:  # 左岸传教士数量等于总数
        if C >= 0 and C <= N:  # 判断野人数量是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    elif M > 0:  # 左岸传教士数量基于0到N之间时
        if C >= 0 and M >= C and M <= N and C <= N and N - M >= N - C:  # 判断左右两岸传教士数和野人数是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    elif M == 0:  # 左岸传教士为0
        if C >= 0 and C <= N:  # 判断野人数量是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    else:
        return False

5.全部代码

def heuristic(this, k):  # 启发函数计算 h(n) = M + C - K * B
    return this[0] + this[1] - k * this[2]


def creat(array, M, C, B, N):  # 判断生成节点是否符合规则、判断是否重复
    P = array[:]
    if M == N:  # 左岸传教士数量等于总数
        if C >= 0 and C <= N:  # 判断野人数量是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    elif M > 0:  # 左岸传教士数量基于0到N之间时
        if C >= 0 and M >= C and M <= N and C <= N and N - M >= N - C:  # 判断左右两岸传教士数和野人数是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    elif M == 0:  # 左岸传教士为0
        if C >= 0 and C <= N:  # 判断野人数量是否合理
            P.insert(0,[M, C, 1 - B])
            for i in open:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            for i in closed:  # 检查是否重复
                if P[0] == i[0]:
                    return False
            open.append(P)  # 加入open表中
            return True
        else:
            return False
    else:
        return False


if __name__ == '__main__':
    N = int(input("传教士和野人的人数（默认相同）："))
    K = int(input("船的最大容量："))
    open = []  # 创建open表
    closed = []  # 创建closed表
    sample = [N, N, 1]  # 初始状态
    goal = [0, 0, 0]  # 目标状态
    open.append([sample])  # 初始状态放入open表
    creatpoint = searchpoint = 0  # 生成节点数和搜索节点数
    # 目标测试
    while (1):
        if sample == goal:
            print("初始状态为目标状态！")
            break
        if len(open) == 0:
            print("未搜索到解！")
            break
        else:
            this = open.pop(0)  # 拿出open表中第一个状态
            closed.append(this)  # 加入closed表中
            if this[0] == goal:
                print("搜索成功！")
                print('共生成节点数：{}，共搜索节点数:{}'.format(creatpoint, searchpoint + 1))
                print('过河方案如下：')
                print('      [M, C, B]')
                for i in this[::-1]:
                    print('---->', i)
                exit()
            # 扩展节点
            searchpoint += 1
            if this[0][2] == 1:  # 船在左岸时
                for i in range(1, K + 1):  # 只过传教士
                    if creat(this, this[0][0] - i, this[0][1], this[0][2], N):
                        creatpoint += 1
                for i in range(1, K + 1):  # 只过野人
                    if creat(this, this[0][0], this[0][1] - i, this[0][2], N):
                        creatpoint += 1
                for i in range(1, K):  # 过传教士和野人
                    for r in range(1, K - i + 1):
                        if creat(this, this[0][0] - i, this[0][1] - r, this[0][2], N):
                            creatpoint += 1
            else:  # 船在右岸时
                for i in range(1, K + 1):  # 只过传教士
                    if creat(this, this[0][0] + i, this[0][1], this[0][2], N):
                        creatpoint += 1
                for i in range(1, K + 1):  # 只过野人
                    if creat(this, this[0][0], this[0][1] + i, this[0][2], N):
                        creatpoint += 1
                for i in range(1, K):  # 过传教士和野人
                    for r in range(1, K - i + 1):
                        if creat(this, this[0][0] + i, this[0][1] + r, this[0][2], N):
                            creatpoint += 1

            # 启发函数h(n) = M + C - K * B 重排open表
            for x in range(0, len(open) - 1):
                m = x
                for y in range(x + 1, len(open)):
                    if heuristic(open[x][0], K) > heuristic(open[y][0], K):
                        m = y
                if m != x:
                    open[x], open[m] = open[m], open[x]

本文地址：https://blog.csdn.net/weixin_45289300/article/details/110291195