本文实例讲述了python基于回溯法子集树模板解决野人与传教士问题。分享给大家供大家参考,具体如下:

问题

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

(1)修道士和野人都会划船,但船每次最多只能运M个人;
(2)在任何岸边以及船上,野人数目都不能超过修道士,否则修道士会被野人吃掉。

假定野人会服从任何一种过河安排,请规划出一个确保修道士安全过河的计划。

分析

百度一下,网上全是用左岸的传教士和野人人数以及船的位置这样一个三元组作为状态,进行考虑,千篇一律。

我换了一种考虑,只考虑船的状态。

船的状态:(x, y) x表示船上x个传教士,y表示船上y个野人,其中 |x|∈[0, m], |y|∈[0, m], 0<|x|+|y|<=m, x*y>=0, |x|>=|y|

船从左到右时,x,y取非负数。船从右到左时,x,y取非正数

解的编码:[(x0,y0), (x1,y1), ..., (xp,yp)] 其中x0+x1+...+xp=N, y0+y1+...+yp=N

解的长度不固定,但一定为奇数

开始时左岸(N, N), 右岸(0, 0)。最终时左岸(0, 0), 右岸(N, N)

由于船的合法状态是动态的、二维的。因此,使用一个函数get_states()来专门生成其状态空间,使得主程序更加清晰。

代码

n = 3 # n个传教士、n个野人
m = 2 # 船能载m人
x = [] # 一个解,就是船的一系列状态
X = [] # 一组解
is_found = False # 全局终止标志
# 计算船的合法状态空间(二维)
def get_states(k): # 船准备跑第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 < i+j <= m and (i*j == 0 or i >= j):
yield [(-i,-j), (i,j)][k%2==0] # 生成船的合法状态
# 冲突检测
def conflict(k): # 船开始跑第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 < abs(x[-1][0]) < abs(x[-1][1]) or x[-1] == (0, 0) or abs(sum(x[-1])) > m:
# return True
# 任何时候,左岸传教士人数少于野人
if 0 < n - sum(s[0] for s in x) < n - sum(s[1] for s in x):
return True
# 任何时候,右岸传教士人数少于野人
if 0 < sum(s[0] for s in x) < sum(s[1] for s in x):
return True
return False # 无冲突
# 回溯法
def backtrack(k): # 船准备跑第k趟
global n, m, x, is_found
if is_found: return # 终止所有递归
if n - sum(s[0] for s in x) == 0 and n - sum(s[1] for s in x) == 0: # 左岸人数全为0
print(x)
is_found = True
else:
for state in get_states(k): # 遍历船的合法状态空间
x.append(state)
if not conflict(k):
backtrack(k+1) # 深度优先
x.pop() # 回溯
# 测试
backtrack(0)

效果图

Python基于回溯法子集树模板解决野人与传教士问题示例

解的解释,从上往下看:

Python基于回溯法子集树模板解决野人与传教士问题示例

一个结论

貌似只有满足m = n-1,此问题才有解。

更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

本文开发(python)相关术语:python基础教程 python多线程 web开发工程师 软件开发工程师 软件开发流程

分页:12
转载请注明
本文标题:Python基于回溯法子集树模板解决野人与传教士问题示例
本站链接:http://www.codesec.net/view/565157.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 开发(python) | 评论(0) | 阅读(19)