《传教士野人问题》由会员分享，可在线阅读，更多相关《传教士野人问题（11页珍藏版）》请在金锄头文库上搜索。
1、问题：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有 的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上， 如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？解答一：一、算法分析先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，3野人，3牧师；乙岸，0野人，0牧师；船停在甲岸，船上有0个人；目标状态：甲岸，0野人，0牧师；乙岸，3野人，3牧师；船停在乙岸，船上有0个人；整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改 变是通过划船渡河来引发的，所以
2、合理的渡河操作就成了通常所说的算符，根据题目要求，可 以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个 FindNext()函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节 点，看看是否有其它兄弟节点可以扩展，然后用Process()函数递规调用FindNext()，一 级一级的向后扩展。搜索中采用的一些规则如下：1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运
3、少人优先），同 时牧师优先运走；2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3；4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜 索其兄弟节点，而是直接载入链表。5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b， 从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。 二、基本数据结构仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各 自的数目、船的状态、整个问题状态。所以我们定义如下几个数据结构： typedef st
4、ruct _riverside / 岸边状态类型 int wildMan; / 野人数 int churchMan; / 牧师数 RIVERSIDE;typedef struct _boat / 船的状态类型 int wildMan; / 野人数int churchMan; / 牧师数BOAT; typedef struct _question / 整个问题状态 RIVERSIDE riverSide1; / 甲岸RIVERSIDE riverSide2; / 乙岸int side; / 船的位置, 甲岸为-1, 乙岸为1BOAT boat; / 船的状态_question* pPrev; /
5、 指向前一渡船操作_question* pNext; / 指向后一渡船操作 QUESTION; 用QUESTION来声明一个最基本的链表。 三、程序流程及具体设计 本文只找出了最优解，据我所知，本问题有三种解。如果真要找出这三种解，_，那 就得加强对链表的操作了，比如说自己写一个动态链表类，顺便完成一些初始化工作，估计看 起来会舒服些。下面给出部分关键程序： / 主函数 int main() / 初始化QUESTION* pHead = new QUESTION;pHead-riverSide1.wildMan = 3;pHead-riverSide1.churchMan = 3;pHead-
6、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)/ . 遍历链表输出结果 coutpNext;delete pHead;pHead=pTemp;pHead = NULL;return 0; / 渡船过程, 递规调用函数FindNext(.) BOOL Process(QUESTION*
7、 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;pNe
8、w-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 / 完成return Process(pNew);elseQUESTION* pPrev = pQuest-pPrev;if (pPrev = NULL)retur
9、n FALSE; / 无解delete pQuest;pPrev-pNext = NULL;return Process(pPrev); / 返回其父节点重新再找return TRUE; / 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作 / 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧 BOOL FindNext(QUESTION* pQuest) / 基本规则/ 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.static BOAT boatState5; / 5个算符if (pQuest-side = -1) boatSta
10、te0.wildMan = 2;boatState0.churchMan = 0;boatState1.wildMan = 1;boatState1.churchMan = 1;boatState2.wildMan = 0;boatState2.churchMan = 2;boatState3.wildMan = 1;boatState3.churchMan = 0;boatState4.wildMan = 0;boatState4.churchMan = 1;elseboatState0.wildMan = 0;boatState0.churchMan = 1;boatState1.wildMan = 1;boatState1.churchMan = 0;boatState2.wildMan = 0;boatState2.churchMan = 2;boatState3.wildMan = 1;boatState3.churchMan = 1;boatState4.wildMan = 2;boatState4.churchMan = 0;int i; / 用来控制算符if (pQuest-boat.wildMan = 0 / 取算符1elsefor (i=0; iboat.wildMan = boatStatei.wildMan
