A*算法解决传教士—野人过河问题

2024-09-03 19:58
文章标签 算法 问题 解决 过河 野人 传教士

本文主要是介绍A*算法解决传教士—野人过河问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A*算法解决传教士—野人过河问题

算法原理

1、A算法的基本原理分析；
在或图的一般搜索算法中，如果在搜索过程的步骤⑦利用估价函数f(n)=g(n)+h(n)对open表中的节点进行排序，则该搜索算法为A算法。
g(n)：从初始节点到n的实际代价
因为n为当前节点，搜索已达到n点，所以g(n)可计算出。
h(n)：启发函数，从n到目标节点的最佳路径的估计代价。
因为尚未找到解路径，所以h(n)仅仅是估计值。
对A算法中的g(n)和h(n)做出限制：
g(n) >= g(n)（g*(n)为S0到n的最小费用）
-h(n) <= h*(n)（h*(n)为n到Sg的实际最小费用）
则算法被称为A*算法。

2、传教士—野人过河问题的知识表示方法分析；
在这个问题中，需要考虑：
1、两岸的传教士人数和野人人数 2、船在左岸还是在右岸
已知：传教士和野人数：N（两者默认相同），船的最大容量：K
定义：M：左岸传教士人数 C：左岸野人人数 B：左岸船个数
可用一个三元组来表示左岸状态，即S=(M, C, B)。
约束条件：M>=0,C>=0,B=1或0
已知左岸状态，右岸的状态为：
右岸传教士人数：M’=N-M
右岸野人人数：C’=N-C
右岸船数：B’=1-B
满足同样的约束条件

3、针对传教士—野人过河问题的A算法详细分析
（1）A算法求解传教士和野人过河问题，主要实现过程：
①使用状态空间法将问题的求解抽象为状态空间的搜索。
②根据A算法的思想、A算法的具体步骤、设计估价函数的方法，针对传教士–野人过河问题设计出估价函数f(n)，给出条件约束函数。
（2）估价函数设计：f(n)=g(n)+M+C-K*B

  • h(n)=M+C-K*B把状态转换后左岸剩余人数作为启发性信息

合理性分析：
本问题中，在满足条件约束的前提下，总是希望能使左岸的人数最少。当左岸有船时，应当使船每次都满负荷运载，即运KB人过河。
然而，在最大运载量为K的情况下，状态转换后左岸的剩余人数不可能小于M+C-KB，即从节点n到目标节点的最小代价h*(n)不可能小于h(n) ，因此，满足A算法的条件限制h(n)<=h(n)。
（3）本问题中操作是指用船把传教士或野人从河的左岸运到右岸，或者从河的右岸运到左岸，并且每个操作都应该满足以下3个条件：
①船至少有一个人(M或C)操作，离开岸边的M和C的减少数目等于到达岸边的M和C的增加数目。
②每次操作，船上的人数不得超过K个。
③操作应保证不产生非法状态。

设计思路

1、设计状态空间表示方式
可用一个三元组来表示左岸状态，即S=(M, C, B),将所有扩展的节点和原始节点存放在同一列表中。初始状态为（N,N,1），目标状态为（0,0,0），问题的求解转换为在状态空间中，找到一条从状态(N, N, 1)到状态(0, 0, 0)的最优路径。
例：在3传教士3野人问题中，初始状态为（3,3,1），目标状态为（0,0,0）。
当1野人离开左岸到达右岸后，原状态变为p = [(3,2,0),(3,3,1)],p[0]为当前状态，而列表最后一个为初始状态，只要当p[0] = (0,0,0)则完成搜索。
2、节点拓展方法与合法状态判断
（1）节点拓展：通过减少和增加传教士或野人的数量来拓展节点。
当船在左岸（B=1）：①减少野人 ②减少传教士 ③减少野人和传教士
当船在右岸（B=0）：①增加野人 ②增加传教士 ③增加野人和传教士
（2）合法状态判断
①左岸传教士数量等于总数或左岸传教士为0：C>=0,C<=N
②左岸传教士数量基于0到N之间时: C >=0 , M >= C , M <= N , C <= N , N-M >= N-C
③其他状态为不合法

3、搜索过程
①建立只含有初始节点S的搜索图G，把S放到OPEN表中；
②建立CLOSED表，其初始值为空表；
③若OPEN表是空表，则失败退出；
④选择OPEN表中第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n；
⑤若n为目标节点，则有解并成功退出。
⑥沿指针追踪图G中从n到S这条路径得到解（指针在步骤⑦中设置）；
⑦扩展n，生成不是n的祖先的那些后继节点的集合M，把M的这些成员作为n的后继节点添入图G中；
对M中子节点进行如下处理：
-对没在G中出现过的（即没在OPEN或CLOSED表中出现过的）M成员设置一个指向n的指针，把M的这些成员加进OPEN表；
-已在OPEN或CLOSED表中的每个M成员，确定是否需要更改指向n的指针方向；
-已在CLOSED表中的每个M成员，确定是否需要更改图G中它的每个后裔节点指向父节点的指针。
⑧按某种方式或按某个试探值，重排OPEN表；
⑨转步骤③。

完整代码

def GJ(this,k):#估价函数计算 h(n) = M + C - K * Breturn 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 Falsefor i in closed:if P[0] == i[0]:return Falseopen.append(P)return Trueelse:return Falseelif 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 Falsefor i in closed:if P[0] == i[0]:return Falseopen.append(P)return Trueelse:return Falseelif M == 0:#左岸传教士为0if  C >= 0 and C <= N:P.insert(0, [M, C, 1 - B])for i in open:if P[0] == i[0]:return Falsefor i in closed:if P[0] == i[0]:return Falseopen.append(P)return Trueelse:return Falseelse:return Falseif  __name__ == '__main__':N = int(input("传教士和野人的人数（默认相同）："))K =int(input("船的最大容量："))open = []  #创建open表closed = [] #创建closed表sample = [N,N,1] #初始状态goal = [0,0,0]#目标状态open.append([sample])creatpoint = searchpoint = 0while(1):if sample == goal:print("初始状态为目标状态！")breakif len(open) == 0:print("未搜索到解！")breakelse:this = open.pop(0)closed.append(this)if this[0] == goal:print("搜索成功！")print('共生成节点数：{}，共搜索节点数:{}'.format(creatpoint,searchpoint + 1))print('过河方案如下：')print('      [M, C, B]')for i in this[::-1]:print('---->',i)exit()#扩展节点searchpoint += 1if 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 += 1for i in range(1,K+1):if creat(this,this[0][0],this[0][1]-i,this[0][2],N):creatpoint += 1for 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 += 1else:#船在右岸时for i in range(1,K+1):if creat(this,this[0][0]+i,this[0][1],this[0][2],N):creatpoint += 1for i in range(1,K+1):if creat(this,this[0][0],this[0][1]+ i,this[0][2],N):creatpoint += 1for 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 = xfor y in range(x+1,len(open)):if  GJ(open[x][0],K) >  GJ(open[y][0],K):m = yif m != x:open[x],open[m] = open[m],open[x]

运行结果

参数设置1：N = 3，K =2
初始状态：（3,3，1），目标状态：（0,0,0）
实验结果：
在这里插入图片描述
参数设置2：N = 5，K =3
初始状态：（5,5，1），目标状态：（0,0,0）
实验结果：
在这里插入图片描述
参数设置3：N = 10，K =4
初始状态：（10,10，1），目标状态：（0,0,0）
实验结果：
在这里插入图片描述

这篇关于A*算法解决传教士—野人过河问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1133903。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
如何解决线上平台抽佣高 线下门店客流少的痛点！

如何解决线上平台抽佣高 线下门店客流少的痛点！

目前，许多传统零售店铺正遭遇客源下降的难题。尽管广告推广能带来一定的客流，但其费用昂贵。鉴于此，众多零售商纷纷选择加入像美团、饿了么和抖音这样的大型在线平台，但这些平台的高佣金率导致了利润的大幅缩水。在这样的市场环境下，商家之间的合作网络逐渐成为一种有效的解决方案，通过资源和客户基础的共享，实现共同的利益增长。 以最近在上海兴起的一个跨行业合作平台为例，该平台融合了环保消费积分系统，在短
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2