パーティション問題の変形の複雑さ

この投稿によって動機づけられ、
NP完全変形サブセット合計またはパーティションの問題の問題
、私はパーティションのこの変形に興味があります:

バランスのとれたパーティション問題(両方の部分のカーディナリティが同じ)の解を考えると、最大のカーディナリティの差異(すなわち、|
P_1 | – | P_2 || $が最大)を有する別の解を見つける。

このような不均衡なパーティションを見つけるための効率的なアルゴリズムはありますか、それともNP困難ですか?

私は擬似多項式時間アルゴリズムに興味があり、問題が強く
NP困難であることを証明しています。

P.S. $ p1 = {2,2,3,4,5,6 } $と$ p2 = {1,1,3,4,5,8 }
$という例があります(@domotorpの要求通りです)。 。 2番目の解は$ p1 = {1,2,3,4,4,8 } $と$
p2 = {1,2,3,5,5,6 } $です(2番目の解は最適ではありませんp1とp2の要素数が等しいため)。

ベストアンサー

バランスの取れたパーティションが与えられていなくても、擬似多項式時間で最大カーディナリティの不一致パーティションを見つけ出す(または存在しないことを決定する)問題は解決できます。

入力が正の整数$ S = {x_1、 ldots、x_N } $のマルチセットであるとします。 $ K = sum_
{i = 1} ^ Nx_i $とする。以下では、$ S
$の最大カーディナリティ不一致パーティションを見つけるための動的プログラミングアルゴリズムを示します。

$ s $、$ i $、$ c $が$ 0 le s le K $と$ 0 le c le i le N
$の変数であるとします。基数が$ c $であり、合計が$ sであるマルチセット$ T subseteq {x_1、
ldots、x_i } $が存在する場合にのみ、$ p(s、i、c)$を真とする$。

再発を定義することができます:

  • $ p(s、0、0)$は、$ s = 0 $なら真です。
  • $ p(s、i-1、c)$または$ p(s-x_i、i-1、c-1)$のいずれかが真の場合、/li>

  • $ p(s、i、c)$はそうでなければfalseです。

この再帰を使って、$ N $と$ K $での時間多項式のすべての有効な$ s $、$ i $、$ c $の$ p
$の値を計算できます。

さらに、述語$ phi(c)= p( frac {K} {2}、N、c)$は、 “和が$ Sの部分集合$ S $の合計の?
“または「同等のものとして、カーディナリティの相違$ | N-2c | $を伴う$ Sのパーティションが存在しますか?したがって、$
p $のすべての値を見つけた後、$ phi(c)= p( frac {K} {2}、N、c)$のすべての値を調べ、$ $
phi(c)$とのカーディナリティの差異$ | N-2c | $が最大の$ true。この値を$ c_0 $と呼んでください。 $
phi(c)$が真でない場合、$ S $の区画はありません。

残っているのは、実際に$ S $のパーティションの中のどれかが$ c_0
$のサイズを持つパーティションを見つけることだけです。これを行うためのアルゴリズムは次のとおりです。

initialize P_1 and P_2 to be empty lists
initialize (s, c) to (k/2, c_0)
for i = N, N-1, ..., 1
| if p(s, i-1, c) is true:
| | add x_i to P_1
| else:
| | add x_i to P_2
| | set (s, c) to (s - x_i, c-1)
output P_1 and P_2

このアルゴリズムは、$ p( frac {K} {2}、N、c_0)$から$ p(0,0,0)$までの$ p $
backの再帰の直後にあることに注意してください。つまり、アルゴリズムは、ループの開始時に$
p(s、i、c)$が常に真であるという不変量を維持する(これは誘導によって証明するのが容易である)。インバリアントは、ループの最後の反復後も保持され続けます。つまり、$
p(s、0、c)$はループの後で真です。 $ s = c = 0 $の場合にのみ$ p(s、0、c)$が真であるため、$ frac
{K} {2} $と$ c_0 $から$ s $と$ c $が減少するループの途中で$ 0 $になります。 $ s $と$ c
$が変化する唯一の行を見ると、これは、$ P_2 $のリストが$ frac {K} {2} $の$ c_0
$個の要素を含むことを意味します。言い換えると、$ P_1 $と$ P_2 $はカーディナリティーの相違が$ | N – 2c_0 |
$である$ S $のパーティションを形成します。$ c_0 $の定義は$ Sの任意のパーティション$。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です