algorithm - 算法-计算两个DAG的最长公共(public)子序列(LCS)

我有两个有向无环图，我需要计算这些图的最长公共子序列（lcs）。对于两个字符串/子序列，我使用使用动态规划（dp）的lcs算法，但如何将此算法修改为图形？
知道吗？
整个任务：
设g是一个有向无环图，其中每个顶点都用有限字母表中的符号标记。不同的顶点可以用相同的符号标记G中的每个有向路径都有通过连接路径中顶点的符号而形成的跟踪图g的序列是图g中某条有向路的迹的子序列。
设计了一种计算两个给定有向无环图的最长公共序列的有效算法。
示例：字符串dynamic、program和depthfirst是图片的有向无环图序列。字符串程序是它的跟踪。

最佳答案

让A是第一个DAG，B是第二个DAG对于a中的任意两个节点a和b中的任意两个节点，定义从a中的a和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源相关的对（“开始节点”）的值。

关于algorithm - 算法-计算两个DAG的最长公共(public)子序列(LCS)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23605559/