以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  过河问题[讨论]  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=33239)

--  作者：binaryluo
--  发布时间：5/29/2006 10:13:00 AM

--  过河问题[讨论]
题目：

有一条河，在河的左岸有3个人和3个野兽要过河。河里有一只船，该船每次最多可以装2个物体（人或兽）。在河两岸上如果人的数目小于兽的数目，人就被兽吃掉。请列出人和兽能安全过河所有方法。


[此贴子已经被作者于2006-5-29 10:38:33编辑过]
--  作者：binaryluo
--  发布时间：5/29/2006 10:19:00 AM

--  我的解决方法
算法分析：
将某一时刻河岸的整个状态抽象为一个结构体，而没一个状态会由下列5中情况派生出5个子状态：1个人过河，2个人过河，1个兽过河，2个兽过河，1个人和一个兽过河。对每一个子状态进行判断：如果左边和右边都有人，两边的人数必须分别大于等于两边的兽数；如果左边有人，右边没人，左边的人数必须大于左边兽数；如果左边没人，右边有人，右边的人数必须大于右边的兽数。

算法描述：
typedef struct _stNode {
 int hl, bl, hr, br;
} stNode;

bool humbst(stNode st, void (*opt)(stNode sm, FILE *fp), FILE *fp)
{
 bool rev = false;
 stNode st1, st2, st3, st4, st5;

 do
 {
  /*
   如果左边和右边都有人，两边的人数必须分别大于等于两边的兽数；
   如果左边有人，右边没人，左边的人数必须大于左边兽数；
   如果左边没人，右边有人，右边的人数必须大于右边的兽数。
  */
  if ((st.hl && (st.hl >= st.bl) && st.hr && (st.hr >= st.br))
   || (st.hl && st.hl >= st.bl && !st.hr)
   || (!st.hl && st.hr && st.hr >= st.br))
  {
   opt(st, fp); /* 显示合法状态 */
   rev = true;
   if (st.hl >= 1) /* 将左边的一个人运到右边 */
   {
    fprintf(fp, "load = one human\n", 0);
    st1.hl = st.hl - 1;
    st1.bl = st.bl;
    st1.hr = st.hr + 1;
    st1.br = st.br;
    st1.parent = &st;
    if (humbst(st1, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.hl >= 2) /* 将左边的两个人运到右边 */
   {
    fprintf(fp, "load = two human\n", 0);
    st2.hl = st.hl - 2;
    st2.bl = st.bl;
    st2.hr = st.hr + 2;
    st2.br = st.br;
    st2.parent = &st;
    if (humbst(st2, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.bl >= 1) /* 将左边的一个兽运到右边 */
   {
    fprintf(fp, "load = one beast\n", 0);
    st3.hl = st.hl;
    st3.bl = st.bl - 1;
    st3.hr = st.hr;
    st3.br = st.br + 1;
    st3.parent = &st;
    if (humbst(st3, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.bl >= 2) /* 将左边的两个兽运到右边 */
   {
    fprintf(fp, "load = two beast\n", 0);
    st4.hl = st.hl;
    st4.bl = st.bl - 2;
    st4.hr = st.hr;
    st4.br = st.br + 2;
    st4.parent = &st;
    if (humbst(st4, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }

   if (st.hl >= 1 && st.bl >= 1) /* 将左边的一个人一个兽运到右边 */
   {
    fprintf(fp, "load = one human and one beast\n", 0);
    st5.hl = st.hl - 1;
    st5.bl = st.bl - 1;
    st5.hr = st.hr + 1;
    st5.br = st.br + 1;
    st5.parent = &st;
    if (humbst(st5, opt, fp))
    {
     fprintf(fp, "\n", 0);
    }
   }
  }
 }while (false);

 return rev;
}

--  作者：binaryluo
--  发布时间：5/29/2006 10:35:00 AM

--  我的疑问
程序运行结果表明满足条件的渡河方案共有12种。

我现在的疑问就是会不会存在某种情况：有一个状态，该状态的左岸和右岸人兽数目满足限制条件，当从该状态的左岸继续运输到右岸时，该状态的任何子状态的人兽数目都不满足条件（兽的数目大于人的数目），但是通过先从该状态的右岸先运输到左岸，然后在继续从左岸运输到右岸则存在合法的解决方案。

因为在我的算法中我隐式地认为只能从左岸运东西到右岸，而不能右岸运东西到左岸。上面我有疑问的情况说通俗点就是会不会某个状态已经不满足条件，但是可以通过将刚才从左岸运过来的东西再回运（回运以后的子状态如果与该状态的父状态相同则不算），调整一下后继续操作也可以找出合理的解决方案。

例如：
S1->S2->S3，此时S3的某边的人数已经小于兽数，所以将S3的右边物体（人或兽）回运到左边得状态S4，且S2与S4不相同，从S4继续操作以后，成功找到一种解决方案：S1->S2->S3->S4->S5->S6……->Sn。

--  作者：phoenixinter
--  发布时间：5/29/2006 10:49:00 AM

--  
晕，这个就是一个图的遍历问题。
也就是说，两边的状态各看作图的节点
如果一个状态可以到另一个状态在节点之间连边
然后dfs一下
--  作者：Logician
--  发布时间：5/29/2006 11:34:00 AM

--  
“该状态的任何子状态的人兽数目都不满足条件”
如何定义“子状态”？
需要注意的是：船的位置（在哪侧）也是“状态”的一个组成部分。
--  作者：binaryluo
--  发布时间：5/29/2006 11:11:00 PM

--  
每个状态都可能对应5种子状态：
个人过河，2个人过河，1个兽过河，2个兽过河，1个人和一个兽过河。

我在做的过程中确实没考虑船的位置。

--  作者：Logician
--  发布时间：5/30/2006 1:53:00 AM

--  
考虑河的左岸，用（X,Y,Z）表示河左岸有X个人、Y个兽、Z条船。
则初始状态为（3,0,1），目标状态为（0，0，0）。
要注意到，（2，2，0）和（2，2，1）是两个相当不同的状态。


[此贴子已经被作者于2006-5-30 14:17:04编辑过]
--  作者：phoenixinter
--  发布时间：5/30/2006 6:48:00 AM

--  
嗯，Logician说的没错了。
--  作者：binaryluo
--  发布时间：5/30/2006 10:58:00 AM

--  
以下是引用Logician在2006-5-30 1:53:00的发言：
考虑河的左岸，用（X,Y,Z）表示河左岸有X个人、Y个兽、Z个人。
则初始状态为（3,0,1），目标状态为（0，0，0）。
要注意到，（2，2，0）和（2，2，1）是两个相当不同的状态。

Logician兄所说的(X,Y,Z)中X和Z都表示人，他们的区别是什么啊？

--  作者：Logician
--  发布时间：5/30/2006 2:16:00 PM

--  
不好意思，写错了，Z是船。Z=1表示船在左岸，Z=0表示船在右岸。
--  作者：binaryluo
--  发布时间：5/31/2006 9:49:00 AM

--  

"考虑河的左岸，用（X,Y,Z）表示河左岸有X个人、Y个兽、Z条船。"

Logician兄的意思是说不管Z为0(左)还是为1(右)，X和Y都是表示左岸的人与兽？还是说当Z为0时，X,Y表示左岸的人与兽，当Z为1时，X,Y表示右岸的人与兽？

--  作者：Logician
--  发布时间：5/31/2006 10:01:00 AM

--  
对，我的意思是：不管Z为0(左)还是为1(右)，X和Y都是表示左岸的人与兽。
(X,Y,Z)完全记录左岸的状态。
--  作者：binaryluo
--  发布时间：5/31/2006 1:44:00 PM

--  
以下是引用Logician在2006-5-31 10:01:00的发言：
对，我的意思是：不管Z为0(左)还是为1(右)，X和Y都是表示左岸的人与兽。
(X,Y,Z)完全记录左岸的状态。

如果是（2, 1, 0）——表示左边有2人1兽，此时右边是1兽2人。左边是满足限制的，但是右边不满足。所以，我觉得一个状态只保存左边的人与兽不是很理想，因为左右都需要判断，这就需要在根据左边的情况算出右边情况，比较麻烦。不如将右边的情况也添加到其中，（X,Y,U,V,Z）——X：左边人数，Y：左边兽数，U：右边人数，V：右边兽数，Z：船的位置。

--  作者：Logician
--  发布时间：5/31/2006 2:18:00 PM

--  
呵呵。加不加都可以。
右边的可以从左边推出来，所以约束条件可以写成：(X≥Y||X==0) && (X≤Y||X==3)。
你为了直观和方便，增加一点冗余当然也可以。
我的问题是，你定义的“子状态”到底是什么？在考虑了船的位置这个重要因素后，你的疑问是否还存在？
--  作者：binaryluo
--  发布时间：5/31/2006 9:18:00 PM

--  
我说的“子状态”其实就是当船从河的一边运输人兽到另一边后的河岸两边的人兽情况。
因为船的容量是2，所以船承载的物体有以下5种可能：
1人0兽
2人0兽
0人1兽
0人2兽
1人1兽
当然，是否都能够存在这5中情况应根据当前河岸上的人兽数以及船在的位置而定。
比如（用5元组表示）：
状态（3，3，0，0，0）中，当船从左岸移动到右岸后就可能产生下面5种子状态：
（2，3，1，0，1）、（1，2，2，0，1）、（3，2，0，1，1）、（3，1，0，2，1）、（2，2，1，1，1）
而新产生的子状态（3，2，0，1，1）中，当船从右岸移动到左岸后只可能产生下面一种子状态：
（3，3，0，0，0），其实也就是初始状态。
又如子状态（2，2，1，1，1）中，当船从右岸移动到左岸后可能产生以下3种子状态：
（3，2，0，1，0）、（2，3，1，0，0）、（3，3，0，0，0）
……

针对每一个状态，我递归地判断它是否满足人数大于等于兽数。还有，如果在子状态中出现以前出现过的重复状态（例如（3，2，0，1，1）产生（3，3，0，0，0）），则不对这种重复状态进行处理。

我现在重新实现了下，还在调试。应该是解决掉我的问题了。
等调通了我再将算法完整的写一下。^_^

--  作者：phoenixinter
--  发布时间：6/1/2006 8:18:00 AM

--  
说了dfs啊dfs……
--  作者：binaryluo
--  发布时间：6/1/2006 9:56:00 AM

--  
以下是引用phoenixinter在2006-6-1 8:18:00的发言：
说了dfs啊dfs……

如果你有好的想法，可以把它清晰、完整的表达出来。
不要这种空喊，没有意义啊。你空叫一个深度优先还不是没有人能够理解你是怎么想的，至少我不能。

--  作者：Logician
--  发布时间：6/1/2006 8:31:00 PM

--  
很简单啊。
看到“DFS”或“BFS”，心里自然要想到“树”或“图”。而把这个问题转化为图是一个简单而显然的过程：
把(X,Y,Z)的每种可行的取值组合看作一个顶点，把状态的转换看作边。
则所有可能出现的状态和它们之间的转换就构成了一个图。
从初始状态(3,3,1)开始，作DFS或BFS，直到遍历到(0,0,0)就可以了。
用BFS可以确保找到最优解（即运送次数最少的解）。
实现也是显然的，前面已经给出了可行状态的判定条件（它可以进一步简化为：X==Y||X==3||X==0），状态转换的条件也很好写。其余的就是图的DFS和BFS遍历算法的基本套路了。
--  作者：binaryluo
--  发布时间：6/2/2006 9:37:00 AM

--  
以下是引用Logician在2006-6-1 20:31:00的发言：
很简单啊。
看到“DFS”或“BFS”，心里自然要想到“树”或“图”。而把这个问题转化为图是一个简单而显然的过程：
把(X,Y,Z)的每种可行的取值组合看作一个顶点，把状态的转换看作边。
则所有可能出现的状态和它们之间的转换就构成了一个图。
从初始状态(3,3,1)开始，作DFS或BFS，直到遍历到(0,0,0)就可以了。
用BFS可以确保找到最优解（即运送次数最少的解）。
实现也是显然的，前面已经给出了可行状态的判定条件（它可以进一步简化为：X==Y||X==3||X==0），状态转换的条件也很好写。其余的就是图的DFS和BFS遍历算法的基本套路了。

那就是说先要构建人兽数的“状态变迁图”，然后再用dfs来遍历该图？也就是说现在dfs已经是现成的了，只需要实现该“状态变迁图”的构建就可以了。

其实我觉得自己的想法应该也是可行的。只是现在写出的递归可能是把什么特殊情况被遗漏了而发生了死循环，会出现“栈区溢出”的错误。这两天都在调：（

--  作者：Logician
--  发布时间：6/2/2006 5:32:00 PM

--  
“状态变迁图”并不用显式的给出呀，从当前状态动态生成就可以了。
你以前用没有试过用BFS/DFS求解问题吗？
比如现在的状态是(X,Y,1)，你可以算出，从它能直接到达哪些状态（即，那些Z'=0，min(0,X-2)<=X'<=X，min(0,Y-2)<=Y'<=Y，min(0,X+Y-2)<=X'+Y'<X+Y的状态(X',Y',Z')，同理可以算出若当前状态是(X,Y,0)，下一步有哪些可行的状态。对每一个可以到达的状态，作两种检查：一是它是否是合法状态（人不少于兽），二是它是否以前检查过（检查过就不在检查了，以免死循环）。
这实际上就是BFS/DFS的基本思想，也是大多数此类求解问题算法的基本思路。
你的方法本质上也是生成了这样的一个“状态变迁图”，只不过因为你没有区分船的问题，所以把两种不同的状态看成了一种，同时，没有使用BFS/DFS的思路，所以难以避免出现死循环（比如程序可能会不断地循环搜索(3,3,1)->(2,2,0)->(3,3,1)->(2,2,0)->....这样的路线）。

--  作者：binaryluo
--  发布时间：6/3/2006 8:29:00 AM

--  
终于可以了：）
原来是判断递归结束的四个if语句中，有一句的一个变量名写错了。


typedef struct _stNode {
 int hl, bl, hr, br;
 pos bp;     /* boat position */
 struct _stNode *parent;
} stNode;

bool humbst(stNode st, FILE *fp, void (*opt)(stNode sm, void *fp))
{
 bool rev = false;

 do
 {
  /* 该状态与初始状态相同的情况不操作 */
  if (st.hl == N && st.bl == N && st.hr == 0 &&
   st.br == 0 && st.bp == left && st.parent != NULL)
   break;

  /* 该状态与祖父状态相同的情况不操作 */
  if (st.parent != NULL && st.parent->parent != NULL)
  {
   if ((st.hl == st.parent->parent->hl)
    && (st.bl == st.parent->parent->bl)
    && (st.hr == st.parent->parent->hr)
    && (st.br == st.parent->parent->br)
    && (st.bp == st.parent->parent->bp))
    break;
  }

  /* 人数小于兽数的时候不满足 */
  if ((st.hl != 0 && st.hr != 0 && (st.hl < st.bl || st.hr < st.br))
   || (st.hl != 0 && st.hr == 0 && st.hl < st.bl)
   || (st.hl == 0 && st.hr != 0 && st.hr < st.br))
   break;

  /* 中止状态 */
  if (st.hl == 0 && st.bl == 0 && st.hr == N &&
   st.br == N && st.bp == right)
  {
   opt(st, fp);
   rev = true;
   break;
  }

  /* 正常情况 */
  opt(st, fp);
  switch (st.bp)
  {
  case left:
   rev = humbst_left(st, fp, stDisp);
   break;

  case right:
   rev = humbst_right(st, fp, stDisp);
   break;
  }
 } while (false);

 return rev;
}

bool humbst_left(stNode st, FILE *fp, void (*opt)(stNode sm, FILE *fp))
{
 bool rev = false;
 stNode st1, st2, st3, st4, st5;

 if (st.hl >= 1) /* 将左边的一个人运到右边 */
 {
  st1.hl = st.hl - 1;
  st1.bl = st.bl;
  st1.hr = st.hr + 1;
  st1.br = st.br;
  st1.bp = right;
  st1.parent = &st;
  rev = humbst(st1, fp, opt);
 }

 if (st.hl >= 2) /* 将左边的两个人运到右边 */
 {
  st2.hl = st.hl - 2;
  st2.bl = st.bl;
  st2.hr = st.hr + 2;
  st2.br = st.br;
  st2.bp = right;
  st2.parent = &st;
  rev = humbst(st2, fp, opt);
 }

 if (st.bl >= 1) /* 将左边的一个兽运到右边 */
 {
  st3.hl = st.hl;
  st3.bl = st.bl - 1;
  st3.hr = st.hr;
  st3.br = st.br + 1;
  st3.bp = right;
  st3.parent = &st;
  rev = humbst(st3, fp, opt);
 }

 if (st.bl >= 2) /* 将左边的两个兽运到右边 */
 {
  st4.hl = st.hl;
  st4.bl = st.bl - 2;
  st4.hr = st.hr;
  st4.br = st.br + 2;
  st4.bp = right;
  st4.parent = &st;
  rev = humbst(st4, fp, opt);
 }

 if (st.hl >= 1 && st.bl >= 1) /* 将左边的一个人一个兽运到右边 */
 {
  st5.hl = st.hl - 1;
  st5.bl = st.bl - 1;
  st5.hr = st.hr + 1;
  st5.br = st.br + 1;
  st5.bp = right;
  st5.parent = &st;
  rev = humbst(st5, fp, opt);
 }

 return rev;
}

bool humbst_right(stNode st, FILE *fp, void (*opt)(stNode sm, FILE *fp))
{
 bool rev = false;
 stNode st1, st2, st3, st4, st5;

 if (st.hr >= 1) /* 将右边的一个人运到左边 */
 {
  st1.hl = st.hl + 1;
  st1.bl = st.bl;
  st1.hr = st.hr - 1;
  st1.br = st.br;
  st1.bp = left;
  st1.parent = &st;
  rev = humbst(st1, fp, opt);
 }

 if (st.hr >= 2) /* 将右边的两个人运到左边 */
 {
  st2.hl = st.hl + 2;
  st2.bl = st.bl;
  st2.hr = st.hr - 2;
  st2.br = st.br;
  st2.bp = left;
  st2.parent = &st;
  rev = humbst(st2, fp, opt);
 }

 if (st.br >= 1) /* 将右边的一个兽运到左边 */
 {
  st3.hl = st.hl;
  st3.bl = st.bl + 1;
  st3.hr = st.hr;
  st3.br = st.br - 1;
  st3.bp = left;
  st3.parent = &st;
  rev = humbst(st3, fp, opt);
 }

 if (st.br >= 2) /* 将右边的两个兽运到左边 */
 {
  st4.hl = st.hl;
  st4.bl = st.bl + 2;
  st4.hr = st.hr;
  st4.br = st.br - 2;
  st4.bp = left;
  st4.parent = &st;
  rev = humbst(st4, fp, opt);
 }

 if (st.hr >= 1 && st.br >= 1) /* 将右边的一个人一个兽运到左边 */
 {
  st5.hl = st.hl + 1;
  st5.bl = st.bl + 1;
  st5.hr = st.hr - 1;
  st5.br = st.br - 1;
  st5.bp = left;
  st5.parent = &st;
  rev = humbst(st5, fp, opt);
 }

 return rev;
}


humbest函数其实就是构造一个状态变迁图（树），然后用opt函数来对该图进行操作（比如说dfs）。在此衷心感谢Logician和phoenixinter热心参与讨论，你们的想法给了我很多提示。^_^

--  作者：binaryluo
--  发布时间：6/3/2006 8:39:00 AM

--  
以下是引用Logician在2006-6-2 17:32:00的发言：
“状态变迁图”并不用显式的给出呀，从当前状态动态生成就可以了。
你以前用没有试过用BFS/DFS求解问题吗？
比如现在的状态是(X,Y,1)，你可以算出，从它能直接到达哪些状态（即，那些Z'=0，min(0,X-2)<=X'<=X，min(0,Y-2)<=Y'<=Y，min(0,X+Y-2)<=X'+Y'<X+Y的状态(X',Y',Z')，同理可以算出若当前状态是(X,Y,0)，下一步有哪些可行的状态。对每一个可以到达的状态，作两种检查：一是它是否是合法状态（人不少于兽），二是它是否以前检查过（检查过就不在检查了，以免死循环）。
这实际上就是BFS/DFS的基本思想，也是大多数此类求解问题算法的基本思路。
你的方法本质上也是生成了这样的一个“状态变迁图”，只不过因为你没有区分船的问题，所以把两种不同的状态看成了一种，同时，没有使用BFS/DFS的思路，所以难以避免出现死循环（比如程序可能会不断地循环搜索(3,3,1)->(2,2,0)->(3,3,1)->(2,2,0)->....这样的路线）。


我以前只是实现过DFS和BFS，并没有用图的DFS和BFS解决过实际问题。谢谢你的详细讲解：）
我看了你说的才发觉其实我想的跟你说的也就是一个意思，只是原先我没有意识到我想的跟你说的也就是一个意思。
真的很高兴能够在这个论坛上认识你们。

--  作者：Logician
--  发布时间：6/3/2006 12:09:00 PM

--  
呵呵。：）
--  作者：doubleman
--  发布时间：6/5/2006 1:05:00 AM

--  
用（L,LH,LB）表示河左岸人的数数目为LH，兽的数目为LB,，用（R,RH,RB）表示河右岸人的数数目为RH，兽的数目为RB。约束条件是：LH>=LB并且RH>=RB。定义下面的一些算符：A1(表示一个人和一只兽从河的左岸到右岸)，A2(表示一个人和一只兽从河的右岸到左岸)，A3(表示两个人从河的左岸到右岸)，A4(表示两只兽从河的左岸到右岸)。这样初始状态为(L,3,3)，(R,0,0)，目标状态为(L,0,0)，(R,3,3)。运用广度优先或者深度优先搜索算法就可以搞定啦。具体实现可以用PROLOG语言来做到。

--  作者：wanghuicn2008
--  发布时间：7/1/2006 4:51:00 PM

--  
我觉得也是图的遍历，考虑船在哪一侧，主要是状态之间的转换，题目没仔细看，主要是若两个都可行，那么就要考虑这两个状态之间转换可能性的问题了，具体来说就是连边的可能性
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 250.000ms