c******f
发帖数: 2144 | 1 最短公共超序列问题(Shortest common supersquence):给一些字符串 比如 abc ,bcd
,def
然后可以判断是否有长度为 x 的字符串是这些字符串的父串，换句话说是否有一个长
度为x 的字符串能包含着三个字符串，比如abcdef就能，如果x为6 我们就能找到长度
为6的字符串包含了abc, bcd, def
再给一个例子，如果有这些字符串 abc, bcd, efg， x还是为 6，是否有长度为6的字
符串能包含这3个字符串么？没有！最短的是abcdefg 也就是说这三个字符串的最短公
共超序列长度为7
我现在不需要求最短公共超序列，但是我想证明这个问题是NP hard的，我想用TSP旅行
商问题 或者汉密尔顿路的问题reduce到这个问题上来证明这个最短公共超序列也是
nphard的，因为如果我们能把任何一个nphard的问题reduce到最短公共超序列问题上来
，就能证明最短公共超序列问题也是nphard的了。换句话说，我不明白怎么能给一个旅
行商问题或者汉密尔顿路径的问题，根据这些问题建立出一个最短公共超序列问题，然
后如果最短公共超序列问题可以解 |
|
