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

实用标准文档

function s=destination() global n node;

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

2. 运用启发式函数 %%

%野人和传教士过河问题 úte:2010/12/15

%author:wang shi ting

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

global n node open_list index; n=2;

result=zeros(100,1); node=zeros(100,5);

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

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

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

open_list=[1,0.01];%节点号 启发函数值

while (1)

[row,~]=size(open_list); if row==0

fprintf('all the nodes in open list have been expanded.'); return end

for i1=1:row

open_list(i1,2)=6.01-node(open_list(i1,1),1)-node(open_list(i1,1),2);%定义启发函数

if node(open_list(i1,1),4)==-1%如果该结点是目标结点，则打印结果 fprintf('传教士野人过河问题\\n'); j=1;

k=open_list(i1,1); StepNum=1;

文案大全

实用标准文档

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

fprintf('方法如下\\n'); 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'); return end end

[r_row,~,~]=find(open_list(:,2)==max(open_list(:,2))); j=open_list(r_row(1,1),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

%display(open_list);

open_list(r_row(1),:)=[ ]; index=index-1;%open表个数减1 %display(open_list); end %%

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

global node open_list index; 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

index=index+1;

open_list(index,1)=n; n=n+1; %%

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

global node open_list index; 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

index=index+1;

open_list(index,1)=n; 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;%均不相同 %%

function s=destination() global n node;

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

文案大全