实验二 传教士与野人过河问题
一、实验目的
    理解并熟悉掌握深度优先搜索和广度优先搜索算法。
二、实验内容
    设有3个传教士和3个野人来到河边，打算乘一只船从左岸到右岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?
三、实验内容左岸右岸
  （1）设置状态变量并确定值域
  设M为传教士人数，C 为野人人数，B为船数，要求M>=C且M+C <= 3，
L表示左岸，R表示右岸。
初始状态                            目标状态
L    R                                L    R
M    3    0                            M    0    3
C    3    0                            C    0    3
B    1    0                            B    0    1
（2）确定状态组，分别列出初始状态集和目标状态集
    用三元组来表示：（ML , CL , BL）（均为左岸状态）
    其中，,BL ∈{ 0 , 1}
        ：(3 , 3 , 1)        ： (0 , 0 , 0)
      初始状态：表示全部成员在河的的左岸；
      目标状态：表示全部成员从河的左岸全部渡河到河的右岸。
（3）定义并确定规则集合
  以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其 中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。则共有10种操作，操作集为：  F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}
P10    if ( ML ,CL , BL=1 )  then ( ML–1 , CL , BL –1 )
P01    if ( ML ,CL , BL=1 )  then ( ML , CL–1 , BL –1 )
P11    if ( ML ,CL , BL=1 )  then ( ML–1 , CL–1 , BL –1 )
P20    if ( ML ,CL , BL=1 )  then ( ML–2 , CL , BL –1 )
P02    if ( ML ,CL , BL=1 )  then ( ML , CL–2 , BL –1 )
Q10     if ( ML ,CL , BL=0 )  then ( ML+1 , CL , BL+1 )
Q01    if ( ML ,CL , BL=0 )  then ( ML , CL+1 , BL +1 )
Q11    if ( ML ,CL , BL=0 )  then ( ML+1 , CL +1, BL +1 )
Q20    if ( ML ,CL , BL=0 )  then ( ML+2 , CL +2, BL +1 )
Q02    if ( ML ,CL , BL=0 )  then ( ML , CL +2, BL +1 )
（4）当状态数量不是很大时，画出合理的状态空间图
  箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和野人数。
       
                图1 状态空间图
四、算法设计
方法一: 树的遍历
    根据规则由根（初始状态）扩展出整颗树，检测每个结点的“可扩展标记”，为“-1”的即目标结点。由目标结点上溯出路径。
方法二：启发式搜索
    构造启发式函数为：
           
    选择较大值的结点先扩展。
5、实验结果
  1、请给出求得问题解的具体过程，即从初始结点到目标结点的解路径。
  2、程序清单。
  3、给出结点的表示方法，和操作的表示方法。