中間者会
中間者間 - 最適化する方法解決策は、元の問題を 2 つに分割し、それぞれを独立して解決し、その後、半分の解決策を組み合わせて元の問題の解決策を取得することで構成されます。
したがって、2 つの条件が満たされる場合は、
meet-in-the-middle を使用するのが合理的です。
1) 問題の半分を解くのに必要な時間は、問題全体を解くのにかかる時間よりも漸近的に短くなります。
2) 半分の問題を解くことで、元の問題全体の解を得ることができ、同時に、問題全体を解くよりも漸近的に速く解決できます。
例
A、
B、
C、
D という 4 つの整数配列があるとします。これらの数値の合計がゼロになるように、各配列から数値を 1 つだけ選択する必要があります。単純な解決策、つまり、考えられるすべてのオプションを単純に列挙することもできます。これは
O(n4) で機能します。
ただし、
meet-in-the-middle を使用することはできます。
a + b + c + d = 0 は
(a + b) = -(c + d) と同等であることに注意してください。
タスクを 2 つの半分に分割しましょう。つまり、前半では配列
A と
B のみを使用し、後半では
C のみを使用します。 > と
D。
前半で可能なすべての
(a + b) オプションを反復処理し、すべての値をハッシュ テーブル (
unowned_map、
HashMap など)。これは O(n2) で機能します。
ここで、後半ですべての可能なオプション (c + d) を反復処理します。特定のオプションを検討するとき、反対の符号の現在の合計に関連付けられた値がハッシュ テーブルに存在するかどうかを確認します (その後、合計するとゼロになる 2 つの逆数が見つかりました)。この部分は O(n2) でも機能します。
ここには個別の「回答のマージ」フェーズはありません。 1 つ目では、各半分を解決する過程でこれを実行しました。ほとんどのタスクでも同様の状況が発生します
。
最終的には、meet-in-the-middle を使用した O(n2) で解決策を導き出しました。
meet-in-the-middle は、指数関数的な解を最適化するときに最もよく使用され、実行時間に大きな影響を与えることに注意してください。