algorithm - 不明瞭な代表者のシステムは効率的に解決可能ですか？

Question

セットS1、S ₂、...、_Snがあり_ます。これらのセットは互いに素である必要はありません。私たちの仕事は、選択された要素の総数ができるだけ少なくなるように、各セットの代表的なメンバーを選択することです。1つの要素が複数のセットに存在する可能性があり、それに含まれるすべてのセットを表すことができます。これを効率的に解決するアルゴリズムはありますか？

Answer 1

元のセットS ₁、S ₂、...、S _nを宇宙の要素とし、元のセット メンバーをセット自体とします: T ₁、T ₂、... 、Ｔ_ｍ（ここで、Ｔ_ｉは、対応するメンバーを含む元の集合である要素｛Ｓ_{ｊ ｝を含む）。}

ここで、宇宙S ₁、S ₂、...、S _nを集合T ₁、T ₂、...、T _{m で}カバーする必要があります。まさにセットカバー問題です。これはよく知られている NP 困難な問題であるため、効率的に解決するアルゴリズムはありません (理論家が通常言うように、P=NP でない限り)。ウィキペディアのページからわかるように、貪欲な近似アルゴリズムがあります。効率的ですが、近似率はあまり良くありません。

Answer 2

「効率的に」とは、多項式時間を意味していると思います。

Evgeny Kluev は正しく、問題は NP 困難です。その決定バージョンは、ヒッティング セット問題として知られており、その概念が導入された直後に、現在 NP 完全と呼ばれるものであることが示されました。Evgeny の削減がヒッティング セットの問題からセット カバーの問題への削減であることは事実ですが、明示的な逆削減を確認することは難しくありません。

和集合 U={u ₁ ,u ₂ ,...,u _n } である集合 C={C ₁ ,C ₂ ,...C _m } が与えられた場合、最小カーディナリティのサブセット C' を見つけたいとします。 union も U に等しくなります。最初の問題でS _{iを {C j} in C | C j として定義します。u _iは C _j } の要素です。S={S ₁ ,S ₂ ,...,S _n } の最小ヒット セットは、目的の C' に等しくなります。

Answer 3

Evgeny の栄光を盗むためではありませんが、投稿者の問題の一般的なケースが NP 困難であることをおそらくより厳密に示すかなり簡単な方法を次に示します。

E のすべてのエッジがXの少なくとも 1 つの頂点に隣接している単純なグラフ( V , E ) で、頂点Vから最小セットXを見つける最小頂点被覆問題を考えます。

エッジは、順序付けされていない 2 要素セット { v _a , v _b } で表すことができます。ここでv _aとv _bはVの個別の要素です。{ v _a , v _b }として表されるエッジeがv _cに隣接するのは、 v _cが { v _a , v _b }の要素である場合に限られることに注意してください。

したがって、最小頂点被覆問題は、 Vの最小サイズのサブセットXを見つけることと同じです。ここで、 Eのエッジによって定義される各エッジ セット { v _a , v _b } には、 Xにある要素が含まれます。

元の問題を効率的に解くアルゴリズムがあれば、上記の問題を効率的に解くアルゴリズムがあるため、最小頂点被覆問題も効率的に解くことができます。

Answer 4

検討すべきアルゴリズムのいくつかは、シミュレーテッド アニーリングと遺伝的アルゴリズムです。これは、最適に近いソリューションで生活できる場合です (最適なソリューションが得られる可能性がありますが、必ずしもそうとは限りません)。シミュレーテッド アニーリングは、生産用の電子 CAD 自動配置で機能させることができます (私は Wintek の自動配置プログラムの開発チームの一員でした)。