新建 文本文档.cpp

野人过河问题属于人工智能学科中的一个经典问题,问题描述如下: 有三个牧师(也有的翻译为传教士)和三个野人过河,只有一条能装下两个人的船,在河的任何一方或者船上,如果野人的人数大于牧师的人数,那么牧师就

本文只找出了一种解，因为对于这种规模比较小的问题，得到一种解就够了。

下面给出核心程序（在VC6.0下编译通过）：  

/*============================================================================

 *File: Main.cpp

 *Content: 

      模拟野人过河问题, 问题描述如下: 

      有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果

      野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？

      假设河的两岸分别是甲岸和乙岸, 刚开始时6个人都在甲岸, 目标状态是六个人都在乙岸. 

 *Finished Date: 2004-04-05

 *Email: [e-mail]

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝*/

 
#include<iostream>

using namespace std;
 

typedef int BOOL;

 

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;

 

// 子函数声明

BOOL FindNext(QUESTION*);

BOOL Process(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))

    {

         char str[256] = "";

         cout<<"\n    野人过河问题, 描述如下: 话说有三个牧师和三个野人过河,只有一条能装\n"<<

               "下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数, 那\n"<<

               "么牧师就会有危险. 你能不能找出一种安全的渡河方法呢?\n\n"<

         cout<<"***************************  渡河最优过程  ***************************"<

        cout<<"______________________________________________________________________"<

         cout<<"  甲岸: 野人数|牧师数   渡河方向|载野人|载牧师   乙岸: 野人数|牧师数"<

         QUESTION* pQuest = pHead;

         while (pQuest)

         {

             wsprintf(str, "\t   %d\t %d\t  %s\t   %d\t  %d\t\t %d\t  %d", pQuest->riverSide1.wildMan, 

                  pQuest->riverSide1.churchMan,  (pQuest->side == -1) ? "---->":"<----", pQuest->boat.wildMan,

                  pQuest->boat.churchMan,pQuest->riverSide2.wildMan, pQuest->riverSide2.churchMan);

             cout<

             pQuest = pQuest->pNext;

         }

        cout<<"______________________________________________________________________"<

         cout<<"成功渡河。";

    }

    else

         cout<<"到底怎样才能渡河呢? 郁闷!"<

    // 回收内存空间

    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);

    }

// 不能找到合适的渡河操作，就返回当前节点的父节点，即pQuest在结果链表中的上级节点，同时删除pQuest节点

    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];

    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

    {

     // 如果扩展A节点得到B和C两个节点，然后假如说在继续扩展B的时候失败了，程序就需要返回到A节点，重新扩展，// 这个时候已经用过的算符就不能再用, 避免出现重新回到B节点。另外请注意我们选取算符是优先级的，比如说5

// 个算符中，第3个被用过了，那么第1、2个也肯定被用过了，那么现在就只能使用第4、5个了。

    for (i=0; i<5; i++) 

        if (pQuest->boat.wildMan == boatState[i].wildMan && pQuest->boat.churchMan == boatState[i].churchMan)

            break;

        i++;       

    } // end else

    

    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;

                  }//end if

                  break;  // 该操作可行, 推出循环

             }//end if

         }//end for

          // 找到合适渡船操作

         if (j < 5)

         {

             pQuest->boat.wildMan = boatState[j].wildMan;

             pQuest->boat.churchMan = boatState[j].churchMan;

             return TRUE;

         }//end if

    }//end if

    return FALSE;

}