我对野人过河的问题思考

其中0?ML?3,0?CL?3，BL ∈{ 0 , 1}（1为左岸，0为右岸）； S0：(3 , 3 , 1) Sg：(0 , 0 , 0)； 初始状态和目标状态如下： 初始状态 L M 3 Y B 3 1 R 0 0 0 目标状态 L R M 0 Y B 0 0 3 3 1 3. 确定规则集 以河的左岸为基点考虑，船从左岸划向右岸定义为Pij操作，其中，下标i表示船载的传教士数，下标j表示船载的野人数；同理，从右岸将船划回左岸称为Qij操作，下标的定义同前。则共有10种操作，操作集为： F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20} P10 ：if ( ML ,YL , 1 ) then ( ML–1 , YL , 0 ) P01 ：if ( ML ,YL , 1 ) then ( ML ,YL–1 , 0 ) P11 ：if ( ML ,YL , 1 ) then ( ML–1,YL–1 , 0 ) P20 ：if ( ML ,YL , 1 ) then ( ML–2 , YL , 0 ) P02 ：if ( ML ,YL , 1 ) then ( ML , YL–2 , 0 ) Q10 ：if ( ML ,YL , 0 ) then ( ML+1 , YL , 1 ) Q01 ：if ( ML ,YL , 0 ) then ( ML , YL+1 , 1 ) Q11 ：if ( ML ,YL , 0 ) then ( ML+1 , YL +1, 1 ) Q20 ：if ( ML ,YL , 0 ) then ( ML+2 , YL , 1 ) Q02 ：if ( ML ,YL , 0 ) then ( ML , YL +2, 1 ) 4. 确定合理的状态 在（ML , YL , BL）中，0?ML?3,0?YL?3，BL ∈{ 0 , 1}，因此共有4×4×2=32种状态，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种： S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1) 左岸 S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1) 右岸 S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0) S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0) Example：(3 3 1) (2 2 0) (3 2 1) (3 0 0) (3 1 1) (1 1 0) (2 2 1) (0 2 0) (0 3 1) (0 1 0) (0 2 1) (0 0 0) 三 算法设计 启发式搜索，构造启发式函数为：满足条件时：f?6.01?ML?YL，其他：f???，选择较大值的结点先扩展。 方法如下： 第1次：左岸到右岸，传教士过去1人，野人过去1人； 第2次：右岸到左岸，传教士过去1人，野人过去0人； 第3次：左岸到右岸，传教士过去0人，野人过去2人； 第4次：右岸到左岸，传教士过去0人，野人过去1人； 第5次：左岸到右岸，传教士过去2人，野人过去0人； 第6次：右岸到左岸，传教士过去1人，野人过去1人； 第7次：左岸到右岸，传教士过去2人，野人过去0人； 第8次：右岸到左岸，传教士过去0人，野人过去1人； 第9次：左岸到右岸，传教士过去0人，野人过去2人； 第10次：右岸到左岸，传教士过去0人，野人过去1人； 第11次：左岸到右岸，传教士过去0人，野人过去2人； 问题结束。 C源代码： 程序尚待改进 # include 主函数： {int a=3,b=3,h=1,i=1,c=0,d=0; void LR(int x,int y); void RL(int k,int p); printf(\状态：%d\\n%d,%d,\\n%d,%d\\n\i++; while(a!=0||b!=0||h!=0) {if(h!=0) {LR (a,b); a=R; b=Q; c=3-a; d=3-b; printf(\状态：%d\\n%d,%d,\\n%d,%d,\\n\h--; i++;} else {RL (c,d); c=R; d=Q; a=3-c; b=3-d; printf(\状态;%d\\n%d,%d,\\n%d,%d,\\n\ h++; i++;} } i--; printf(\} void LR(int x,int y) {if(x!=y) { if(y==1) {x=x-2; R=x; Q=y;} else {x--; y--; R=x; Q=y;} } else {x--; y--; R=x; Q=y;} } void RL(int k,int p) {if(k==p) {k--; p--; R=k; Q=p;} else { p--; R=k; Q=p;} } Matlab源代码： 运用启发式函数： function [ ]=guohe() Ylear all; Ylose all; global n node open_list index; n=2; result=zeros(100,1); node=zeros(100,5);