Python基于回溯法子集树模板解决野人与传教士问题示例
作者:罗兵 时间:2023-07-14 04:36:05
本文实例讲述了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)
效果图
解的解释,从上往下看:
一个结论
貌似只有满足m = n-1
,此问题才有解。
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/7076172.html
标签:Python,回溯法
0
投稿
猜你喜欢
如何使用python生成大量数据写入es数据库并查询操作
2024-01-22 18:00:55
解决golang 关于全局变量的坑
2024-02-17 05:46:02
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
2022-05-05 07:34:53
Python数据类型最全知识总结
2022-01-13 14:18:48
sql索引失效的情况以及超详细解决方法
2024-01-21 09:25:30
Python实战项目之MySQL tkinter pyinstaller实现学生管理系统
2024-01-15 16:21:25
PHP实现异步定时多任务消息推送
2023-05-25 09:51:29
基于Python获取城市近7天天气预报
2023-04-02 08:59:35
mysql left join的基本用法以及on与where的区别
2024-01-19 23:08:44
python+mysql实现简单的web程序
2024-01-15 12:31:58
Python类的用法实例浅析
2023-07-31 11:17:18
js 客户端打印html 并且去掉页眉、页脚的实例
2024-04-22 22:24:26
SQL注入防御:用三种策略应对SQL注入攻击
2008-12-15 16:31:00
Python安装使用命令行交互模块pexpect的基础教程
2023-07-09 22:43:40
python3爬取各类天气信息
2022-01-18 06:09:35
window环境下使用VScode连接虚拟机MySQL方法
2024-01-21 04:42:06
Python socket实现的文件下载器功能示例
2021-03-12 22:43:19
pycharm运行scrapy过程图解
2022-07-19 19:30:20
PHP比你想象的好得多
2023-11-20 09:33:30
YiiFramework入门知识点总结(图文教程)
2023-11-20 18:41:03