问题:在河的左岸有N个传教士、N个野人和一条船，传教士们想用这条船把所有人都运过河去，但有以下条件限制:

1.传教士和野人都会划船，但船每次最多只能运M个人；

2.在任何岸边以及船上，野人数目都不能超过传教士，否则传教士会被野人吃掉。

假设野人会服从任何一个过河安排，请制定一个确保传教士安全过河的方案。

代码:

n=3     #n个传教士，n个野人
m=2     #船能载m人

x=[]
X=[]

is_found=False      #全局终止标志

#计算船的合法状态空间
def get_states(k):
    global n,m,x
    if k%2==0: #从左到右，只考虑左岸人数
        s1,s2=n-sum(s[0] for s in x),n-sum(s[1] for s in x)
    else:
        s1, s2 = sum(s[0] for s in x), sum(s[1] for s in x)
    for i in range(s1+1):
        for j in range(s2+1):
            if 0=j):
                yield [(-i,-j),(i,j)][k%2==0]  #生成船的合法状态
#冲突检测
def conflict(k):
    global n,m,x
    #若船上载的人与上一趟一样，会进入死循环
    if k>0 and x[-1][0]==-x[-2][0] and x[-1][1]==-x[-2][1]:
        return True
    #任何时候，左岸传教士人数少于野人
    if 0

运行结果:

[(0, 2), (0, -1), (0, 2), (0, -1), (2, 0), (-1, -1), (2, 0), (0, -1), (0, 2), (0, -1), (0, 2)]

说明:船的状态:(x,y),x表示传教士人数，y表示野人人数。

船从左往右时，取非负数；从右往左时，取非正数。

支付宝打赏

微信打赏

传教士   野人   算法

发表评论

留言与评论（共有 0 条评论） “”

验证码：