欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

解决传教士与野人问题

程序员文章站 2022-03-14 21:20:52
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] # 初始状态...

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

相关标签: 笔记