哪位高手编过商人过河的程序，望共享

射天狼

<>有三位商人和三位仆人要过河，只有一条船，且每次最多载两人。若河任一岸仆人数多于商人数将会发生杀人越货。求安全过河的方法。</P>
<>本人曾试图用matlab求解，但经过一番努力没有做出结果，希望喜欢挑战的高手能指点一二，不胜感激。</P>

golden

我把思路贴出过，具体可以可以看看以前的贴子。有两种方法。ＭＡＴ最简单的方法是用最短路算法，就是一个状态可以变为另一个状态那么两个状态之间的距离为1。否则为无穷。用最短路算法直接求就行了。如果最短路算法不会的话可以在论谈里找一下，我记的是四等兄（等等等等）发的贴子吧。再不行就问老师要。要是老师不会就让他滚蛋。

射天狼

<>我看过一本参考书说可以用穷举法来解，但我编出的程序运算次数太多。<b><FONT color=#000066>golden</FONT></b> 大哥提到的帖子是在哪一版里呀？</P>[em04]

golden

看这个贴<a href="http://www.shumo.com/bbs/dispbbs.asp?BoardID=109&amp;ID=5012" target="_blank" >http://www.shumo.com/bbs/dispbbs.asp?BoardID=109&amp;ID=5012</A>

射天狼

<>不胜感激，我自己试试。</P>

射天狼

<>function [y,m,n]=go(A,m,n,y0)
for i=1:6
    for j=i+1:6
         B=A;
         B(i)=0;
         B(j)=0;
         if sum(B(1:3))&gt;sum(B(4:6))&amp;m~=i&amp;n~=j
             A=B;
             y=[y0 sum(A(1:3)) sum(A(4:6))];
             m=i;
             n=j;
             back(~A,m,n,y);
             return
         end
     end
end</P><>~~~~~~~~~~~~~~</P><>function [y,m,n,h]=back(A,m,n,y0)
for h=0:1
    for i=1:6
        for j=i+1:6
            B=A;
            B(i)=B(i)-1;
            B(j)=B(j)-h;
            if sum(B(1:3))&gt;sum(B(4:6))&amp;m~=i&amp;(n~=j|~h)&amp;sum(A)~0
                A=B;
                m=i;n=j;
                y=[y0 sum(~B(1:3)) sum(~B(4:6))]
                go(~A,m,n,y);
                return
            elseif  sum(A)==0
                return
            end
        end
    end
end
               
            ~~~~~~~</P><P>A=[1 1 1 1 1 1];
[x,m,n]=back(A,0,0,[])</P><P>还是不能运行</P><P>太郁闷了</P>[em03][em03][em03][em03][em03][em03][em03]

golden

看不懂程序

射天狼

<>就是两个函数分别表示过河（go）与返回（back），其中每个程序都用循环来实现每种可能的组合，并判断是否符合条件（条件是根据你那篇帖子编的），若符合就把结果记录在y[]中，（y矩阵结构是单数为商人数，偶数位是仆人数），然后调用返回函数。</P><>程序中的[y,m,n]   和[y,m,n,h]中m,n,h只是我调试不出后用来看其变化的没有实际用处。</P><>还有就是最后一组命令写错了应该是：</P><P>A=[1 1 1 1 1 1]%输入此岸初始的状态1：3是商人，4:6是仆人</P><P>[y,m,n]=go(A,0,0,[])%m,n用来记录是一次过河的人，商人或仆人</P>

射天狼

我觉得用的是递归的思想，不知道有什么毛病，怎么不能运行呀？

maquan_zhangjin

顶!