1

私は正確なカバーや同様の問題に比較的慣れていないので、ご容赦ください。典型的な正確なカバーの問題があるとします。セットXとXのサブセットSのコレクションが与えられた場合、 Xを正確にカバーするS * ( S のサブセット)を見つけたいと思います。ただし、ソリューションS * に正確にk 個の要素が含まれるようにします。さらに、1つのソリューションで十分です。

Knuth の Algorithm X は、考えられるすべての解を返すように設計されていることを知っています。Knuth のアルゴリズムを実行して、 k 個の要素を持つソリューションが見つかるまでソリューションを反復する必要がありますか、それとも (私が推測するように) もっと良い方法がありますか? 私はところでPythonを使用しています。

コンテキストとして、Xのサイズは <100 ですが、Sのサイズは 10^6 にすることができます。kは 10 未満で比較的小さい。

4

1 に答える 1

2

kが小さい場合は、余分な要素を追加して、余分な要素の 1 つだけを含む各複製でk各サブセットを複製してみてください。kk

もう 1 つのアプローチは、正確なカバー問題を整数線形プログラムとして解き、ILP ソルバーで解くことです。x_i次に、th サブセットがソリューションに含まれるかどうかを示す0-1 の変数がiあり、重複するセットがソリューションに含まれるのを防ぐ制約があります。この定式化では、カバーに正確kなサブセットを提供するには、単純にsum(x_i) = k.

アルゴリズム X を変更して、制約を直接処理することもできます。これまでに選択した行の数を数えてください。すでに を選択している場合は、kそれ以上検索せずに失敗してください。k同様に、行数が少ないソリューションは無視します。

于 2020-06-21T15:07:03.610 に答える