動的ディスクリートノードフロー制御のための良好なローカルヒューリスティックは何ですか？

Question

ノードのセットがあるとします。いくつかのノードはプロデューサーであり、一部は消費者であり、一部はルーターです。各ノードには最大スループットがあり、1日に受け付けることができるユニットの最大数と、1日に送信できるユニットの最大数を定義します（この場合、受け入れと送信はお互いに干渉しません）。各ノードには単位の記憶容量もあり、フローの変化に対処できます。また、各ノードは、（プレーン上の）最大8つの近隣ノードとだけアウト・コネクトすることができ、イン・コネクションにも同じ制限が適用されます。

私は既にグラフを与えられたノードを列挙し、ノードをフォローするノードにユニットをプッシュするヒューリスティックを既に持っています。それは各ノードを列挙し、各ターゲットノードにmax（ceil（残存送信可能ユニット/残存ノード）ノード、受信可能残存ユニット数）を送信する。

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

編集 量は、（いくつかの最大の下方に）時間とともに変化することができ、ノードを追加または削除することができます。

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

Answer 1

「定常状態」ソリューション、つまり同じフローが毎日特定のエッジに沿って発生するソリューションを探している場合、ノードにリソースの「備蓄」はありません（これは、各備蓄量は一定の割合で増加し続け、最終的には無限大になります）。

ので、その場合には、我々は、各ノードのストレージ容量を忘れることができ、そして問題があまりにも多くの困難もなく、多項式時間で正確を解決することができMaximum Flow problem、と非常によく似ています。 Wikipediaのリンクはさまざまなアルゴリズムを提案しています。実装が難しくないFord-Fulkersonから始めることをお勧めします（他のものはもっと簡単かもしれませんが、自分では実装していません）。エッジノードで、というよりもを横切って流れる上の制約と最大流量のお得な情報：

が実際に最大フロー問題にあなたの問題を有効にするには、あなたがする必要があります一つのことがあります。 「ノードスループット」制約を「エッジスループット」制約に変換するには、すべてのノードを1つの線でリンクされた3つのノード（1→2→3）に変換し、ノード1とノード2の間のエッジは、ノードの「出力容量」に等しい容量を有するノード2とノード3との間のエッジとを含む。次に、ノードへのすべての入力がノード1に接続され、すべての出力がノード3に接続されていることを確認します。

これはあなたに「定常状態」のソリューションを提供します。それは、自分よりもスマートな人がこれを証明することができるとは思うが、日数を指定してストレージ容量を使用することで、その日数のスループットを向上させる戦略を考案することが可能である。不可能である。いずれにしても、各エッジごとに毎日同じフローを使用したい場合は、Max Flowソリューションよりも優れているわけではありません。