解决传教士与野人问题
程序员文章站
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
推荐阅读
-
vue spa应用中的路由缓存问题与解决方案
-
使用vue-router与v-if实现tab切换遇到的问题及解决方法
-
Hive与Oracle之间利用Sqoop进行数据的导入导出时遇到的问题及解决方法
-
安装Eclipse ADT插件时遇到的问题与解决方法
-
git指令总结及常见问题积累与解决方案
-
Android设备获取扫码枪扫描的内容与可能遇到的问题解决
-
Python2.x中str与unicode相关问题的解决方法
-
ScrollView与ListView合用(正确计算Listview的高度)的问题解决
-
如何解决win10与Ubuntu16.04时间不同步的问题的方法
-
CloudStack SSVM启动条件源码阅读与问题解决方法