配布するアルゴリズム

Question

"人"のリストLpと "食べ物"の別のリストLfがあります。

Lpの各要素はLfの要素の1つ以上を必要としますが、1つしか受け取ることはできません。

Lpのどの要素をLpの各要素に与えるかを決定するアルゴリズムはどのようにするべきですか（すべてのLfを配布する必要もなく、すべてのLpに提供する必要もありません）。必要なLfが割り当てられているLpの数を最大にしようとしています。

Answer 1

これはグラフのような問題をモデル化し、次のようにmaximum flowについて解くことによって解決することができる。

1. 各人にグラフ内のノードを考えます。これらのpノードをコールしましょう。
2. 各食品を同じグラフの別のノードとみなします。これらのfノードと呼ぶことにしよう。
3. 食品bが好きa人は、P_Aと F_B 間のエッジを追加した場合。誰もが好む食べ物ごとにこれを行います。各エッジの容量は1です。
4. 各p-nodeに接続するソースノードIを作成します。各人は多くとも1つの食べ物を食べることができるので、Iから各p-nodeまでのエッジの容量も1でなければならない。
5. 各f-nodeに接続するシンクノードOを作成する。各食品は多くとも1人で食べることができるので、これらの辺も1の容量を持つべきです。Edmonds-Karpアルゴリズム（または他の最大流量アルゴリズム）を実行します。出力を見てください。結果として得られる最大流量ネットワークによって使用されるpノードからfノードへのエッジは、問題に対する答えです。

エッジの容量を変更することで、問題のステートメントへのバリエーションを調整できます。