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

野人过河问题算法分析

       野人过河问题属于人工智能学科中的一个经典问题，问题描述如下： 有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？
一、算法分析
       先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：
          初始状态：甲岸，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;
}