2

私は有向グラフを持っています。各エッジには固有の「重み」w_ijがあり、これは固定されています。各ノードにはv_i構成可能な値がありますが、値が固定されている「ルート ノード」(着信エッジなし) と「リーフ ノード」(発信エッジなし) は除きます。

各エッジの「ノードによって調整された」エッジ値は次の式で与えられます。 s_ij = w_ij + v_j - v_iつまり、隣接するノードの値の差によってエッジの値を調整します。もちろん、ノードの値を変更すると、 の値に影響しますs_ij。

の値に興味があり、min{s_ij}この「ボトルネック」値が最大化されるように、ノードへの値の最適な割り当てを見つけたいと考えています。

それを行う方法のアイデアはありますか？

注:ルートからリーフへのサイクルと「固定パス」は、最小値の上限を提供します (たとえば、サイクルでは、ノードの差の合計は常に 0 であるため、得られる最善の値はエッジの固有の平均です)。ウェイト）。しかし、サイクルと「固定パス」が重複する可能性があるため、最小上限が達成可能かどうかは明らかではありません。ソリューションには、最初にそのようなパス/サイクルを見つけることが含まれる可能性があります。

4

2 に答える 2

4

私の理解が正しければ、問題はこの線形計画として定式化できます。ソースまたはシンクであるv_i = 0すべての頂点に対して、入力を調整します。i

maximize z

subject to
for every ij,
    z + v_i - v_j <= w_ij  (i.e., z <= w_ij + v_j - v_i = s_ij)

variables
z unbounded
for every vertex i not a source or sink,
    v_i unbounded

これがデュアルプログラムです。

minimize sum_ij of w_ij y_ij

subject to
sum_ij y_ij >= 1
for every vertex i not a source or sink,
    sum_j y_ij - sum_j y_ji = 0

variables
for every ij,
    y_ij >= 0

ソースとシンクを保存制約から除外しなかった場合、これはまさに最小平均コスト サイクルの線形プログラムになります。現状では、フロー分解手法を使用して、ソース-シンク パスまたはサイクルのいずれかである最適値が存在することを示すことができます。最小平均コスト サイクルを見つけるための単純なアルゴリズムをわずかに変更すると、次のようになります。ここに適用されます。

最適値が得られたら、重み付きの Bellman-Ford を実行しz*てポテンシャルを見つけることができます。詳細を提供できなくて申し訳ありませんが、宿題をやっているようなしつこい気持ちがあります.v_iw_ij - z*

于 2013-06-23T17:09:04.257 に答える