答案：× 用状态空间法进行表示。根据状态空间表示问题的步骤,问题求解如下：第一步,定义问题状态的描述形式。设SK=(Nx,Ny,C)表示修道士和野人在河的左岸的状态,其中,Nx表示修道士在左岸的实际人数,Ny表示野人在左岸的实际人数,C用来指示船是否在左岸(C=1表示在左岸,C=0表示不在左岸)。第二步,用所定义的状态描述形式把问题的所有可能状态都表示出来,并确定出问题的初始状态集和目标状态集。对于状态SK=(Nx,Ny,C)来说,由于Nx,Ny的取值有0,1,2,3四种可能,C的取值有0和1两种可能,所以本问题所有可能的状态共有4×4×2=32种。各状态的形式描述如下： 在这些状态中,由于有安全约束条件——任何岸边野人的数量都不得超过传教士的数量(即Nx≥Ny),所以只有20个状态是合法的,像(1,2,1)、(1,3,1)和(2,3,1)等都是不合法的状态。而由于这些不合法状态的存在,又会导致某些合法状态是不可到达的。这样,这个问题总共只有16种可到达的合法状态,以下划线表示。问题的初始状态集为：S=(S0}={(3,3,1)},目标状态集为：G={S31)={(0,0,0))第三步,定义一组用于状态变换算符F。定义算符L(i,j)表示划船将i个传教士和j个野人送到右岸的操作；算符R(i,j)表示划船从右岸将i个传教士和j个野人带回左岸的操作。由于过河的船每次最多载两个人,所以,i j≤2,这样定义的算符组F中只可能有如下10个算符：F：L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)至此,该问题的状态空间(S,F,G)构造完成。这就完成了对问题的状态空间表示。为了求解该问题,根据该状态空间的16种可到达合法状态和10种算符,构造它的状态转换图,如图2．21所示。 在图2．21所示的状态空间图中,每个节点只能取L、R操作之一,这取决于变量C的取值,即船是在左岸还是在右岸,若船在左岸(即C=1),则只能取L操作,若船在右岸,则只能取R操作。从初始节点(3,3,1)(状态S0)到目标节点(0,0,0)(状态S31)的任何一条通路都是问题的一个解。其中：L(1,1),R(1,0),L(0,2),R(0,1),L(2,0),R(1,1),L(2,0),R(0,1),L(0,2),R(0,1),L(0,2)是算符最少的解之一。
