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

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

时间：2023-02-24 17:03:44

相关推荐

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]