guohe.c

野人过河问题,可能有点问题,但基本思想是对的,大家再查一下

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;

// 主函数
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<<"到底怎样才能渡河呢? 郁闷!"<<endl;
       // 回收内存空间
       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);
       }
       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;

}