missionary.m

解决关于牧师和野人过河的经典问题

S=[3 3 0];     
T=[3 3 1];    

OPEN=S;                    %存储待扩展节点的表
OPENList=[0];              %存储OPEN表中各节点的父节点指针
CLOSE=[];                  %存储已经被扩展过的节点，搜索图
Pointer=[];                %用来存储图中各节点的父节点指针
Next=[];                   %存储搜索过程中正在被扩展的节点的后继节点

%以下循环为搜索过程
begintime = cputime;      %搜索开始时间
while ~isempty(OPEN)       
    Node=OPEN(1,:);     %将OPEN表中的第一个节点作为下一步将要扩展的节点
  
    Pointer=[Pointer,OPENList(1)];   %将当前要扩展的节点的父节点指针加入Poiner表中
    OPENList=OPENList(2:end);        %将当前要扩展的节点的父节点指针从OPENList表中移去
    CLOSE=[CLOSE; Node];                %将当前要扩展的节点加入已扩展节点表中
    OPEN=OPEN(2:end,:);                %将当前要扩展的节点从OPEN表中移去
    
  %     假如当前要扩展的节点就是目标节点，则成功，退出循环
    if isempty(find(T-Node))
        break;
    end
    
    
    if Node(3)==0
        L=Node(1:2);
        R=3-L;
        if L(1)>=1 & L(2)>=1 & (R(1)+1>=R(2)+1)  %假如运一个传教士和一个野人
            Temp=[R(1)+1 R(2)+1 1];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))   
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if L(1)>=2 & (L(1)-2==0 | L(1)-2>=L(2)) %假如运二个传教士
            Temp=[R(1)+2,R(2),1];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if L(2)>=2 & (R(2)+2<=R(1) | R(1)==0)  %假如运二个野人
            Temp=[R(1) R(2)+2,1];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if L(1)>=1 & (L(1)-1>=L(2) | L(1)==0) & R(1)+1>=R(2)%假如运一个传教士
            Temp=[R(1)+1 R(2) 1]; 
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next ;Temp];
            end
        end
        if   L(2)>=1 & (R(1)>=R(2)+1 | R(1)==0)%假如运一个野人
            Temp=[R(1) R(2)+1 1]; 
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next ;Temp];
            end
        end
        
    else
        R=Node(1:2);
        L=3-R;
        if R(1)>=1 & (R(1)-1>=R(2) | R(1)==0) & L(1)+1>=L(2)%假如运一个传教士
            Temp=[L(1)+1 L(2) 0]; 
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if   R(2)>=1 & (L(1)>=L(2)+1 | L(1)==0)%假如运一个野人
            Temp=[L(1) L(2)+1 0]; 
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next ;Temp];
            end
        end
        if R(1)>=1 & R(2)>=1 & (L(1)+1>=L(2)+1)%假如运一个传教士和一个野人
            Temp=[L(1)+1 L(2)+1 0];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if R(1)>=2 & (R(1)-2==0 | R(1)-2>=R(2)) %假如运二个传教士
            Temp=[L(1)+2,L(2),0];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
        if R(2)>=2 & (L(2)+2<=L(1) | L(1)==0)  %假如运二个野人
            Temp=[L(1) L(2)+2,0];
            isancestor=0;
            Ancestor=Pointer(end);
            while Ancestor~=0
                if isempty(find(Temp-CLOSE(Ancestor,:)))  
                    isancestor=1;
                    break;
                end
                Ancestor=Pointer(Ancestor);
            end
            if ~isancestor
                Next=[Next; Temp];
            end
        end
    end
    
    
%     检查后继节点表中的节点是否在OPEN表或在CLOSE表中，并将在OPEN表或在CLOSE表中的后继节点存于inopenorclose中
    inopenorclose=[];
    for k=1:size(Next,1)
        for t=1:size(OPEN,1)
            if all(all(Next(k,:)==OPEN(t,:)))
                inopenorclose=[inopenorclose,k];
                break;
            end
        end
        for t=1:size(CLOSE,1)
            if all(all(Next(k,:)==CLOSE(t,:)))
                inopenorclose=[inopenorclose,k];
                break;
            end
        end
    end
%    从Next表中去掉已在OPEN表或在CLOSE表中的后继节点
    while ~isempty(inopenorclose)
        k=inopenorclose(1);
        Next=[Next(1:k-1,:);Next(k+1:end,:)];
        inopenorclose=inopenorclose(2:end);
        inopenorclose=inopenorclose-1;
    end

%     将不在在OPEN表或在CLOSE表中的后继节点加入OPEN表，对其重排并将它们的父节点指针加入OPENList表
    father=length(Pointer);
    OPEN=[OPEN; Next];
    OPENList=[OPENList,father*ones(1,size(Next,1))];
    Next=[];
end

% 目标节点已找到，回溯找到求解路径
TheAnswer=Node;
last=Pointer(end);
while last~=0
    TheAnswer=[CLOSE(last,:); TheAnswer];
    last=Pointer(last);
end
times =(cputime-begintime)/60        %计算搜索时间
%sstate=TheAnswer(1:2:end-1,:);
%estate=TheAnswer(2:2:end,:);
TheResult=[];
for i=1:size(TheAnswer,1)
    d=TheAnswer(i,3);
    if d==0
        L=TheAnswer(i,1:2);
        R=3-L;
        boat=' L ';
    else
        R=TheAnswer(i,1:2);
        L=3-R;
        boat=' R ';
    end
    
    state=[];
    for j=1:3-L(1)
        state=[state,'  '];
    end
    for j=1:L(1)
        state=[state,' M'];
    end
    for j=1:3-L(2)
        state=[state,'  '];
    end
    for j=1:L(2)
        state=[state,' W'];
    end
    state=[state,'------------'];
    for j=1:3-R(1)
        state=[state,'  '];
    end
    for j=1:R(1)
        state=[state,' M'];
    end
    for j=1:3-R(2)
        state=[state,'  '];
    end
    for j=1:R(2)
        state=[state,' W'];
    end
    TheResult=[TheResult;boat,state];
end
TheResult