SY0903620 赵磊
一、实验题目
请用A*算法实现传教士和野人问题
问题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？
算法设计要求给出：状态表示，规则库，启发函数等
二、实验目的
通过具体问题的编程求解，利用A*算法解决此经典问题，了解人工智能的启发式搜索算法的基本过程与原理。
三、设计思想
1、编程工具
采用C++语言在Visual Studio 6.0环境下编写；
2、整体思想
(1)把初始结点So放入OPEN 表中，计算f(So)。
(2)如果OPEN为空，则搜索失败，退出。
(4)考察节点n是否为目标节点。若是，则求得问题的解，退出。
(5)若节点n不可扩展，则转第(2)步。
3、具体说明
用A*算法求解传教士与野人问题。M=C=5, K=3。节点估价值设为f(n)=h(n)+g(n)，g(n)设为节点搜索深度，而h(n) = m(n) + c(n) - 2b(n),其中m：河左岸的传教士人数；c：河左岸的野人人数；b：船是否在左岸，1：表示在左岸，0：表示不在左岸。
采用结构体定义形式，定义状态节点*NewNode(int m, int c, int b)，其中包含m左岸传教士人数、c左岸野人人数、b船状态（左或右）。开始状态为（3，3，1），目标状态为（0，0，0）。
若需要条件满足，即任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉，要对状态结点的安全性进行判断，判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的。即判断：
if (pNode->m < 0 ||
pNode->c < 0 ||
pNode->m > M ||
pNode->c > M) return 0;
if (pNode->m == M ||
pNode->m == 0) return 1;
要扩展节点n生成其全部后继节点. 对于n的每一个后继节点m配置指向父节点的指针时：
a)计算f(m)
b)如果m既不在OPEN表中, 也不在CLOSED表中, 则用估价函数f把它添入OPEN表. 从m加一指向父辈节点n的指针。
c)如果m已在OPEN表或CLOSED表上, 则比较刚刚对m计算过的值f和前面计算过的该节点在表中的f值. 如果新的f值较小, 则
I.以此新值取代旧值
II.从m指向n, 而不是指向它的父辈节点
III. 如果节点m在CLOSED表中, 则把它移回OPEN表
四、具体函数功能
1)
int Equal(struct NODE *pNode1, struct NODE *pNode2)
功能：判断两个节点所表示的状态是否相等
入口参数：
pNode1：指向节点1的指针
pNode2：指向节点2的指针
返回值：当两个节点所表示的状态相等时，返回1，否则返回左岸右岸0
2)
struct NODE *NewNode(int m, int c, int b)
入口参数：
m：河左岸的传教士人数
c：河左岸的野人人数
b：船是否在左岸，1：表示在左岸，0：表示不在左岸
返回值：指向新产生的节点的指针，或者空间不够时，返回NULL
3)
void FreeList(struct NODE *pList)
功能：释放动态产生的链表
入口参数：
pList：指向OPEN表或者CLOSED表的指针
返回值：无
4)
struct NODE *In(struct NODE *pNode, struct NODE *pList)
功能：判断一个节点是否在一个链表中
入口参数：
pNode：指向给定节点的指针
pList：指向给点链表的指针
返回值：当pNode在pList中时，返回以pNode为首的链表
的后一部分；否则返回NULL
5)
struct NODE *Del(struct NODE *pNode, struct NODE *pList)
功能：从链表pList中删除节点pNode
入口参数：
pNode：指向给定节点的指针
pList：指向给定的链表
返回值：删除给定节点后的链表
6)
struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)
功能：将一个节点按照f值（从小到大）插入到OPEN表中
入口参数：
pNode: 指向给定节点的指针
pOpen：指向OPEN表的指针
返回值：指向插入给定节点后OPEN表的指针
注意：同一个节点（具有相同指针的一个节点），只能向表中添加一次，否则可能会造成循环链表
7)
struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)
功能：将一个节点插入到CLOSED表中
入口参数：
pNode: 指向给定节点的指针
pClosed：指向CLOSED表的指针
返回值：指向插入给定节点后CLOSED表的指针
注意：同一个节点（具有相同指针的一个节点），只能向表中添加一次，否则可能会造成循环链表
8)
void PrintList(struct NODE *pList)
功能：在屏幕上打印一个链表，用于调试程序
入口参数：
pList：指向链表的指针
返回值：无
9)
void PrintNode(struct NODE *pNode)
功能：在屏幕上打印一个节点，用于调试程序
入口参数：
pNode：指向节点的指针
返回值：无
10)
void PrintPath(struct NODE *pGoal)
功能：在屏幕上打印解路径。在搜索过程中，每个节点指向其父节点，从目标节点开始，逆向打印各节点，既得到解路径
入口参数：
pGoal：指向求解得到的目标节点
返回值：无
11)
int IsGrandFather(struct NODE *pNode, struct NODE *pFather)
功能：判断一个节点是否与自己的祖父节点所表示的状态一样
入口参数：
pNode：指向给定节点的指针
pFather：指向给定节点的父节点的指针
返回值：当给定节点所表示的状态与自己的祖父一样时，返回1，否则返回0
12)
int IsGoal(struct NODE *pNode)
功能：判断给定节点是否为目标节点
入口参数：
pNode：指向给定节点的指针
返回值：当给定节点是目标节点时，返回1，否则返回0
13)
int Safe(struct NODE *pNode)
功能：判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的
入口参数：
pNode：指向给定节点的指针
返回值：当给定节点安全时，返回1，否则返回0
14)
int H_Function(struct NODE *pNode)
发布评论