class1.cs

传教士和野人渡河问题盲目搜索算法 一个典型的人工智能算法

using System;

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


 *Content: 

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

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

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

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

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

 
namespace ConsoleApplication14
{
	/// <summary>
	/// Class1 的摘要说明。
	/// </summary>
	/// 
	public struct RIVERSIDE   // 岸边状态类型

	{

		public int wildMan;    // 野人数 

		public int churchMan;  // 牧师数

	};

 

	public struct BOAT  // 船的状态类型

	{  

		public int wildMan;    // 野人数

		public int churchMan;  // 牧师数

	};

 

	public class QUESTION

	{

		public RIVERSIDE riverSide1;   // 甲岸

		public RIVERSIDE riverSide2;   // 乙岸

		public int side;                 // 船的位置, 甲岸为-1, 乙岸为1

		public BOAT boat;              // 船的状态

		public QUESTION pPrev;        // 指向前一渡船操作

		public QUESTION pNext;        // 指向后一渡船操作

	};

 

	// 子函数声明

	//public static int FindNext(QUESTION quest);

	//public static int Process(QUESTION quest);

 
	class Class1
	{
		/// <summary>
		/// 应用程序的主入口点。
		/// </summary>
		[STAThread]
		static void Main(string[] args)
		{
			// savage.cpp : 定义控制台应用程序的入口点。
			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 =new char[256];
				

				Console.WriteLine("\n    野人过河问题, 描述如下: 话说有三个牧师和三个野人过河,只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数, 那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢?\n\n");

				Console.WriteLine("===========================渡河过程演示(盲目搜索)===========================");


				Console.WriteLine("  甲岸: 野人数|牧师数   渡河方向|载野人|载牧师   乙岸: 野人数|牧师数");

				QUESTION pQuest = pHead;

				while (pQuest!=null)

				{

					Console.WriteLine("\t   {0}\t {1}\t  {2}\t   {3}\t  {4}\t\t {5}\t  {6}", pQuest.riverSide1.wildMan, 

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

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

					pQuest = pQuest.pNext;

				}

				Console.WriteLine("===========================================================================");


			}
		}

					/* 回收内存空间

					while (pHead)

				{

					QUESTION pTemp = pHead.pNext;

					delete pHead;

					pHead=pTemp;

				}

			pHead = null;

				*/
 
 



 

//  渡船过程, 递规调用函数FindNext(...)

public static 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;         //  无解


         pPrev.pNext = null;

         return Process(pPrev);   // 返回其父节点重新再找

    }

   // return true;

}

 

// 判断有否下一个渡河操作, 即根据比较算符找出可以接近目标节点的操作

// 算符共5个: 1野/ 1牧 / 1野1牧 / 2野 / 2牧 

public static bool FindNext(QUESTION pQuest)

{
    // 基本规则

    // 渡船的优先顺序: 甲岸运多人优先, 野人优先; 乙岸运少人优先, 牧师优先.

    BOAT[] boatState=new BOAT[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;

}


		}
	}