野人过河问题算法分析.doc

《野人过河问题算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、野人过河问题属于人工智能学科屮的一•个经典问题，问题描述如下：有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船,在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险.你能不能找出一种安全的渡河方法呢？一、算法分析先来看看问题的初始状态和n标状态，假设和分为甲岸和乙岸：初始状态：甲岸，3野人，3牧师；乙岸，0野人，0牧师；船停在甲岸，船上有0个人；戸标状态：甲岸，0野人，0牧师；乙岸，3野人，3牧师；船停在乙岸，船上有0个人；整个问题就抽彖成了怎样从初始状态经屮间的一•系列状态达到H标状态。问题状

2、态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题H要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一•个FindNext（-）函数找出下一步可以进行的渡河操作屮的最优操作,如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process（•••）函数递规调用FindNext（•••）,一级一级的向后扩展。搜索111采用的一•些规则如下:1、渡船优

3、先规则：甲岸一•次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走；2、不能重复上次渡船操作（通过链表屮前一操作比较），避免进入死循坏;3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；4、由于只是找岀最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。5、若扩展某节点8的时候，没有找到合适的子节点，则从链表屮返回节点a的父节点b,从上次已经选择了的算符之后的算符屮找最优先的算符继续扩展bo二、基本数据结构仔细阅读

4、问题，可以发现有些基本东西我们必须把握，例如：每吋刻河两岸野人牧师各自的数门、船的状态、整个问题状态。所以我们定义如下几个数据结构：typedefstructriverside//岸边状态类型intw订dMan;//野人数intchurchMan;//牧帅数}RIVERSIDE;typedefstruct_boat//船的状态类型{intw订dMan;//野人数intchurchMan;//牧师数}BOAT;typedefstruct_question//整个问题状态{RIVERSIDEriverSidel;//甲岸RIVERSIDEri

5、verSide2;//乙岸intside;//船的位置，甲岸为-1,乙岸为1BOATboat;//船的状态.question*pPrev;//指向前一渡船操作_questi()n*pNext;//指向后一渡船操作}QUESTION;用QUESTTON来声明一个最基本的链表。三、程序流程及具体设计本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，\那就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看起来会舒服些。下而给出部分关键程序：//主函数intmdin(){//初始化QUESTION

6、*pHead=newQUESTION;pHead->riverSidel.wildMan=3;pHead->riverSidel.churchMan二3;pllead->riverSide2.wiIdMan=0;pHead->riverSide2.churchMan=0;pHead->side=-1;//船在甲岸pHead->pPrev=NULL;pHead~>pNext=NULL;pllead~>boat.wi1dMan二0;pHead->boat.churchMan=0;if(Process(pHead))//遍历链表输出结果cout

7、«"成功渡河。〃；}elsecout«，z到底怎样才能渡河呢？郁闷!，z«endl;//回收内存空间while(pHead){QUESTION*pTemp二pHead->pNext;deletepHead;pHead=pTemp;}pHead二NULL;return0;}//渡船过程，递规调用函数FindNext(...)BOOLProcess(QUESTION*pQuest){if(FindNext(pQuest)){QUESTION*pNew=newQUESTION;pew->riverSidel.wildMan=pQuest->r

8、iverSidel.wildMan+pQuest~>boat.wiIdMan*(pQuest~>side);pNew->riverSidel.churchMan二pQuest->riverSi