容量付き最小全域木
スパニングツリー型

容量付き最小全域木は、指定されたルートノードを持ち、容量制約を満たすグラフの最小コスト全域木です。容量制約は、ルートノードに接するすべてのサブツリー（ルートに単一の辺で接続された最大のサブグラフ）が個以下のノードを持つことを保証します。ツリーノードに重みがある場合、容量制約は次のように解釈できます。つまり、どのサブツリーでも重みの合計は 個以下である必要があります。サブグラフをルートノードに接続する辺はゲートと呼ばれます。最適解を見つけることはNP困難です。[1] r {\displaystyle r} c {\displaystyle c} r {\displaystyle r} c {\displaystyle c} c {\displaystyle c}

アルゴリズム

根 を持つグラフ があるとします。内の他のすべてのノードを とします。頂点と 間の辺コストを とすると、コスト行列 が形成されます。 G ＝ （ V 、 E ） {\displaystyle G=(V,E)} n ＝ | G | {\displaystyle n=|G|} r ∈ G {\displaystyle r\in G} 1つの 私 {\displaystyle a_{i}} G {\displaystyle G} c 私 j {\displaystyle c_{ij}} 1つの 私 {\displaystyle a_{i}} 1つの j {\displaystyle a_{j}} C ＝ c 私 j {\displaystyle C={c_{ij}}}

エサウ・ウィリアムズヒューリスティック

Esau-Williams ヒューリスティックは、正確な解に非常に近い次善の CMST を見つけますが、平均すると EW は他の多くのヒューリスティックよりも優れた結果を生成します。

初期状態では、すべてのノードはルート （星型グラフ）に接続されており、ネットワークのコストは です。これらの各エッジはゲートです。各反復処理において、内のすべてのノードについて最も近い近傍ノードを探し、トレードオフ関数 を評価します。正のトレードオフの中で最大のものを探し、結果として得られるサブツリーが容量制約に違反しない場合は、 番目サブツリーをエッジでに接続しているゲートを削除します。ツリーにこれ以上の改善ができなくなるまで、反復処理を繰り返します。 r {\displaystyle r} ∑ 私 ＝ 0 n c r 私 {\displaystyle \displaystyle \sum _{i=0}^{n}c_{ri}} 1つの j {\displaystyle a_{j}} G − r {\displaystyle G-{r}} t （ 1つの 私 ） ＝ グラム 私 − c 私 j {\displaystyle t(a_{i})=g_{i}-c_{ij}} t （ 1つの 私 ） {\displaystyle t(a_{i})} グラム 私 {\displaystyle g_{i}} 私 {\displaystyle i} 1つの j {\displaystyle a_{j}} c 私 j {\displaystyle c_{ij}}

最適でない CMST を計算するための Esau-Williams ヒューリスティック: 

関数CMST( c , C , r ):
     T = { , , ..., }
    変化があります:
        各ノードに対して= 異なるサブツリー内の最も近いノード
            = - t_max = max ( )
         k = iが= t_max
        の場合( cost (i) + cost (j) <= c )
             T = T - T = TユニオンTを返します
  
    
      
        
          c
          
            1
            r
          
        
      
    
    {\displaystyle c_{1r}}
  

  
    
      
        
          c
          
            2
            r
          
        
      
    
    {\displaystyle c_{2r}}
  

  
    
      
        
          c
          
            n
            r
          
        
      
    
    {\displaystyle c_{nr}}
  

  
    
      
        
          1つの
          
            私
          
        
      
    
    {\displaystyle a_{i}}
  

            
  
    
      
        
          1つの
          
            j
          
        
      
    
    {\displaystyle a_{j}}
  

  
    
      
        t
        （
        
          1つの
          
            私
          
        
        ）
      
    
    {\displaystyle t(a_{i})}
  

  
    
      
        
          グラム
          
            私
          
        
      
    
    {\displaystyle g_{i}}
  

  
    
      
        
          c
          
            私
            j
          
        
      
    
    {\displaystyle c_{ij}}
  

        
  
    
      
        t
        （
        
          1つの
          
            私
          
        
        ）
      
    
    {\displaystyle t(a_{i})}
  

  
    
      
        t
        （
        
          1つの
          
            私
          
        
        ）
      
    
    {\displaystyle t(a_{i})}
  

  
    
      
        
          グラム
          
            け
          
        
      
    
    {\displaystyle g_{k}}
  

            
  
    
      
        
          c
          
            け
            j
          
        
      
    
    {\displaystyle c_{kj}}

EW が多項式時間で解を見つけるのは簡単にわかります。

[2]

アフージャのヒューリスティック

Ahujaのヒューリスティック[3]は、ランダム化された貪欲な初期解 から大規模なマルチ取引所近傍での局所探索を使用する。

初期解決策

初期解は、Esau-Williams法のランダム化版を用いて求められます。ランダム化は、各ステップにおいて最良の解ではなく、最良の解から一様ランダムに結合を実行することで実現されます。 p {\displaystyle p}

ローカル検索近隣地域

を根 を持つ初期解とします。近傍は、 の異なる構成要素の 1 つを置換する単一のノードまたはサブツリー（本稿の冒頭で述べたようなサブツリーではなく、一般的なサブツリー）の任意の組み合わせで構成されます。この場合、置換後の構造は次の置換子となり、最後の置換子は最初の置換子を置換し、元の構成要素は複数の置換子を持たないものとし、結果として得られる構成要素のいずれにおいても容量が超過しません。 T {\displaystyle T} r {\displaystyle r} T ∖ r {\displaystyle T\setminus r}

改善グラフ

改善グラフは、非常に大きな近傍を効率的に検索するためのツールです。改善グラフを通るパスは、ソリューションへの変更に対応し、パスのコストは、変更を適用したときのソリューションのコストの変化です。ここで、改善グラフは、各ノードの2 つのコピーと、任意のノードから の異なるコンポーネント内の任意のノードへの最大 4 つのエッジを使用して構築された有向マルチグラフです。エッジは、元のコンポーネントからノードを削除し、ターゲット コンポーネントでルートとなるサブツリーを置き換える変更に対応します。ノードとサブツリーを組み合わせると、4 つの可能なエッジが生成されます。対応する変更によってターゲット コンポーネントが容量を超えない場合、エッジが存在します。エッジのコストは、ターゲット コンポーネントの頂点上の最小全域木のコストの、置き換え前と置き換え後の差です。したがって、ローカル検索の近傍は、各コンポーネントから最大で 1 つのノードを含む改善グラフのサイクルに対応します。 私 ′ 、 私 ″ {\displaystyle i',i''} 私 ∈ V （ T ） {\displaystyle i\in V(T)} T ∖ r {\displaystyle T\setminus r} 私 ′ 、 j ″ {\displaystyle i',j''} 私 {\displaystyle i} j {\displaystyle j} 私 ′ {\displaystyle i'} 私 ″ {\displaystyle i''}

ローカル検索ステップ

局所探索ステップでは、動的計画法アプローチを使用して、改善グラフ内の最小コストのサイクルを探します。改善グラフの長さが増加するパスが生成され、開始と終了、および関連するコンポーネントが同じである最も好ましいパスのみが格納されます。このために、パスを保持するために、これら 3 つのプロパティのタプルをキーとするハッシュ テーブルが使用されます。各負のサイクルには、このノードを含むサイクル内のすべてのパスが負のコストを持つノードが存在するため、負のコストを持つパスのみを考慮する必要があります。パス間の関連するコンポーネント セットの比較は、アルゴリズムで最も一般的な操作の 1 つであるため、速度向上のため、整数として格納されたインジケータ ビット配列の比較として実装されます。ただし、これは明らかにハッシュ衝突の多発に起因しており、ハッシュ関数とテーブル構造の特定の選択、およびスペース制限による高い負荷係数の結果である可能性があります (2003 年の論文)。

パフォーマンス

論文執筆当時（2003年）、このアルゴリズムは標準的なオペレーションズ・リサーチのベンチマークにおいて最先端でした。実行の大部分は改善グラフの構築（または更新）によって行われました。改善グラフのエッジ数は、入力グラフのサイズに比例して経験的に2乗します。これは、比較的複雑な最小全域木探索ステップの実行回数を決定するため、最も重要な要素です。したがって、入力グラフの密度が低いほど、改善グラフのエッジ数が減少するため、実行時間が大幅に短縮されるという結論が導き出されます。

アプリケーション

CMST問題はネットワーク設計において重要です。多くの端末コンピュータを中央ハブに接続する必要がある場合、スター構成は通常、最小コストの設計とは言えません。端末をサブネットワークに編成するCMSTを見つけることで、ネットワークの実装コストを削減できます。

参考文献

  1. ^ Jothi, Raja; Raghavachari, Balaji (2005)、「容量付き最小スパニングツリー問題とそのネットワーク設計における変種の近似アルゴリズム」、ACM Trans. Algorithms、1 (2): 265– 282、doi :10.1145/1103963.1103967、S2CID  8302085
  2. ^ Esau, LR; Williams, KC (1966). 「テレプロセシングネットワーク設計について：第2部 最適ネットワークの近似法」IBM Systems Journal . 5 (3): 142– 147. doi :10.1147/sj.53.0142.
  3. ^ Ahuja, RK; Orlin, JB; Sharma, D. (2003). 「容量制限付き最小全域木問題のための複合大規模近傍構造」.オペレーションズ・リサーチ・レターズ. 31 (3): 185– 194. doi :10.1016/S0167-6377(02)00236-5.
「https://en.wikipedia.org/w/index.php?title=Capacitated_minimum_spanning_tree&oldid=1270867004」から取得