この問題を証明するために、この割り当てがあります。
有限のアルファベット £、2 つの文字列 x、y € £*、および正の整数 K.単一の記号の削除または隣接する記号の交換の一連の K 以下の操作によって、文字列 x から文字列 y を導出する方法はありますか?
np-complete です。セットカバー問題の決定バージョンから変換を行う必要があることはすでにわかっていますが、これを行う方法がわかりません。どんな助けでも大歓迎です。
質問する
1253 次
2 に答える
2
修正レーベンシュタイン距離のように見えます。問題は、二次時間で DP を使用して解決できます。
最小集合カバー (MSC) からこの文字列修正問題への変換については、次のドキュメントで説明されています。
Robert A. Wagner
On the complexity of the Extended String-to-String Correction Problem
1975, Proceedings of seventh annual ACM symposium on Theory of computing
MSC の問題を簡単に説明すると、次のようになります。
有限集合 x_1、...、x_n、および整数 L が与えられた場合、|J| となるような {1,...,n} のサブセット J が存在しますか? <= L、および
union_{j in J} x_j = ユニオンすべて x_i ?
w = すべての x_i を結合し、t = |w| とします。および r = t^2 であり、w にないシンボル Q、R、S を選択します。
文字列を取ります:
A = Q^r R x_1 Q^r S^(r+1) ... Q^r R x_n Q^r S^(r+1)
B = R Q^r ... R Q^r w S^(r+1) ... S^(r+1) <- each ... is n times
and
k = (l+1)r - 1 + 2t(r+1)(n-1) + n(n-1)(r+1)^2/2 + (r*n + |x_1 ... x_n| - t)*W_d
[W_d is delete operation weight, can be 1.]
文字列間訂正問題 (A,B,k) は、元の MSC 問題が満足できるものであることが示されています。
文字列の構成から、証明が自明ではないことは明らかです :-) しかし、管理するには複雑すぎません。
于 2011-06-06T08:40:00.770 に答える