夫妻异地如何交I-485 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

夫妻异地如何交I-485

夫妻异地如何交I-485# EB23 - 劳工卡

c*f2012-01-28 08:01

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*u2012-01-28 08:01

2 楼

夫妻异地是分开交485申请，还是一起申请？
多谢了。

x*y2012-01-28 08:01

3 楼

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*f2012-01-28 08:01

4 楼

这样是根据graph造字符串么？是不是反了阿？

c*f2012-01-28 08:01

5 楼

怎么能保证“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