学informatik的人进来

变态一下,考考大家

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

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

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


谁能给出?biggrin.gi
原用户名密码丢失,现在换马甲。
Share |
Share

算法,瞎弄,别笑

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

TOP

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

第四步输出时,为什么是整棵树?
原用户名密码丢失,现在换马甲。

TOP

不好意思

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

TOP

第2步是核心的一步

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

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

A**D -> D**N -> N**Q -> Q**A
原用户名密码丢失,现在换马甲。

TOP

对,

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

TOP

这个问题 我觉得是个 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 ]
原用户名密码丢失,现在换马甲。

TOP

好啊,

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

TOP

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

假定 n = 所有节点的数量 , V = 所有路径数量
遍历整个Graph 应该是 O(n*ld(V))
原用户名密码丢失,现在换马甲。

TOP