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

2024-03-21 11:31:54

本文实例讲述了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相关内容可查看本站专题：《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

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

Python基于回溯法子集树模板实现8皇后问题

本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''
Python基于回溯法子集树模板解决选排问题示例

本文实例讲述了Python基于回溯法子集树模板解决选排问题.分享给大家供大家参考,具体如下: 问题从n个元素中挑选m个元素进行排列,每个元素最多可重复r次.其中m∈[2,n],r∈[1,m]. 如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次. 分析解x的长度是固定的,为m. 对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1].我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!! 一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做
Python基于回溯法子集树模板解决旅行商问题（TSP）实例

本文实例讲述了Python基于回溯法子集树模板解决旅行商问题(TSP).分享给大家供大家参考,具体如下: 问题旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短? 分析此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小
Python基于回溯法子集树模板解决0-1背包问题实例

本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-
Python使用回溯法子集树模板解决爬楼梯问题示例

本文实例讲述了Python使用回溯法子集树模板解决爬楼梯问题.分享给大家供大家参考,具体如下: 问题某楼梯有n层台阶,每步只能走1级台阶,或2级台阶.从下向上爬楼梯,有多少种爬法? 分析这个问题之前用分治法解决过.但是,这里我要用回溯法子集树模板解决它. 祭出元素-状态空间分析大法:每一步是一个元素,可走的步数[1,2]就是其状态空间.不难看出,元素不固定,状态空间固定. 直接上代码. 代码 '''爬楼梯''' n = 7 # 楼梯阶数 x = [] # 一个解(长度不固定,1-2数组,表示
Python基于回溯法子集树模板解决取物搭配问题实例

本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状
Python基于回溯法子集树模板解决最佳作业调度问题示例

本文实例讲述了Python基于回溯法子集树模板解决最佳作业调度问题.分享给大家供大家参考,具体如下: 问题给定 n 个作业,每一个作业都有两项子任务需要分别在两台机器上完成.每一个作业必须先由机器1 处理,然后由机器2处理. 试设计一个算法找出完成这n个任务的最佳调度,使其机器2完成各作业时间之和达到最小. 分析: 看一个具体的例子: tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 最优调度顺序:1 3 2 处理时间:18 这3个作业的6种可能的调度方案是1,2,3:1
Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题输入第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情
Python基于回溯法子集树模板解决数字组合问题实例

本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.
Python使用回溯法子集树模板解决迷宫问题示例

本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.
Python基于回溯法子集树模板实现图的遍历功能示例

本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能.分享给大家供大家参考,具体如下: 问题一个图: A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径.请找出所有可能的路径. 分析将这个图可视化如下: 本问题涉及到图,那首

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

相关推荐

随机推荐