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

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL → 计算机理论与工程 → 『 算法理论与分析 』 → 请问如何求有向图的最长无环路? ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 22685 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 请问如何求有向图的最长无环路? 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

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

    Ｆｌｏｙｄ写的起点，终点未指定的算法：
    void Floyd_LongestPath(Graph G,Dist **&D)
    {
    int i,j,v;  
    D=new Dist *[G.VerticesNum()];  
    for(i=0;i< G.VerticesNum();i++)
    D[i]=new Dist[G.VerticesNum()]; 
    for(i=0;i< G.VerticesNum();i++){
    for(j=0;j< G.VerticesNum();j++){
    if(i==j)D[i][j].length=0;
    elseD[i][j].length=MinusINFINITY;
    }
    }
    for(v=0;v< G.VerticesNum();v++)
    {
    for(Edge e=G.FirstEdge(v);G.isEdge(e)e=G.NextEdge(e))
    Ｄ［ｖ］［Ｇ．ＴｏＶｅｒｔｅｘ（ｅ）］．ｌｅｎｇｔｈ＝１；
    }
    for(v=0;v< G.VerticesNum();v++)
    for(i=0;i< G.VerticesNum();i++)
    for(j=0;j< G.VerticesNum();j++)
    {
    if((D[i][j].length== MinusINFINITY||Ｄ［ｉ］［ｊ］．ｌｅｎｇｔｈ＜Ｄ［ｉ］［ｖ］．ｌｅｎｇｔｈ＋Ｄ［ｖ］［ｊ］．ｌｅｎｇｔｈ)
    {
    Ｄ［ｉ］［ｊ］．ｌｅｎｇｔｈ＝Ｄ［ｉ］［ｖ］．ｌｅｎｇｔｈ＋Ｄ［ｖ］［ｊ］．ｌｅｎｇｔｈ
    }
    }
    ｝
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/30 12:23: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楼
    发贴心情 
    你直接把最短路的算法改造成求最长路的？
    请论证一下：为什么它求出来的就是最长路？

    ----------------------------------------------
    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/7/30 14:56:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

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

    如果是不考虑圈，因为Floyd算法遍历了所有的路，如要求v1，v2间的最长路。Floyd算法探索了所有从v1到v2的路，进而从中间选出来一条最长的。

    如果这条最长的路含有圈。。需要删除这条路，从新作Floyd搜索。。这个删除过程我认为也是有回溯的。。很复杂。。。

    Dijkstra算法需要改进为遍历每一条边，即总循环次数由VerticesNum改为EdgesNum，即先前点的标注改为边的标注，并且每一条边的两个端点都是需要检测的，此时可求。

    如果考虑圈。。。太复杂了。。。。

    能不能对图预处理？把有圈图变成无圈图？例如把圈中一个顶点分成2个？
    单从有圈图的角度考虑，太复杂了。。。


    [此贴子已经被作者于2006-7-30 19:27:57编辑过]
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/30 18:14: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楼
    发贴心情 
    虽然任何一本算法/计算理论书上都有讲过“最长路是NPC”（从而间接证明了你的算法是错误的），不过我在这里还是给你一个直接的反例：

    “对于两点v1，v2，若求得的最长路上有v3，则v1，v3是v1到v3的最长路；v3，v2是v3到v2的最长路。”这个命题是错误的。
    考虑这样一个图：
    A ------H
    |       |
    B       |
    |       |
    C       |
    |       |
    D - I - J
    |       |
    E       |
    |       |
    F       |
    |       |
    G ----- K
    假定每条边的权都是1（从而这个反例对有权图和无权图都有效），那么A到G的最长路有两条：AHJIDEFG 和 ABCDIJKG，其中都含有顶点D，但这两条路中，前一条中不含从A到D的最长路(AHJID)，后一条中不含从D到G的最长路(DIJKG)。从而像Dijkstra算法那样先求局部最长路，然后连接起来的方法是不可行的。

    关于“最长路问题是NPC问题”的论述，参见Garey和Johnson的Computer And Intractability - A Guide To The Theory Of NP-Completeness（http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=36231 有电子版下载）第213页（电子书中的第112个页面）：[ND29] Longest Path。

    ----------------------------------------------
    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/7/30 19:26:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第15楼
    发贴心情 
    你说的有理，我也想到了，这句话应该这样说：对于两点v1，v2，若求得的最长路上有v3，则（1）v1，v3是v1到v3的最长路；（2）v3，v2是v3到v2的最长路
    这两个中间至少有一个成立。

    只听过NP，不知道啥叫NPC，这个题：
    如果是无圈图，则（1）（2）同时成立，D，F在这里都可以用。
    如果是有圈图，感觉算法异常复杂，甚至是回溯都不能很好解决的。所以我认为出路只有变有圈为无圈，或寻求一些局部求解

    请问书上说的这个题的方法是什么？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/30 19: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的博客第16楼
    发贴心情 
    很对，如果是无圈图，有简单的解法。如果不是无圈图，那么就很难，所以一般情况下（即不保证无圈时）不可能用Floyd来做。

    那本书上证明了这个问题是NPC问题。

        NPC，即NP Complete。简单地来说，NPC问题是这样一类问题：
        首先，这些问题都是NP的。即，假设你提供给我无穷多台计算机，让它们同时工作，来解决这个问题，那么我可以轻易地在多项式时间里找到解，所谓多项式时间，就是它的时间增长速度不超过n的某个幂次，其中n是输入的规模，例如在这里，n就是输入的图顶点数。
        其次，如果这些问题中有任何一个问题是P问题（即，能用一台普通的计算机在多项式时间内解决），那么其它所有的NP问题（包括所有的NPC问题）都能用一台普通的计算机在多项式时间内解决。

        典型的NPC问题有：TSP（旅行商问题）、SAT（命题逻辑公式的可满足性问题）、哈密顿图问题（即，判定一个给定的图中是否有Hamilton回路）、哈密顿路问题（即，判定一个给定的图中是否有Hamilton通路）等。
        这些问题都被认为是很“难”的问题，因为多年来一直没人能找到解决这些问题的多项式时间算法。如果证明了一个问题是NPC的，就意味着证明了这个问题与上述那些“难”题一样“难”。因为如果一个问题是NPC的，而你在多项式时间内解决了它，就意味着你能在多项式时间内解决上述所有问题。鉴于一直没人能找到上述问题的多项式时间解，当你证明了一个问题是NPC时，就意味着你证明了：至今为止，这世上还没有人能在多项式时间内解决它。
        而Dijstra算法的时间复杂度是O(n^2)，Floyd算法的时间复杂度是O(n^3)，它们都是众人熟知的多项式时间算法。所以只要证明了“最长路问题是NPC”，就意味着上述算法肯定不能用（否则早就有人用它解决了TSP等问题了）。

        如果想知道更多有关NPC的内容，就看我前面提到的那本书吧。那是关于NPC问题的经典著作。

    ----------------------------------------------
    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/7/30 20:28:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第17楼
    发贴心情 
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/7/30 20:39:00
     
     baochens 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：2
      积分：68
      门派：XML.ORG.CN
      注册：2005/10/18

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给baochens发送一个短消息 把baochens加入好友 查看baochens的个人资料 搜索baochens在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看baochens的博客第18楼
    发贴心情 
    NPC problem...
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/4/17 22:18:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/4/27 13:27:24

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

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