入力: n 要素の M 個の順序付きタプルのセット。各要素はセットです。つまり、(A1、A2、...、An)、各 Ai はセットです。
問題: これらの n タプルを組み合わせて、n タプルの最小セットを作成します。2 つの n-タプルは、1 つの位置のみが異なる場合、つまり次のように組み合わせることができます。
A = (A1, A2, ..., An) と B = (B1, B2, ..., Bn) は (A1, A2, ..., Ai U Bi, Ai+1, ..) に結合できます。 ., An) iff Aj = Bj, for every j != i.
例: 入力: 4 2 タプル: ({1}, {1}), ({1}, {2}), ({3}, {1}), ({3}, {2}) 出力: 1 つの 2 タプル: ({1, 3}, {1, 2})
私の質問は、この問題にどのようにアプローチしますか? 既知のNP問題に還元できるかどうか知っていますか? 1 つのアイデアは、これをグラフとしてモデル化することです。タプル A と B を組み合わせることができる場合、色 i (i = それらが異なる位置) でそれらの間に色付きのエッジを描画します。