商人过河问题的MATLAB程序

数学建模中经典问题商人过河问题的MATLAB源代码，绝对是自己想出来的算法，比枚举算法的时间复杂度要小得多，算法中运用了队列作为存储结构，自己感觉非常的巧妙，前天用C语言实现后，一直想着用MATLAB实现，现在将同样算法的MATLAB源代码提供给大家，希望广大朋友给我提出意见和建议，Email：liang.wang.hubei@gmail.com，谢谢

function s=businessman
n=input（‘输入商人数目：‘）;
nn=input（‘输入仆人数目：‘）;
nnn=input（‘输入船的最大容量：‘）;
if nn>n
    n=input（‘输入商人数目：‘）;
    nn=input（‘输入仆人数目：‘）;
    nnn=input（‘输入船的最大容量：‘）;
end
k=1;
for i=0:nnn %产生出所有的可能过河的决策
    for j=0:nnn
        if （i+j<=nnn） &（i+j>0）
            d（k1:3）=[ij1];       %1表示从此岸到彼岸
            d（k+11:3）=[-i-j-1];  %-1表示从彼岸到此岸
            k=k+2;
        end
    end
end
k=1;
for i=n:-1:0            %产生安全队列
    for j=nn:-1:0
        if （（i>=j） & （（n-i）>=（nn-j））） | （（i==0）|（i==n））
            A（k1:3）=[ij1];       %1表示此岸安全    
            k=k+1;
        end
    end
end
%队列数据结构，第一列表示商人数，第二列表示仆人数，第三列用于记录该结点的上一个结点，第四列表示船的运动方向（1表示此岸往彼岸运动，-1表示从彼岸往此岸运动）
sq（11）=n;sq（12）=nn;sq（13）=0;sq（14）=1;        %初始状态
front=1;rear=1; %队列的头尾指针
while（front<=rear）
    x=sq（front1）;
    y=sq（front2）;
    flag=0;
    if （sq（front4）==1）
        for v=2:2:size（d1）
            i=x+d（v1）;
            j=y+d（v2）;
            if （is_save（Aij）==1）
                rear=rear+1;
                sq（rear1）=i;
                sq（rear2）=j;
                sq（rear3）=front;
                sq（rear4）=-1;
            end
            if （i==0 && j==0）
                flag=1;
            end
        end
    end
    if （flag==1）
        break;
    end
    flag=0;
    if （sq（front4）==-1）
        for v=1:2:size（d1）
            i=x+d（v1）;
            j=y+d（v2）;
            if （is_save（Aij）==1） & （sq（sq（front3）1）~=i | sq（sq（front3）2）~=j）
                rear=rear+1;
                sq（rear1）=i;
                sq（rear2）=j;
                sq（rear3）=front;
                sq（rear4）=1;
            end
            if （i==0 && j==0）
                flag=1;
            end
        end
    end
    if （flag==1）
        break;
    end
    front=front+1;
end
%打印路径
i=sq（rear3）;
k=2;
s（11）=0;s（12）=0;
while（i>0）
    s（k1）=sq（i1）;
    s（k2）=sq（i2）;
    i=sq（i3）;
    k=k+1;
end

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2082  2010-08-30 15:40  商人过河MATLAB\businessman.m

     文件        149  2010-08-30 07:05  商人过河MATLAB\is_save.m

     目录          0  2010-08-30 15:45  商人过河MATLAB

----------- ---------  ---------- -----  ----

                 2231                    3