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的了。换句话说，我不明白怎么能给一个旅
行商问题或者汉密尔顿路径的问题，根据这些问题建立出一个最短公共超序列问题，然
后如果最短公共超序列问题可以解 | x***y
发帖数: 633 | 2 We can reduce Hamilton Path to this problem as follows:
assume that the largest weight of all the edges in HP is K (or a larger value to make reduction possible), and this is the length of each string we will use. So, we reduce HP problem by: if for two nodes X, Y and the weight of their edge is m, then we convert the node to 2 strings x', y', such that the length of largest common substring between x' suffix and y's prefix is K-m( when K is large enough, this is possible). Then, the each HP pro
【在 c******f 的大作中提到】
: 最短公共超序列问题(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到这个问题上来证明这个最短公共超序列也是
| c******f
发帖数: 2144 | 3 这样是根据graph造字符串么？ 是不是反了阿？ | c******f
发帖数: 2144 | 4 怎么能保证“the length of largest common substring between x' suffix and y's
prefix is K-m”这样的字符串一定能够造阿？有没有什么理论的证明？ 我画了一些
图倒是都对 而且我知道 如果是string来构造graph的话 用的就是这个方法
value to make reduction possible), and this is the length of each string we
will use. So, we reduce HP problem by: if for two nodes X, Y and the weight
of their edge is m, then we convert the node to 2 strings x', y', such that
the length of largest common substring between x' suffix and y's prefix is K
-m( when K is large enough, this is p
【在 x***y 的大作中提到】
: We can reduce Hamilton Path to this problem as follows:
: assume that the largest weight of all the edges in HP is K (or a larger value to make reduction possible), and this is the length of each string we will use. So, we reduce HP problem by: if for two nodes X, Y and the weight of their edge is m, then we convert the node to 2 strings x', y', such that the length of largest common substring between x' suffix and y's prefix is K-m( when K is large enough, this is possible). Then, the each HP pro
| a***9
发帖数: 364 | 5 是的，我老糊涂了。
【在 c******f 的大作中提到】
: 这样是根据graph造字符串么？ 是不是反了阿？
|
|
