人在德国社区 - Powered by Discuz! Board

标题: 学informatik的人进来 [打印本页]

作者: laopo 时间: 2004-12-15 14:58 标题: 学informatik的人进来

变态一下，考考大家

关于成语接龙的最长解法的问题：

给出一个集合 P，定义它为一个包含 n 个成语的集合，并且假定其所有 n 个成语互不相同。

试给出一个有效的算法，能决定这 n 个成语的最长接龙 S(P).

谁能给出？biggrin.gi

作者: 班超 时间: 2004-12-15 21:27 标题: 算法，瞎弄，别笑

提示: 作者被禁止或删除内容自动屏蔽

作者: laopo 时间: 2004-12-16 11:20

第1步，明白。
第2步，每个成语为树根, 初始化n棵树，是什么意思？

第四步输出时，为什么是整棵树？

作者: 班超 时间: 2004-12-16 12:38 标题: 不好意思

提示: 作者被禁止或删除内容自动屏蔽

作者: laopo 时间: 2004-12-16 13:54

第2步是核心的一步

你所说“按此原则不断向下延伸，直到没有可能后停止”
的“没有可能” 具体是什么情况

因为有可能，部分成语组成若干个环状

A**D -> D**N -> N**Q -> Q**A

作者: 班超 时间: 2004-12-16 14:55 标题: 对，

提示: 作者被禁止或删除内容自动屏蔽

作者: laopo 时间: 2004-12-20 10:26

这个问题我觉得是个 spanning tree 的问题，应该可以在polynomial time内解决
即，1个含有n个节点的Graph，对其任意2个节点进行：
1.建立从节点i 到节点j 的路径：如果节点1的尾＝节点2的首，for all i ,j =1..n and i<>j
2.不建立路径：反之

然后，在此Graph上寻找一条路径，尽可能多地包含节点，并且不重复。

p.s.这个问题我是从生物计算机里的Superstring 问题想到的。

[ Last edited by laopo on 2004-12-20 at 11:37 ]

作者: 班超 时间: 2004-12-20 12:15 标题: 好啊,

提示: 作者被禁止或删除内容自动屏蔽

作者: laopo 时间: 2004-12-20 13:12

然后，
深度优先，遍历整个Graph

假定 n = 所有节点的数量 , V = 所有路径数量
遍历整个Graph 应该是 O(n*ld(V))

欢迎光临人在德国社区 (http://rs238848.rs.hosteurope.de/bbs/)