传教士问题.cpp

传教士与野人问题

#include <iostream.h>
#include<stdio.h>


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 Process(QUESTION* pQuest);      //    渡船过程
bool FindNext(QUESTION* pQuest);      // 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作 


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; 
	   int i=1;
       if (Process(pHead)) 
       { 
           while( pHead!=NULL)
		   {     
			      cout<<"第 "<<i<<"步"<<endl;
                  cout<<"左岸有野人："<<pHead->riverSide1.wildMan<<endl;
				  cout<<"左岸有传教士: "<<pHead->riverSide1.churchMan<<endl;
				  pHead=pHead->pNext;
				  i++;
		   }
       } 
      
       
       while (pHead) 
       { 
              QUESTION* pTemp = pHead->pNext; 
              delete pHead; 
              pHead=pTemp; 
       } 
       pHead = NULL; 
       return 0; 
} 



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 1;  //     完成 
              return Process(pNew); 
       } 
       else 
       { 
              QUESTION* pPrev = pQuest->pPrev; 
              if (pPrev == NULL) 
                     return 0;        //     无解 
              delete pQuest; 
              pPrev->pNext = NULL; 
              return Process(pPrev);   // 返回其父节点重新再找 
       } 
       return 1; 
} 


// 算符共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 1; 
              } 
       } 
       return 0; 

}