0

ルールのリストに基づいて、数値の有効な順列が存在するかどうかを判断するアルゴリズムを作成しようとしています。

nノードと整数がnあり、各ノードにはペアリングできない整数のリストが含まれています。私の目標は、各ノードを整数とペアリングできるかどうかを判断することです。

現在、私の最善の解決策は、ペアリングできる番号とノードを選択し、それらをリストから削除してから、関数を再帰的に呼び出すことです。

最悪の場合、これにより可能なすべての順列が階乗時間で生成される可能性があります。すべての順列を生成せずに有効なペアリングが存在するかどうかを判断することは可能ですか?

助けてくれてありがとう！

4

3 に答える 3

2

この問題は、Maximum Bipartite Matching に縮小され、Ford-Fulkerson アルゴリズムを使用して O(nm) http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithmで解決できます。

アイデアは、頂点がn個の整数とn個のノードであるグラフを作成でき、その整数を使用してそのノードを表すことができる場合、ノードから整数への有向エッジが存在することです。上記のアルゴリズムを適用すると、グラフを 2 つのセットに分けることができます。

于 2013-09-18T11:10:43.867 に答える
0

これは、代入問題と考えることもできます。

割り当てたくない組み合わせには莫大なコストを割り当て、実行可能なすべての組み合わせにはゼロのコストを割り当てることができます。

目的関数を最小化し、結果がゼロより大きい場合は、実行可能な代入が不可能であることを意味します。

標準ハンガリーアルゴリズムを適用可能

于 2013-09-18T11:33:36.533 に答える
0

これらの「ペアリングできない整数のリスト」がどのように生成されるかについての詳細がない限り、いいえ。この種の問題の解決策は、分割統治アルゴリズムです: http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

于 2013-09-18T11:01:14.923 に答える