2

これがよく知られた問題なのか、1 つに還元できるのかはわかりませんが、ここ数日以来、私が苦労しているのは次のとおりです。

X_1、X_2、X_3 .. X_n を整数のセットとします。

各セット X_i には、m 個 (すべてのセットで等しい) の要素 x_i,j : j = 1...m があります。

私の目標は、各セットから 1の要素を選択して、選択したすべての要素間のペアごとの差の合計が最小になるようにすることです。

シリアル差分の合計 (つまり、連続したセットから選択された要素間の差分の合計) を最小化するという、少し異なる問題から始めました。DP の前方計算は次のとおりです。

セット i から要素 j を選択するためのコストを F(i, j) とします。

F(i, j) = min_k F(i - 1, k) + |x(i-1,k) - x(i, j)|

つまり、前のセットで k 番目の要素を選択し、現在のセットで j 番目の要素を選択するコストを評価します。現在のステップのコストは、セット i-1 の k 番目の要素とセット i の j 番目の要素の絶対差に等しくなります。

しかし、私の本当の問題は、セット X_1、... X_n の順序に依存しません。本質的に、動的プログラミングは私に何かを与えてくれますが、私が言ったように、「シリアル」差の合計が最小になるように、要素の「チェーン」を各セットから 1 つずつ見つけるという、関連しているが異なる問題です。

基本的な分析から、この問題に対する単純な解決策は、n セットのすべての順列を生成し、順列ごとに動的計画法を使用して解決することであることがわかります。これは扱いにくいですが、n が十分に小さい場合は、このばかげた網羅的なアプローチを採用することもできます。

この問題が多項式アルゴリズムを使用して解決できるかどうか、または既知の NP 困難/完全な問題の 1 つに還元できるかどうかを判断することはできません。二次計画として。

私に助言するか、いくつかの読み物を教えてください。

ありがとう。

[編集1]

議論の便宜のためにここに例を追加します。

X = [[11, 24, 38], [12, 21, 33], [13, 22], [15, 23]]

解は 24, 21, 22, 23 です (無関係かもしれませんが、私の DP は 11, 12, 13, 15 を与えます。私は特に私の DP を失敗させるためにこの例を作成しました)。

[編集2]

これはNP完全な問題ではないと思います。DP から拡張できる解決策は次のとおりです [正しいかどうかはわかりませんが、そのようです]:

ソリューションには、各セットから少なくとも 1 つの要素が含まれます。

ですから、任意のセット (サイズが異なる場合は、できれば最小のもの) を選択して、リストから削除してみましょう。

これを X\Xp と呼びましょう。ここで、Xp は削除されたセットです。

\Xp の各要素 x に対して、新しいセット X' = X\Xp U {x} を作成します。

DP を m 回解き、目的関数 (ペアごとの距離の合計) を計算すると、それらの最良のものを選択できます。

DP自体はO(nm ^ 2)かかり、これをm回実行すると、O(nm ^ 3)になります。

4

2 に答える 2

1

これにより、重み付きグラフで最小の重みのクリークを見つけることができます。異なるセット内の任意の 2 つのノードの重みは、それらの差の絶対値に等しくなります。

于 2013-07-13T07:48:39.043 に答える