接続されたグラフでは、空腹の人が立っている n 個のポイントがあります。お腹が空いた人は、グラフにある k 件のレストランのいずれかに行きたがります。移動距離は1人1km以内。レストランは CEILING[n/k] 人までしか収容できません。
これらの空腹の人々とその地域のレストランのポイントが与えられた場合、すべてのゲストを収容できるかどうかを多項式時間で実行する効率的なアルゴリズムはありますか (True または False のように)。
これは巡回セールスマン問題を思い起こさせますが、これは修正版に過ぎないのでしょうか?
これは、二部グラフでのマッチング問題の例です。これは、巡回セールスマン問題よりもはるかに簡単に解決でき、O((n+k)^3) で解決できます。
次の 2 つの下位問題があります。
たとえば、Floyd-Warshall アルゴリズムを使用して、O(n^3) 内のポイントの任意のペア間の最短経路を計算することができます。
許可されるマッチングは、1 km 未満の距離の接続です。
このマッチング問題は、グラフを作成してから最大フローを解くことで解決できます。
適切なグラフは、ソース ノード、シンク ノード、および各人物と各レストランのノードを持つことです。
次に、このグラフを通る最大フローを計算します。最大フローが n の場合にのみ、すべてのゲストを収容できます。
最大フローを計算するアルゴリズムは多数あります。1 つの例は、複雑さ O(V^3)の push-relabelです。ここで、V は頂点の数です (この問題では V=n+k+2)。