没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
野人过河问题算法分析
野人过河问题属于人工智能学科中的一个经典问题,问题描述如下: 有三
个牧师(也有的翻译为传教士)和三个野人过河,只有一条能装下两个人的船,
在河的任何一方或者船上,如果野人的人数大于牧师的人数,那么牧师就会有
危险. 你能不能找出一种安全的渡河方法呢?
一、算法分析
先来看看问题的初始状态和目标状态,假设和分为甲岸和乙岸:
初始状态:甲岸,3 野人,3 牧师;
乙岸,0 野人,0 牧师;
船停在甲岸,船上有 0 个人;
目标状态:甲岸,0 野人,0 牧师;
乙岸,3 野人,3 牧师;
船停在乙岸,船上有 0 个人;
整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。
问题状态的改变是通过划船渡河来引发的,所以合理的渡河操作就成了通常所
说的算符,根据题目要求,可以得出以下 5 个算符(按照渡船方向的不同,也
可以理解为 10 个算符):
渡 1 野人、渡 1 牧师、渡 1 野人 1 牧师、渡 2 野人、渡 2 牧师
算符知道以后,剩下的核心问题就是搜索方法了,本文采用深度优先搜索,
通过一个 FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作,如
果没有找到则返回其父节点,看看是否有其它兄弟节点可以扩展,然后用
Process(…)函数递规调用 FindNext(…),一级一级的向后扩展。
搜索中采用的一些规则如下:
1、渡船优先规则:甲岸一次运走的人越多越好(即甲岸运多人优先),同
时野人优先运走;
乙岸一次运走的人越少越好(即乙岸运少人优先),
同时牧师优先运走;
2、不能重复上次渡船操作(通过链表中前一操作比较),避免进入死循环;
3、任何时候河两边的野人和牧师数均分别大于等于 0 且小于等于 3;
4、由于只是找出最优解,所以当找到某一算符(当前最优先的)满足操作
条件后,不再搜索其兄弟节点,而是直接载入链表。
5、若扩展某节点 a 的时候,没有找到合适的子节点,则从链表中返回节点
a 的父节点 b,从上次已经选择了的算符之后的算符中找最优先的算符继续扩
展 b。
二、基本数据结构
仔细阅读问题,可以发现有些基本东西我们必须把握,例如:每时刻河两
岸野人牧师各自的数目、船的状态、整个问题状态。所以我们定义如下几个数
据结构:
typedef struct _riverside // 岸边状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}RIVERSIDE;
typedef struct _boat // 船的状态类型
{
int wildMan; // 野人数
int churchMan; // 牧师数
}BOAT;
typedef struct _question // 整个问题状态
{
RIVERSIDE riverSide1; // 甲岸
RIVERSIDE riverSide2; // 乙岸
int side; // 船的位置, 甲岸为-1, 乙岸为 1
BOAT boat; // 船的状态
_question* pPrev; // 指向前一渡船操作
_question* pNext; // 指向后一渡船操作
}QUESTION;
用 QUESTION 来声明一个最基本的链表。
三、程序流程及具体设计
本文只找出了最优解,据我所知,本问题有三种解。如果真要找出这三种
解,^_^,那就得加强对链表的操作了,比如说自己写一个动态链表类,顺便
完成一些初始化工作,估计看起来会舒服些。
下面给出部分关键程序:
// 主函数
int main()
{
// 初始化
QUESTION* pHead = new QUESTION;
pHead->riverSide1.wildMan = 3;
pHead->riverSide1.churchMan = 3;
pHead->riverSide2.wildMan = 0;
pHead->riverSide2.churchMan = 0;
pHead->side = -1; // 船在甲岸
pHead->pPrev = NULL;
pHead->pNext = NULL;
pHead->boat.wildMan = 0;
pHead->boat.churchMan = 0;
if (Process(pHead))
{
// ......... 遍历链表输出结果
}
cout<<"成功渡河。";
}
else
cout<<"到底怎样才能渡河呢? 郁闷!"<<endl;
// 回收内存空间
while (pHead)
{
QUESTION* pTemp = pHead->pNext;
delete pHead;
pHead=pTemp;
}
pHead = NULL;
return 0;
}
// 渡船过程, 递规调用函数 FindNext(...)
BOOL Process(QUESTION* pQuest)
{
if (FindNext(pQuest))
{
QUESTION* pNew = new QUESTION;
pNew->riverSide1.wildMan = pQuest->riverSide1.wildMan
+ pQuest->boat.wildMan*(pQuest->side);
pNew->riverSide1.churchMan = pQuest-
>riverSide1.churchMan + pQuest->boat.churchMan*(pQuest->side);
pNew->riverSide2.wildMan = 3 - pNew-
>riverSide1.wildMan;
pNew->riverSide2.churchMan = 3 - pNew-
>riverSide1.churchMan;
pNew->side = (-1)*pQuest->side;
pNew->pPrev = pQuest;
pNew->pNext = NULL;
pNew->boat.wildMan = 0;
pNew->boat.churchMan = 0;
pQuest->pNext = pNew;
if (pNew->riverSide2.wildMan==3 && pNew-
>riverSide2.churchMan==3)
return TRUE; // 完成
return Process(pNew);
}
else
{
QUESTION* pPrev = pQuest->pPrev;
剩余14页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功