新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 算法理论与分析 』 → 过河问题[讨论] ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 29209 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 过河问题[讨论] 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第11楼
    发贴心情 


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

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 9:49:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第12楼
    发贴心情 
    对，我的意思是：不管Z为0(左)还是为1(右)，X和Y都是表示左岸的人与兽。
    (X,Y,Z)完全记录左岸的状态。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 10:01:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第13楼
    发贴心情 
    以下是引用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：船的位置。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 13:44:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第14楼
    发贴心情 
    呵呵。加不加都可以。
    右边的可以从左边推出来，所以约束条件可以写成：(X≥Y||X==0) && (X≤Y||X==3)。
    你为了直观和方便，增加一点冗余当然也可以。
    我的问题是，你定义的“子状态”到底是什么？在考虑了船的位置这个重要因素后，你的疑问是否还存在？

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 14:18:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第15楼
    发贴心情 
    我说的“子状态”其实就是当船从河的一边运输人兽到另一边后的河岸两边的人兽情况。
    因为船的容量是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）），则不对这种重复状态进行处理。

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/5/31 21:18:00
     
     phoenixinter 帅哥哟，离线，有人找我吗？水瓶座1987-2-12
      
      
      威望：1
      头衔：Ikki
      等级：大四(GRE考了1600分!)(版主)
      文章：127
      积分：1126
      门派：Lilybbs.net
      注册：2005/3/14

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给phoenixinter发送一个短消息 把phoenixinter加入好友 查看phoenixinter的个人资料 搜索phoenixinter在『 算法理论与分析 』的所有贴子 点击这里发送电邮给phoenixinter  引用回复这个贴子 回复这个贴子 查看phoenixinter的博客第16楼
    发贴心情 
    说了dfs啊dfs……

    ----------------------------------------------
    phoenixinter
    algorithm bm@lilybbs
    ikki@poj

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/6/1 8:18:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第17楼
    发贴心情 
    以下是引用phoenixinter在2006-6-1 8:18:00的发言：
    说了dfs啊dfs……

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/6/1 9:56:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第18楼
    发贴心情 
    很简单啊。
    看到“DFS”或“BFS”，心里自然要想到“树”或“图”。而把这个问题转化为图是一个简单而显然的过程：
    把(X,Y,Z)的每种可行的取值组合看作一个顶点，把状态的转换看作边。
    则所有可能出现的状态和它们之间的转换就构成了一个图。
    从初始状态(3,3,1)开始，作DFS或BFS，直到遍历到(0,0,0)就可以了。
    用BFS可以确保找到最优解（即运送次数最少的解）。
    实现也是显然的，前面已经给出了可行状态的判定条件（它可以进一步简化为：X==Y||X==3||X==0），状态转换的条件也很好写。其余的就是图的DFS和BFS遍历算法的基本套路了。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/6/1 20:31:00
     
     binaryluo 帅哥哟，离线，有人找我吗？
      
      
      威望：6
      等级：研二(Pi-Calculus看得一头雾水)(版主)
      文章：679
      积分：5543
      门派：IEEE.ORG.CN
      注册：2005/2/19

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给binaryluo发送一个短消息 把binaryluo加入好友 查看binaryluo的个人资料 搜索binaryluo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看binaryluo的博客第19楼
    发贴心情 
    以下是引用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已经是现成的了，只需要实现该“状态变迁图”的构建就可以了。

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

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/6/2 9:37:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第20楼
    发贴心情 
    “状态变迁图”并不用显式的给出呀，从当前状态动态生成就可以了。
    你以前用没有试过用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)->....这样的路线）。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/6/2 17:32:00
     
     GoogleAdSense天蝎座1984-10-28
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 点击这里发送电邮给Google AdSense  访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2025/9/8 4:16:57

    本主题贴数25，分页： [1] [2] [3]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 109.375ms