谁会人狼羊菜渡河问题的，请进来帮帮忙！

cathy_yi

谁会人狼羊菜渡河问题的，请帮帮忙！

人把狼，羊，菜都运到对岸，由于船小，每次只能运一样，并且无人在时，狼和羊不能共存，羊和菜不能共存！

求解决此问题的最佳方案，即求出最短路径！
最好用c语言！

谢谢！

[em12][em12][em12][em12][em05]

cathy_yi

请问是哪的数据结构啊？

HUASHI3483

渡河问题

有三个人捕获了三只熊，送往动物园。路遇一条河，河中又只有 一只摆渡的小船。这条小船每次只能乘两个人或两只熊或一人一熊。三个人和一只老熊会划船，两只小熊不会划船。三人商定，为了 安全，不能让一个人与两只熊同时在河的一边。

　　问:如何利用这一条船安全地渡过河呢?

渡河问题

经过试验，有这样一种渡法。当然还有别的渡法。

　　1·一人带一只小熊过河;

　　2·留下小熊后，那人独自返回;

　　3.让老熊带一只小熊过河;

　　4·留下另一只小熊后，老熊独自返回;

　　5·老熊留下，让两人同时过河;

　　6·留下一人，让一人带一只小熊返回;

　　7·留下小熊，让一人带老熊过河;

　　8·留下老熊后，由一人带一只小熊返回;

　　9·留下两只小熊后，两人又同时渡河;

　　10·三人都留在对岸，由老熊独自返回;

　　11·老熊带一只小熊过河;

　　12·留下小熊后，老熊独自返回;

　　13·最后，由老熊带另一只小熊过河。

　　经过13次往返后，这三个人带着三只熊总算安全地渡过了河。

　　这种渡河问题，不管是简单的，还是复杂的，用船的次数必须是奇数次。这是因为一来一回，相加为2，无论多少次来回，其和总是偶数;而最后一次是只有 "过去"没有"回来"，所以用船的次数必须是奇数。假如我们用试验的办法来解决渡河问题，只有得出奇数次 才有可能是正确的，若是偶数次那就肯定错了。

HUASHI3483

商人们怎样安全过河？                问题提出 模型建立 模型求解 游戏演示 请你思考 请您探索
模型建立
   
   此问题可视为一个 多步决策    多步决策:决策过程难以一次完成，而要分步优化，最后获取一个全局最优方案的决策方法称为多步决策。
问题，每一步就是一次渡河，
   每次渡河就是一次状态转移。
   用三维变量表示状态：
         ------商人数
         ------随从数    ,的取值范围；{0，1，2，3}
         ------船       的取值范围：{0,1}
   那么安全状态可表示为：
        安全状态：商人们安全是指在两岸都安全，故当x=0,3时，y=0,1,2,3，而当x=1,2时,此岸要求x≥y,对岸要求3-x≥3-y,综合即x=y  

(3,3,1) (3,2,1) (3,1,1) (2,2,1) (3,0,1) (0,3,1) (0,2,1) (1,1,1) (0,1,1)
(3,2,0) (3,1,0) (2,2,0) (3,0,0) (0,3,0) (0,2,0) (1,1,0) (0,1,0) (0,0,0)
    这就是此问题的数学模型。

HUASHI3483

模型求解\另一解法(状态平面分析)
      
      我们用线表示决策,此线将决策前后两个状态相连
     (本题中每一步决策都是可逆的，故线没有方向。)
        线————决策


        
        —————状态

这样问题要求由(3，3，1)变到(0，0，0)的一条道路。

     根据题意，状态转移时要满足一定的规则：
1.Z从1变为0与从0变为1交替进行；
2.当Z从1变为0时，即船从此岸到对岸，此岸人数减少1或2个；
   即(x,y,1)→(u,v,0)时, u≤x, v≤y, u+v=x+y-1 or u+v=x+y-2
3.当Z从0变为1时，即船从对岸到此岸，此岸人数增加1或2个；
   即(x,y,0)→(u,v,1)时, u≥x, v≥y,u+v=x+y+1 or u+v=x+y+2
4.不重复已出现过的状态，如(3,3,1)→(3,1,0)→(3,3,1)；

HUASHI3483

RIVER.PAS
program river2;
type
a=record pre,manL,womanL,boat:integer;end;
var
ar:array[1..2000] of a;
head,tail:integer;
man,woman,bot:integer;
en:boolean;
procedure out;
   var
   ti:integer;
   begin
   ti:=tail;
   while ti<>0 do begin
           writeln(ar[ti].manL:3,ar[ti].womanL:3,ar[ti].boat:2);
      ti:=ar[ti].pre;
      end;
   end;
procedure init;
        begin
   read(man,woman,bot);
   head:=1;
   tail:=1;
   ar[1].manL:=man;ar[1].womanL:=woman;ar[1].boat:=1;
   ar[1].pre:=0;
   en:=false;
   end;
procedure expand(id:integer);
   var
   i,j,k:integer;
   tmp:a;
   begin
   if ar[id].boat=2 then begin
           tmp.manL:=man-ar[id].manL;
      tmp.womanL:=woman-ar[id].womanL;
      end
   else tmp:=ar[id];
   for i:=0 to tmp.manL do
           for j:=0 to tmp.womanL do
              if (i+j<>0)and(i+j<=bot)and((j>=i)or(j=0))and((tmp.manL-i<=tmp.womanL-j)or(tmp.womanL-j=0))
                                and((3-tmp.manL+i<=3-tmp.womanL+j)or(3-tmp.womanL+j=0))then begin
                 tail:=tail+1;
            ar[tail].pre:=id;
            ar[tail].manL:=tmp.manL-i;
            ar[tail].womanL:=tmp.womanL-j;
            ar[tail].boat:=3-ar[id].boat;
            if ar[id].boat=2 then begin
                                   ar[tail].manL:=man-ar[tail].manL;
                              ar[tail].womanL:=woman-ar[tail].womanL;
                      end;
            for k:=1 to tail-1 do
                    if (ar[k].manL=ar[tail].manL)and(ar[k].womanL=ar[tail].womanL)
                       and(ar[k].boat=ar[tail].boat) then begin
                          tail:=tail-1;
                     break;
                     end;
            if ar[tail].manL+ar[tail].womanL=0 then begin
                    en:=true;
               out;
               exit;
            end;
         end;
   end;
begin
init;
while en=false do begin
        expand(head);
   head:=head+1;
   end;
end.

math618

商人安全过河问题

http://col.njtu.edu.cn/zskj/2023/sm00/FLASH/202.swf

cathy_yi

以下是引用HUASHI3483在2004-2-21 10:47:50的发言：
RIVER.PAS
program river2;
type
a=record pre,manL,womanL,boat:integer;end;
var
ar:array[1..2000] of a;
head,tail:integer;
man,woman,bot:integer;
en:boolean;
procedure out;
    var
    ti:integer;
    begin
    ti:=tail;
    while ti<>0 do begin
     writeln(ar[ti].manL:3,ar[ti].womanL:3,ar[ti].boat:2);
       ti:=ar[ti].pre;
       end;
    end;
procedure init;
  begin
    read(man,woman,bot);
    head:=1;
    tail:=1;
    ar[1].manL:=man;ar[1].womanL:=woman;ar[1].boat:=1;
    ar[1].pre:=0;
    en:=false;
    end;
procedure expand(id:integer);
    var
    i,j,k:integer;
    tmp:a;
    begin
    if ar[id].boat=2 then begin
     tmp.manL:=man-ar[id].manL;
       tmp.womanL:=woman-ar[id].womanL;
       end
    else tmp:=ar[id];
    for i:=0 to tmp.manL do
     for j:=0 to tmp.womanL do
        if (i+j<>0)and(i+j<=bot)and((j>=i)or(j=0))and((tmp.manL-i<=tmp.womanL-j)or(tmp.womanL-j=0))
     and((3-tmp.manL+i<=3-tmp.womanL+j)or(3-tmp.womanL+j=0))then begin
           tail:=tail+1;
             ar[tail].pre:=id;
             ar[tail].manL:=tmp.manL-i;
             ar[tail].womanL:=tmp.womanL-j;
             ar[tail].boat:=3-ar[id].boat;
             if ar[id].boat=2 then begin
        ar[tail].manL:=man-ar[tail].manL;
          ar[tail].womanL:=woman-ar[tail].womanL;
         end;
             for k:=1 to tail-1 do
              if (ar[k].manL=ar[tail].manL)and(ar[k].womanL=ar[tail].womanL)
                 and(ar[k].boat=ar[tail].boat) then begin
                    tail:=tail-1;
                      break;
                      end;
             if ar[tail].manL+ar[tail].womanL=0 then begin
              en:=true;
                out;
                exit;
             end;
          end;
    end;
begin
init;
while en=false do begin
  expand(head);
    head:=head+1;
    end;
end.

不好意思~~这段程序我看明白啊~~是不是TC啊？
麻烦你帮我写一份人狼羊的程序好吗？？谢谢了~~

HUASHI3483

对不起，这要靠自己，我只是给出了一个样本

aysten

我是用图做的。动态规划求最短路。