基于C++实现的状态空间的启发式搜索

实验题目：实现状态空间的启发式搜索

1. 实验目的

   • 理解启发式搜索的概念
   • 掌握状态空间搜索技术

2. 实验内容

   • 使用线程实现M-C问题的搜索

状态空间表示法

状态空间表示法是一种基于图的表示方法。一个表示问题的全部可能的状态及其相互关系构成的图。表示为<Qs,F,Qg>

其中Qs为初始状态的集合、F为操作的集合、Qg为目标状态的集合

问题的解：

• 问题的求解过程：在图中寻找出从初始状态Qs出发，到达目标状态Qg的路径，寻找操作序列a
• 问题的解：
  • 从初始状态到目标状态的路径
  • 本质上为一个操作序列，在这个操作序列的作用下，问题的状态从初始状态能够变化到目标状态
  • 解
    • Qs某个初始状态，Qg某个目标状态
    • a为操作序列a1,a2,a3……

启发式搜索

• 定义：在搜索的过程中，应用问题解的有关知识，动态地确定操作规则，优先地扩展最有希望的节点，使搜索更快地朝着目标前进
• 特点：扩展的节点少，效率高
• 知识：解在某条路径上出现的频率；当前节点与目标节点差等
• 搜索的有效性取决于启发式信息的有效性
• 启发式信息的应用：做成启发式函数，将知识写进函数，用于评论节点的”希望性“

M-C问题

关于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*算法的限制条件

图例：

其中：
1

• 用m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸 的船数，用三元组（m,c,b）表示问题的状态。
• 对A*算法，首先需要确定评估函数。设 g(n)=d(n),h(n)=m+c-2b,则有
• f(n)=g(n)+h(n)=d(n)+m+c-2b
• 其中，d(n)为节点的深度。通过分析可知h (n)<= h*(n),满足 A*算法的限制条件。

其中每个stuct有（M,C,B,g,h,f）

分别表示：M传教士人数

			  C野人数

			  B在左侧-0，在右侧-1

			  g当前结点所在解空间树深度

			  h到目标节点的距离

			  f 启发函数值
1
2
3
4
5
6
7
8
9

这个示例模拟了（5,5,1,0,10,10）M-C问题的求解。

如下为（5, 4, 1, 0, 10, 10）的解：

环境

操作系统：Window10 专业版

			  Visual Studio 2019 community
1