2

（「マッピングアルゴリズム」と「1対1アルゴリズム」を検索した）適切な用語が何であるかわからず、より単純な（より標準的な）定式化を考えることはできません。

私は2つのセットを持っています、

A B C D E

と

L M N O P

そして私は1対多の地図を与えられます、例えば

A --> L, M, N, P
B --> M
C --> M, N, O
D --> N
E --> O, L

マップの1対1の「サブセット」がすべてのアイテムをカバーできるかどうかを判断する最も単純および/または最速のアルゴリズムは何ですか？たとえば、上記のような「サブセット」は存在します。

A --> P
B --> M
C --> O
D --> N
E --> L

サブセットマップ自体を知る必要はなく、存在するかどうかだけを知る必要があります。

「ブルートフォース」アルゴリズムは明らかです。わずかな改善は、必要なマッピングを満たすアイテムがない場合は常に深さ優先でバックトラックすることです。別の改善は、マッピングの昇順、たとえば、最初B --> M、、、D --> N次に2番目E --> O, Lなどです。

しかし、これらはすべて、ブルートフォース検索の原始的な変形のように見えます。より良いアルゴリズムはありますか？マップを行列に変換したり、答えを決定するある種の縮小を行ったりするなど、線形システムを使用してこのような問題を解決するという漠然とした記憶がありますが、これを理解するには線形代数を再学習する必要があります。多分SOは私をより速く助けることができます。

ありがとう！

4

2 に答える 2

2

2つのセットが完全に互いに素であると仮定すると、解決しようとしている問題は、2部最大カーディナリティマッチング問題に還元できます。実行できるマッチングの最大数が最初のセットのカーディナリティに等しい場合、すべてのアイテムをカバーするマッピングのサブセットが存在します。

二部マッチング問題からフロー問題への変換とは別に、TopCoderのこのトピックでは、Kuhnのアルゴリズムで問題を解決するためのより高速な方法について説明しています。

于 2013-01-23T20:16:49.323 に答える
1

あなたが探している用語は「二部マッチング」です。これを解決する最も簡単な方法は、フローの問題に変換することです。1つのソースを作成し、それを最初のセットのすべての要素に接続します。最初のセットのすべての要素を2番目のセットの1つ以上の要素に接続します（1対1のマップにある接続を行います）。次に、2番目のセットのすべての要素を単一のシンクに接続します。これらの接続はすべて重み1である必要があります。

最大フローをチェックするために、任意の最大フロー解決アルゴリズム（アイデアについてはhttp://en.wikipedia.org/wiki/Maximum_flow_problemを参照）を使用できます。最大フローが各セットの要素数と正確に等しい場合は、検索しているようなマッピングが存在します。

于 2013-01-22T21:51:17.847 に答える