传教士野人问题

问题：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险 问题：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？   解答一：一、算法分析        先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：           初始状态：甲岸，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<<"到底怎样才能渡河呢? 郁闷!"<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;               if (pPrev == NULL)                      return FALSE;        //     无解               delete pQuest;               pPrev->pNext = NULL;               return Process(pPrev);   // 返回其父节点重新再找        }        return TRUE; } // 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作 // 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧 BOOL FindNext(QUESTION* pQuest) {        // 基本规则        // 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.        static BOAT boatState[5];  // 5个算符        if (pQuest->side == -1)          {               boatState[0].wildMan = 2;               boatState[0].churchMan = 0;               boatState[1].wildMan = 1;               boatState[1].churchMan = 1;               boatState[2].wildMan = 0;               boatState[2].churchMan = 2;               boatState[3].wildMan = 1;               boatState[3].churchMan = 0;               boatState[4].wildMan = 0;               boatState[4].churchMan = 1;        }        else        {               boatState[0].wildMan = 0;               boatState[0].churchMan = 1;               boatState[1].wildMan = 1;               boatState[1].churchMan = 0;               boatState[2].wildMan = 0;               boatState[2].churchMan = 2;               boatState[3].wildMan = 1;               boatState[3].churchMan = 1;               boatState[4].wildMan = 2;               boatState[4].churchMan = 0;        }        int i;  // 用来控制算符        if (pQuest->boat.wildMan == 0 && pQuest->boat.churchMan == 0) // 初始状态, 第一次渡河时                i = 0;  // 取算符1        else        {               for (i=0; i<5; i++)  // 扩展同一节点时, 已经用过的算符不再用, 按优先级来                      if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)                             break;               i++;        }        if (i < 5)        {               int j;               for (j=i; j<5; j++)               {                      int nWildMan1 = pQuest->riverSide1.wildMan + boatState[j].wildMan * pQuest->side;                      int nChurchMan1 = pQuest->riverSide1.churchMan + boatState[j].churchMan * pQuest->side;                      int nWildMan2 = 3 - nWildMan1;                      int nChurchMan2 = 3 - nChurchMan1;                      // 判断本次操作的安全性, 即牧师数量>=野人或牧师数为0                      if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&                             (nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&                             nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)                      {                             // 本操作是否重复上次操作,注意方向不同                            if (pQuest->pPrev != NULL)                            {                                    if (pQuest->pPrev->boat.wildMan == boatState[j].wildMan &&                                           pQuest->pPrev->boat.churchMan == boatState[j].churchMan)                                    continue;                             }                             break;  // 该操作可行, 推出循环，只找出当前最优节点                      }               }               if (j < 5)               {                      pQuest->boat.wildMan = boatState[j].wildMan;                      pQuest->boat.churchMan = boatState[j].churchMan;                      return TRUE;               }        }        return FALSE; }       解答二： 编程，接收m和n，搜索一条可让所有的野人和传教士安全渡到右岸的

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

。我们先假设左岸有3个传教士和3个野人，小船最多可乘2人。把当前左岸的状态抽象为： (3,3,1) 前两个"3"代表左岸有3个传教士和3个野人，1代表船在左岸。把每一次可行的渡船方案作为算符。比如，在初始状态，让1个传教士和1个野人上船并渡到右岸，这一算符可表示为： (1,1) 算符的两位数分别代表要移动的传教士，野人的数量；把人移到没有船的岸边并且改变状态向量中船的值。 对于固定大小的小船，算符的数量是一定的： class Move { public:     int missionary;      //要移动的传教士数量     int cannibal;        //野人 }; class MoveGroup { public:     Move move[500];      //算符集     int numMove;         //可用算符的总数     MoveGroup(int MAX_ON_BOAT) {    //利用构造器求算符集        int m, c, i = 0;        for (m = 0; m <= MAX_ON_BOAT; m++)            for (c = 0; c <= MAX_ON_BOAT; c++)               if (c==0 && m!=0) { move[i].missionary=m; move[i].cannibal=0; i++; }               else if (m==0 && c!=0) { move[i].missionary=0; move[i].cannibal=c; i++; }               else if (m+c<=MAX_ON_BOAT && m+c!=0 && m>=c) { move[i].missionary = m; move[i].cannibal = c; i++; }        numMove = i;     } }; 创建一个MoveGroup 对象 MoveGroup mg(2); 即可得到当小船最多可乘2人时的算符集。 这个程序所要做的，就是通过这个已知的算符集，将初始状态(3,3,1)转变为最终状态(0,0,0)。我们应将状态作为搜索的元素。 构建类时应注意，并不是每个算符对于任意的状态都是可以应用的，这需要对应用算符后的安全性进行检查，以判断这一算符对当前状态是否可用；同时，类中也要包含一个判断当前状态是否是最终节点(0,0,0)的方法；当然”==”，”=”这两个运算符以及null值，这是调用dso.h时所不可或缺的。（详见源文件） class ElemType : Move {  //继承Move类，获得传教士，野人数据成员。 private:     bool boat;            //船是否在左岸？ public:     ElemType* flag;      //这个后边再说，暂时用不到     ElemType(int MAX_PEOPLE) {  //创建初始状态        missionary = cannibal = MAX_PEOPLE;        boat = true;        flag = NULL;     }     ElemType() {}     bool operator ==(ElemType e) { return this->missionary==e.missionary && this->cannibal==e.cannibal && this->boat==e.boat;     }     void operator =(ElemType e) {        this->missionary = e.missionary;        this->cannibal = e.cannibal;        this->boat = e.boat;        this->flag = e.flag;     }     ElemType friend operator >>(ElemType source, Move &mv) {     //移动操作，通过重载运算符“>>”，你将在isSafe(ElemType)中见到用法。        ElemType result;        if(source.boat == 1) {            result.missionary = (source.missionary -= mv.missionary);            result.cannibal = (source.cannibal -= mv.cannibal);            result.boat = 0;        } else {            result.missionary = (source.missionary += mv.missionary);            result.cannibal = (source.cannibal += mv.cannibal);            result.boat = 1;        }        return result;     }     bool isSafe(Move &mv, int MAX_PEOPLE) { //判断当前状态在进行mv操作后还是不是安全状态        if( (boat==1&&(missionary-mv.missionary < 0 ||            cannibal-mv.cannibal < 0)) ||            (boat==0&&(missionary+mv.missionary > MAX_PEOPLE ||            cannibal+mv.cannibal > MAX_PEOPLE)) )            return false;        else {            ElemType temp = *this >> mv;            if( temp.missionary==0 || temp.missionary==MAX_PEOPLE ||               (temp.missionary>=temp.cannibal &&               MAX_PEOPLE-temp.missionary >= MAX_PEOPLE-temp.cannibal))               return true;            else return false;        }     }     bool isSuccess() { return missionary==0 && cannibal==0 && boat==0; }     //isSuccess()判断当前状态是否为最终节点     int getM() { return missionary; }     int getC() { return cannibal; }     int getB() { return boat; }     void print() { cout <<'('<< missionary <<','<< cannibal <<','<< boat <<')' << endl; } };   const ElemType null(0);         //(0,0,1) 这是不会出现的 void print(ElemType &e) { e.print(); }     //打印函数   至此，我们已经完成了对问题的描述。 搜索过程采用较简单的“宽度优先盲目搜索”，算法框图如下：   #include "dso.h" typedef ElemType Status; 当得到了一个最终节点(0,0,0)时，如果我们前边的操作没有保存路径的话，那么我们就只知道这个问题有解，而不知道解的具体路径。还记得在定义ElemType时那个旗子指针吗，用它保留它的父节点的地址，问题就解决了。  open，closed表均通过队列实现。由于对扩展节点要保存指针，所以closed表需要一个获得尾指针的方法。 class Queuex : public Queue { public:     ElemType* getTailPtr() {        if(Queue::isEmpty()) return NULL;        QNode* temp = front->next;        while(temp != rear) {            if(temp->next == rear) return &temp->next->node;            temp = temp->next;        }        return &temp->node;     } }; 搜索得到的答案也保存在一个队列里，但我们知道：当得到一个最终节点时，根据它的指向父节点的指针向上搜索得到的是一个反的解序列，这里使用一个临时的栈，可以将解的顺序调换过来。 class Answer : public Queue { private:     int max_people; public:     Answer(int MAX_PEOPLE, int MAX_ON_BOAT) {        Queue open;        Queuex closed;        Stack temp;                 //这是所使用的临时栈        Status s0(MAX_PEOPLE);       //这是初始节点        MoveGroup mg(MAX_ON_BOAT);  //这是算符集 //以下是搜索算法：        open.enqueue(s0);        max_people = MAX_PEOPLE;        while(!open.isEmpty()) {            Status s1 = open.dequeue(), s2;            closed.enqueue(s1);            ElemType* ptr = closed.getTailPtr();            //得到被扩展的父节点的指针ptr            for(int i = 0; i < mg.numMove; i++)               if( s1.isSafe(mg.move[i], MAX_PEOPLE) ) {                   s2 = s1 >> mg.move[i];                   if(closed.locate(s2) == INFEASIBLE) { s2.flag = ptr; open.enqueue(s2); }                   if(s2.isSuccess()) {                   //搜索到最终节点后的操作                      closed.enqueue(s2);                      while(s2.flag != NULL) { temp.push(s2); s2 = *(s2.flag); }                      this->enqueue(s0);                      while(!s2.isSuccess()) { s2 = temp.pop(); this->enqueue(s2); }                      return;                   }               }        }     }     void show() { this->traverse(print); } };   就要成功了，通过下面这个声明就可以得到MAX_PEOPLE个传教士，MAX_PEOPLE个野人，每艘船上最多乘坐MAX_ON_BOAT人的解： Answer answer(MAX_PEOPLE, MAX_ON_BOAT); 通过下面的调用可以列出整个解的过程： answer.show(); 源程序 >>>  （在控制台输入MAX_PEOPLE和MAX_ON_BOAT，然后输出mco.log演示移动过程）