0

ノードのセットがあるとします。一部のノードはプロデューサー、一部はコンシューマー、一部はルーターです。各ノードには、1 日に受け入れることができるユニットの最大数と、1 日に送信できるユニットの最大数を定義する最大スループットがあります (この場合、受け入れと送信は互いに干渉しません)。各ノードにはユニット用のストレージ容量もあり、フローの変動に対応できます。また、各ノードは最大 8 つの近くのノード (平面上) とのみアウト接続でき、同じ制限がイン接続にも適用されます。

私はすでに、グラフを指定してノードを列挙し、次のノードにユニットをプッシュする十分な仕事をするヒューリスティックを持っています。各ノードを列挙し、max(ceil(remaining-sendable-units/remaining-following-nodes), left-receivable-units-at-receiver) を各ターゲット ノードに送信します。

ここで、ノードを自動的に見て、十分なフローを実現するためにグラフ トポロジをどのようにするかを決定する方法が必要です。私の基本的なアイデアは、各ノードに「責任」を割り当てることでした。最初は、それらが消費したユニット数に相当します。次に、n1 から n2 にエッジを追加すると、n2 の責任の一部が n1 に与えられます。しかし、ノードが消費できる量とノードが受け入れる量の違いがアルゴリズムを混乱させ、私をぐるぐる回らせることにすぐに気付きました。

編集 各プロデューサー/コンシューマーによって消費される量は、時間の経過とともに変化する可能性があり (最大値を下回る)、ノードを追加または削除できます。

簡単なアイデアはありますか？

4

1 に答える 1

0

「定常状態」のソリューション、つまり同じフローが特定のエッジに沿って毎日発生するソリューションを探している場合、ノードでのリソースの「備蓄」はあり得ません (各備蓄が継続することを意味するため)。一定の速度で成長し、最終的には無限に大きくなります)。

その場合、各ノードのストレージ容量を忘れることができ、問題は最大フロー問題に非常に似ており、多項式時間で正確に解くことができ、それほど困難はありません。ウィキペディアのリンクでは、さまざまなアルゴリズムが提案されています。実装がそれほど難しくない Ford-Fulkerson から始めることをお勧めします (他のアルゴリズムの方が簡単かもしれませんが、自分で実装したことはありません)。

問題を実際に Max Flow の問題に変えるには、やらなければならないことが 1 つあります。Max Flow は、ノードではなく、エッジ全体のフローの制約を扱います。「ノード スループット」の制約を「エッジ スループット」の制約に変換するには、ノード 1 と 2 の間のエッジの容量が「ノードの「入力容量」、およびノー​​ドの「出力容量」に等しい容量を持つノード 2 と 3 の間のエッジ。次に、ノードへのすべての入力がノード 1 に接続され、すべての出力がノード 3 に接続されていることを確認します。

私が言ったように、これは「定常状態」の解決策を提供します。事前に日数を指定してストレージ容量を利用することで、その日数のスループットを向上させる戦略を考案できる可能性がありますが、私よりも賢い誰かがこれでさえそうではないことを証明できると思います.可能。いずれにせよ、毎日各エッジで同じフローを維持したい場合は、Max Flow ソリューションよりもうまくいくことはありません。

于 2009-04-25T12:32:16.453 に答える