学informatik的人进来

laopo

变态一下，考考大家

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

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

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

谁能给出？biggrin.gi

laopo

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

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

laopo

第2步是核心的一步

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

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

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

laopo

这个问题 我觉得是个 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 ]

laopo

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

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