赞
踩
实验目的
实验内容
状态空间表示法是一种基于图的表示方法。一个表示问题的全部可能的状态及其相互关系构成的图。表示为<Qs,F,Qg>
其中Qs为初始状态的集合、F为操作的集合、Qg为目标状态的集合
问题的解:
关于M-C问题,即是missionaries and cannibals问题。题目条件是N个传教士和N个野人(N=5)准备渡河。河岸边有一条船每次最多载K人(K=3)渡河;限制条件是河的左右两岸或者船上的传教士人数均要大于或者等于野人数目(防止传教士被吃掉,所以人多打架力量大)。
初始有两种情况讨论:1.船在左岸;2.船在右岸;
待用条件:M(传教士人数),C(野人数);B=0(船在右岸),B=1(船在左岸)
1.船在左岸。因为船每次最多运送3人,所以按照最多运送的人数目进行。当船载3人(划船的1人,乘客2人)从左岸出发到右岸,送下2名乘客后,划船的人将船再次驶向左岸接剩下的3人(5-2);所以实际上这一次只运送过去了2人。 此时船从左岸出发又回到左岸,为一个来回即是2次;
由此可得一个式子:((M+C-3)/2)2+1;
*分析:M+C-3:出去最后一次之前,岸边剩下的3个人。(M+C-3)/2: “/2"的原因是每一个来回可以 运行2个人;”*2"是因为一个来回为2次渡河。“+1”是代表着最后一次渡河;
2.船在右岸。
岸边的状态可以用来表示(M,C,B); B=1代表着船在左岸,B=0代表着船在右岸;
船在右岸的时候是需要一个人将船驶往左岸的,所以此刻存在两种可能性,划船的人是野人或者传教士。此刻可以用状态的来表示(M+1,C,1),(M,C+1,1)。左岸原有M个传教士,C个野人。(M+C+1)-2+1 。其中(M+C+1)的”+1”表示送船回到左岸的那个人,而最后边的”+1”,表示送船到左岸时的一次摆渡。
综上所述:M+C-2B满足A*算法的限制条件
图例:
其中:
其中每个stuct有(M,C,B,g,h,f)
分别表示:M传教士人数
C野人数
B在左侧-0,在右侧-1
g当前结点所在解空间树深度
h到目标节点的距离
f 启发函数值
这个示例模拟了(5,5,1,0,10,10)M-C问题的求解。
如下为(5, 4, 1, 0, 10, 10)的解:
操作系统:Window10 专业版
Visual Studio 2019 community
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。