0

我有两个有向无环图，我需要计算这些图的最长公共子序列（LCS）。对于两个字符串/子序列，我使用动态编程 (DP) 的 LCS 算法，但是如何将此算法修改为图形？

任何想法？

整个任务：

令 G 是一个有向无环图，其中每个顶点都用有限字母表中的符号标记。不同的顶点可以用相同的符号来标记。G 中的每条有向路径都具有通过连接路径中的顶点符号形成的迹线。图 G 的序列是 G 中某个有向路径的迹的子序列。

设计一种计算两个给定有向无环图的最长公共序列的有效算法。

示例：字符串 DYNAMIC、PROGRAM 和 DEPTHFIRST 是图片的有向无环图序列。String PROGRAM 是它的踪迹。

在此处输入图像描述

4

1 回答 1

1

设 A 为第一个 DAG，B 为第二个 DAG。对于 A 中的任意两个节点 a 和 B 中的 b，定义从 A 中的 a 和 B 中的 b 开始的最长公共子序列的长度为

LCS(a,b) =  0 + max LCS(a',b') for any pair (a',b') s.t. a->a' and b->b'
                               or a=a' and b->b', or b=b' and a->a'
                               if a and b do NOT share same label

            1 + max LCS(a',b') for any pair (a',b')
                               s.t. a -> a' and b -> b'
                               if a and b DO share same label

然后对 |A| 应用动态规划 x |B| 对 (a, b) 并读取与 DAG 源（“起始节点”）相关的对的值。

于 2014-05-12T10:22:36.820 回答