[合集] 请教一道赛题：遗传基因

发信人: RoBa269 (弱吧), 信区: Algorithm

标题: [合集] 请教一道赛题：遗传基因

发信站: 水木社区 (Fri Jul 25 12:25:18 2008), 站内

☆─────────────────────────────────────☆

nullspace (潜水使人进步，灌水使人落后) 于 (Sat Jul 19 19:20:00 2008) 提到:

这题只大概的知道可以用有向图描述，但具体算法没有思路。

请提示一下应该用什么方法，有没有简化的办法？

问题描述：有这样一段遗传基因K，它是由一系列的自然数组成：K=a1,a2,a3,a4……am。在

该段基因中，连续的两个自然数被称做它的“特征”。

例如对基因段：8, 5, 1, 4, 2, 3

(5,1)就是它的“特征”之一，而(4,3)则不是。

L教授正在研究这样一段长度未知的奇特基因段，并且已经成功地分析出了该基因段的大多

数“特征”。

现在，他想根据自己当前的研究成果，确定这段基因最少有多长，你能帮助他么？

Input

第一行有一个数N(1<=N<=1000)，表示“特征”的总数。以下有N行，每行有两个互不相同的

整数（在[0,1000]内），表示一个特征。

Output

输出只有一行只有一行，一个数，表示基因段的最短长度。

Sample Input

2 3

3 9

9 6

8 5

5 7

7 6

4 5

5 1

1 4

4 2

2 8

8 6

Sample Output

Hint

对于样例，最短的遗传基因段可能是：(8, 5, 1, 4, 2, 3, 9, 6, 4, 5, 7, 6, 2, 8, 6)

，长度为15。

☆─────────────────────────────────────☆

ArXoR (…) 于 (Sat Jul 19 21:21:44 2008) 提到:

每个特征作为一条边来构图后，直接贪心。

添加一个虚节点s，使它连向其他所有点，

每次从s出发随便边不重地走，直到走不动了，把走过的边都删掉并输出。

直到图为空。

正确性证明是，如果一个点i具有入度a和出度b，那么最优解里i至少存在max{a,b}次。而我

们的算法输出i至多max{a,b}次。

恩，似乎是这样。

【在 nullspace (潜水使人进步，灌水使人落后) 的大作中提到: 】: 这题只大概的知道可以用有向图描述，但具体算法没有思路。; 请提示一下应该用什么方法，有没有简化的办法？; 问题描述：有这样一段遗传基因K，它是由一系列的自然数组成：K=a1,a2,a3,a4……am。
在该段基因中，连续的两个自然数被称做它的“特征”。: ……………….

☆─────────────────────────────────────☆

RoBa269 (弱吧) 于 (Sat Jul 19 21:46:48 2008) 提到:

貌似正确的。拜……

【在 ArXoR (…) 的大作中提到: 】: 每个特征作为一条边来构图后，直接贪心。; 添加一个虚节点s，使它连向其他所有点，; 每次从s出发随便边不重地走，直到走不动了，把走过的边都删掉并输出。; ……………….

☆─────────────────────────────────────☆

sadako (山村贞子) 于 (Sat Jul 19 23:38:05 2008) 提到:

似乎不对

假设输入

1 2

2 3

2 4

加入第一次从s出发选了2

于是第一次走过2 3,

…

最后是2 3 2 4 1 2

但是其实应该是1 2 3 2 4

我有哪出错了吗

【在 ArXoR (…) 的大作中提到: 】: 每个特征作为一条边来构图后，直接贪心。; 添加一个虚节点s，使它连向其他所有点，; 每次从s出发随便边不重地走，直到走不动了，把走过的边都删掉并输出。; ……………….

☆─────────────────────────────────────☆

wywcgs (乌鸦) 于 (Sat Jul 19 23:46:34 2008) 提到:

貌似arxor的意思是每次走最长路，greedy么…

【在 sadako (山村贞子) 的大作中提到: 】: 似乎不对; 假设输入; 1 2; ……………….

☆─────────────────────────────────────☆

sadako (山村贞子) 于 (Sat Jul 19 23:48:44 2008) 提到:

可是同时还写着随便找条边

【在 wywcgs (乌鸦) 的大作中提到: 】: 貌似arxor的意思是每次走最长路，greedy么…

☆─────────────────────────────────────☆

wywcgs (乌鸦) 于 (Sat Jul 19 23:51:03 2008) 提到:

就假装是这个意思吧… 我感觉他可能是顺手写的，也是这个意思，要不然他后面的证明明

显是对不上的啊..

【在 sadako (山村贞子) 的大作中提到: 】: 可是同时还写着随便找条边

☆─────────────────────────────────────☆

sadako (山村贞子) 于 (Sun Jul 20 00:04:10 2008) 提到:

怎样每次选出最长路径呢?

删除路径后又要重新搜一次

【在 wywcgs (乌鸦) 的大作中提到: 】: 就假装是这个意思吧… 我感觉他可能是顺手写的，也是这个意思，要不然他后面的证明

明显是对不上的啊..

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Sun Jul 20 00:18:55 2008) 提到:

其实有个很简单的方法。

每个特征长度是2，如果两个特征能够连起来，哪么总长度=2+1，如果三个特征连起来，哪

么总长度=2+1+1。

而每个端点要么被连起来，要么不被连起来。如果不被连起来，那么它可以连接其他的特征

。而连上的任何特征，其实都是一样的，即该端点被封闭，不能再连接其他特征。

因此，设置一个最大长度l，显然开始的时候l=特征x2

然后随便取出一个特征，例如12，寻找以2开头的所有特征，例如找到24，然后把12和24剔

除，加入14，同时总长度-1。假如找不到以2开头的特征，也找不到以1结尾的特征，也把

12剔除，因为总长度不会因为12而减少了。一直到特征集为空的时候，这个时候总长度就是

最短长度。

具体实现的时候可以用环形链表来实现。从随意某个节点开始，遍历链表，寻找到能够整合

的特征(O(n))，然后整合特征删除节点(O(1))。

【在 ArXoR (…) 的大作中提到: 】: 每个特征作为一条边来构图后，直接贪心。; 添加一个虚节点s，使它连向其他所有点，; 每次从s出发随便边不重地走，直到走不动了，把走过的边都删掉并输出。; ……………….

☆─────────────────────────────────────☆

jamen (***) 于 (Sun Jul 20 05:36:10 2008) 提到:

input:

1 2

output?

【在 mumford (in NYC) 的大作中提到: 】: 其实有个很简单的方法。; 每个特征长度是2，如果两个特征能够连起来，哪么总长度=2+1，如果三个特征连起来，
哪么总长度=2+1+1。: 而每个端点要么被连起来，要么不被连起来。如果不被连起来，那么它可以连接其他的特
征。而连上的任何特征，其实都是一样的，即该端点被封闭，不能再连接其他特征。: ……………….

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Sun Jul 20 08:07:22 2008) 提到:

4啊。

【在 jamen (***) 的大作中提到: 】: input:; 2; 1 2; ……………….

☆─────────────────────────────────────☆

dosomethinga (LOVEWW) 于 (Sun Jul 20 10:22:13 2008) 提到:

construct a digraph

now define degree(vi) = (indegree > outdegree) ? 0 : (outdegree - indegree)

and the output is N + sum(degree(vi))

N is number of pairs input

【在 nullspace (潜水使人进步，灌水使人落后) 的大作中提到: 】: 这题只大概的知道可以用有向图描述，但具体算法没有思路。; 请提示一下应该用什么方法，有没有简化的办法？; 问题描述：有这样一段遗传基因K，它是由一系列的自然数组成：K=a1,a2,a3,a4……am。
在该段基因中，连续的两个自然数被称做它的“特征”。: ……………….

☆─────────────────────────────────────☆

ArXoR (…) 于 (Sun Jul 20 15:15:38 2008) 提到:

呃，我没说清楚。

从s随便走一个边不重的极长路(不一定是最长)，然后除了第一条都删掉。

如果不要构造解，就不用这么搞了。

对你的例子

第一条是 1->2->3

第二条是 2->4

【在 sadako (山村贞子) 的大作中提到: 】: 似乎不对; 假设输入; 1 2; ……………….

☆─────────────────────────────────────☆

RoBa269 (弱吧) 于 (Sun Jul 20 15:18:40 2008) 提到:

极长路是指？向两边都不能再延伸的？

如果这个例子里一开始走到了2呢？向前延到1向后延到3么？

【在 ArXoR (…) 的大作中提到: 】: 呃，我没说清楚。; 从s随便走一个边不重的极长路(不一定是最长)，然后除了第一条都删掉。; 如果不要构造解，就不用这么搞了。; ……………….

☆─────────────────────────────────────☆

ArXoR (…) 于 (Sun Jul 20 15:32:45 2008) 提到:

呃，是两边。

�M了加了个s。。。还是不加吧。。。

【在 RoBa269 (弱吧) 的大作中提到: 】: 极长路是指？向两边都不能再延伸的？; 如果这个例子里一开始走到了2呢？向前延到1向后延到3么？

☆─────────────────────────────────────☆

wywcgs (乌鸦) 于 (Sun Jul 20 15:36:38 2008) 提到:

话说我感觉你的意思是没有任何一条路径真包含这条路径的所有边吧….

比如说如果一条路上有个圈，那就不能用两头加减来说了…..

所以我看还不如就最长路呢….

【在 ArXoR (…) 的大作中提到: 】: 呃，是两边。; �M了加了个s。。。还是不加吧。。。

☆─────────────────────────────────────☆

wywcgs (乌鸦) 于 (Sun Jul 20 15:40:15 2008) 提到:

好……好像有问题啊…..

要是最长路，那咋解啊，汗……

【在 wywcgs (乌鸦) 的大作中提到: 】: 话说我感觉你的意思是没有任何一条路径真包含这条路径的所有边吧….; 比如说如果一条路上有个圈，那就不能用两头加减来说了…..; 所以我看还不如就最长路呢….

☆─────────────────────────────────────☆

ArXoR (…) 于 (Sun Jul 20 15:57:02 2008) 提到:

只考虑一个弱连通分量时

看成添加最少的边使得图变成一个欧拉图吧

入度大于出度的点连向出度大于入度的点，使得所有点都出入平等，

然后跑一个欧拉环路出来

【在 wywcgs (乌鸦) 的大作中提到: 】: 好……好像有问题啊…..; 要是最长路，那咋解啊，汗……

☆─────────────────────────────────────☆

wywcgs (乌鸦) 于 (Sun Jul 20 16:14:31 2008) 提到:

貌似没错….

我最开始看到这道题的时候也想到欧拉回路了，结果后来就忘了….

【在 ArXoR (…) 的大作中提到: 】: 只考虑一个弱连通分量时; 看成添加最少的边使得图变成一个欧拉图吧; 入度大于出度的点连向出度大于入度的点，使得所有点都出入平等，; ……………….

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Sun Jul 20 16:23:01 2008) 提到:

这个显然不对的。可以考虑

1 2

2 1

【在 dosomethinga (LOVEWW) 的大作中提到: 】: construct a digraph; now define degree(vi) = (indegree > outdegree) ? 0 : (outdegree - indegree); and the output is N + sum(degree(vi)); ……………….

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Sun Jul 20 16:29:31 2008) 提到:

貌似这个题没有想象得那么简单。

例如数据是下面的时候

就容易出问题。

最优组合应该是2124。但是如果搞成121的话，那就不是最优了。所以贪心法也肯定有问题

。

【在 mumford (in NYC) 的大作中提到: 】: 其实有个很简单的方法。; 每个特征长度是2，如果两个特征能够连起来，哪么总长度=2+1，如果三个特征连起来，
哪么总长度=2+1+1。: 而每个端点要么被连起来，要么不被连起来。如果不被连起来，那么它可以连接其他的特
征。而连上的任何特征，其实都是一样的，即该端点被封闭，不能再连接其他特征。: ……………….

☆─────────────────────────────────────☆

watam (王小石) 于 (Thu Jul 24 08:37:15 2008) 提到:

说一下我的解法：

在特征集中枚举查找最长连续系列，比如 12 23 53，最长序列是 123
在特征集中去掉最长序列的特征。在剩下的特征中继续查找最长序列，直到特征集为空

。

枚举的问题是复杂度是o(n!)，但每次查找最长序列的话，能够快速剪枝。

【在 mumford (in NYC) 的大作中提到: 】: 貌似这个题没有想象得那么简单。; 例如数据是下面的时候; 12; ……………….

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Thu Jul 24 09:28:05 2008) 提到:

贪心法是不一定对的。而且特征有环，12 23 34 45 56 … 9991000 10001，枚举就会累死

你。

【在 watam (王小石) 的大作中提到: 】

说一下我的解法：

在特征集中枚举查找最长连续系列，比如 12 23 53，最长序列是 123

在特征集中去掉最长序列的特征。在剩下的特征中继续查找最长序列，直到特征集为

空。

……………….

☆─────────────────────────────────────☆

watam (王小石) 于 (Thu Jul 24 09:58:00 2008) 提到:

贪心法对不对还没有证明。

我把算法写了一下，解题目中的例子是0.003s (P4 3.0G), 后来把例子中的数据扩大到17

个特征，也还是0.003s左右。

你举得例子会算得很快，因为只有一个最长序列。其它的能够在第二步就剪枝掉了。

【在 mumford (in NYC) 的大作中提到: 】: 贪心法是不一定对的。而且特征有环，12 23 34 45 56 … 9991000 10001，枚举就会累

死你。

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Thu Jul 24 10:07:43 2008) 提到:

局部贪心法是不对的。例如一个很大的环，12 23 34 45 56 61，拖一个小尾巴26，这样显

然是23456126最好，但是如果搞成一个环1234561，就没法加小尾巴了。

而且枚举里面，碰到复杂的情况就没戏了。例如1…32然后几乎每一对都对应一个特征，中

间剪掉一些特征再加上一些特征。这样你几乎要枚举32!了。

【在 watam (王小石) 的大作中提到: 】: 贪心法对不对还没有证明。; 我把算法写了一下，解题目中的例子是0.003s (P4 3.0G), 后来把例子中的数据扩大到
17个特征，也还是0.003s左右。: 你举得例子会算得很快，因为只有一个最长序列。其它的能够在第二步就剪枝掉了。

☆─────────────────────────────────────☆

watam (王小石) 于 (Thu Jul 24 10:22:40 2008) 提到:

我的是全局贪心，比如你举得例子，1234561是一个长序列，23456126是一个更长的序列，

那算法就会保留23456126这个序列。所以目前来看还是正确的。

枚举的复杂度确实是个问题。最原始的想法是全枚举然后归并，取归并结果最短的。这个算

法在有17个特征时就已算不出来。所以想的是加强剪枝的条件。现在这个求最长序列的剪枝

条件还是比较强的（就是正确性还是待定）。比如你举得这个例子，枚举时12 23 需要往下

枚举， 12 34， 12 45 等就直接剪枝了。

刚试了一下1 2， 2 3， …， 999， 1000。运行时间是21s。

【在 mumford (in NYC) 的大作中提到: 】: 局部贪心法是不对的。例如一个很大的环，12 23 34 45 56 61，拖一个小尾巴26，这样
显然是23456126最好，但是如果搞成一个环1234561，就没法加小尾巴了。: 而且枚举里面，碰到复杂的情况就没戏了。例如1…32然后几乎每一对都对应一个特征，

中间剪掉一些特征再加上一些特征。这样你几乎要枚举32!了。

☆─────────────────────────────────────☆

mumford (in NYC) 于 (Thu Jul 24 10:36:03 2008) 提到:

我说的复杂不是环有多么大。而是例如

12 13 14 15 16

21 23 24 25 26

…

这样

假设有33个数，然后有33*32个特征，其中有几个特征没有，这样你的枚举还算得出来么？

【在 watam (王小石) 的大作中提到: 】: 我的是全局贪心，比如你举得例子，1234561是一个长序列，23456126是一个更长的序列
，那算法就会保留23456126这个序列。所以目前来看还是正确的。: 枚举的复杂度确实是个问题。最原始的想法是全枚举然后归并，取归并结果最短的。这个

算法在有17个特征时就已算不出来。所以想的是加强剪枝的条件。现在这个求最长序列的剪

枝条件还是比较强的（就是正确性还是待定）。比如你举得这个例子，枚举时12 23 需要往

下枚举， 12 34， 12 45 等就直接剪枝了。: 刚试了一下1 2， 2 3， …， 999， 1000。运行时间是21s。

Published on Jul 25, 2008 in categories non-tech

上一篇 Graphics engineer
下一篇本版常用缩写词解释