問題タブ [edmonds-karp]

有向グラフを使用して、効率的な最大フロー アルゴリズムを決定しようとしています。nフライトのリスト (各エントリには、開始都市、終了都市、出発時間、到着時間、およびフライトの収容人数が含まれます) が与えられた場合、ルートが決定されます。 A市からB市まで、できるだけ多くの人が行き来できるようにしたいと考えています。また、A市からB市にできるだけ多くの人が到着するように、可能な便のセットを返却できるようにしたいと考えています。 Ford-Fulkerson アルゴリズムの実装または類似のものである可能性がありますが、効率的な方法でこのスケジュールを max-flow インスタンスに変換できず、具体的には上記のアルゴリズムの擬似コードがどのように見えるかについて問題がありますやった後のように。

Karp が分割問題に還元することにより、次の問題が NP 完全であることを示すことになっています。問題 X は、以下に従って、異なる年齢層にワクチンの用量を分配することです。

与えられた: D ワクチン用量、n 年齢グループ、入力としてa ₁から a _n 。ここで、年齢グループ k は入力としてd ₁から d _{nのk 個}の個人で構成され、年齢グループ k の各個人は d _k用量、少なくとも tを受け取ります。各年齢層の_kパーセントが完全にワクチン接種を受けている必要があり、残りの投与量の最大数は S.

この問題が NP 完全であることを証明する必要があります。ステップの 1 つは、この問題とパーティションの問題の間で Karp 削減を行うことです。私はさまざまな方法でこの削減を試みましたが、成功しませんでした。何か案は？擬似コードが理想的です。