传教士野人过河问题-两种解法思路

S:S0?{0,0,0,0,0,0,0} G:Sg?{1,1,1,1,1,1,1}

但在描述规则时发现这样定义会造成规则麻烦、不清晰，原因在于此题并不关心是哪几个传教士和野人在船上，仅关心其人数，故没有必要将每个人都设置变量，分别将传教士、野人、船作为一类即可。

四、源代码

1. 源程序1：树的遍历 %野人和传教士过河问题 úte:2010/12/14

%author:wang shi ting

function [ ]=guohe() clear all; close all;

global n node; n=2;

solveNum=1; %问题的解法 result=zeros(100,1);

node=zeros(300,5);

node(1,:)=[3,3,1,1,-1];%初始化

%1左岸传教士数 2左岸野人数 3船（1为左岸，0为右岸）

%4是否可扩展(1为可扩展) 5父节点号（-1表示无父节点，即为初始节点） j=1;

% for j=1:n while (1) if j>n break end

if node(j,4)==1 %判断结点是否可扩展 if node(j,3)==1 %船在左岸

if ( (node(j,1)==0) || (node(j,1)==3) )&&(node(j,2)>=1) forward(j,0,1); end

if (node(j,1)==1 && node(j,2)==1 || node(j,1)==3 && node(j,2)==2) forward(j,1,0); end

if (node(j,1)>=1 && node(j,1)==node(j,2)) forward(j,1,1);

end

if (node(j,1)==0 || node(j,1)==3)&& node(j,2)>=2 forward(j,0,2); end

if (node(j,1)==2 && node(j,2)==2 || node(j,1)==3 && node(j,2)==1) forward(j,2,0); end

elseif node(j,3)==0%船在右岸

if ( (node(j,1)==0) || (node(j,1)==3) )&&(node(j,2)<=2) afterward(j,0,1); end

if (node(j,1)==2 && node(j,2)==2 || node(j,1)==0 && node(j,2)==1) afterward(j,1,0); end

if (node(j,1)<=2 && node(j,1)==node(j,2)) afterward(j,1,1); end

if (node(j,1)==0 || node(j,1)==3)&& node(j,2)<=1 afterward(j,0,2); end

if (node(j,1)==1 && node(j,2)==1 || node(j,1)==0 && node(j,2)==2) afterward(j,2,0); end end end j=j+1; end

fprintf('传教士野人过河问题\\n'); for t=1:n j=1; k=t;

StepNum=1;

if node(k,4)==-1 while (k~=-1) result(j)=k; k=node(k,5); j=j+1; end j=j-1;

fprintf('第%d种方法：\\n',solveNum); while j>1

BoatPriNum=node(result(j),1)-node(result(j-1),1); BoatWildNum=node(result(j),2)-node(result(j-1),2); if node(result(j),3)==1

fprintf('第%d次：左岸到右岸，传教士过去%d人，野人过去%d人\\n',...

StepNum,abs(BoatPriNum),abs(BoatWildNum)); StepNum=StepNum+1; end

if node(result(j),3)==0

fprintf('第%d次：右岸到左岸，传教士过去%d人，野人过去%d人\\n',...

StepNum,abs(BoatPriNum),abs(BoatWildNum)); StepNum=StepNum+1; end j=j-1; end

pause(0.2); fprintf('\\n');

solveNum=solveNum+1; end end

fprintf('问题结束'); %%

%从左岸到右岸,船上传教士x个，野人y个 function []=forward(z,x,y) global n; global node;

node(n,1)=node(z,1)-x; node(n,2)=node(z,2)-y; node(n,3)=0; r=search(z); if(~r) return end

node(z,4)=0; node(n,4)=1; node(n,5)=z; s=destination(); if s

node(n,4)=-1; end

n=n+1; %%

%%从右岸到左岸,船上传教士x个，野人y个

function []=afterward(z,x,y) global n; global node;

node(n,1)=node(z,1)+x; node(n,2)=node(z,2)+y; node(n,3)=1;

r=search(z); if(~r) return end

node(z,4)=0; node(n,4)=1; node(n,5)=z;

s=destination(); if s

node(n,4)=-1; end

n=n+1; %%

function r=search(x) global n node; i=x;

while node(i,5)~=-1

if node(i,1)==node(n,1) && node(i,2)==node(n,2) && node(i,3)==node(n,3) r=0; return end

i=node(i,5); end

%跟初始节点比较

if node(i,1)==node(n,1) && node(i,2)==node(n,2) && node(i,3)==node(n,3) r=0; return end

r=1;%均不相同 %%