ヒッチコック型輸送問題に対する途中棄却を含む段階的解法
スポンサーリンク
概要
- 論文の詳細を見る
ヒッチコック型輸送問題の費用と閾値の比較を行う判定問題のアルゴリズムを提案する.最適解を求めるよりも少ない計算時間で求めることが可能な下界を求め,閾値との比較を段階的に行う.比較の結果,下界が閾値よりも大きいことがわかればその段階で棄却する.費用と閾値との間に大きな差がある場合にはより早い段階で棄却されるため計算時間も短くなる.一般のヒッチコック型輸送問題では下界を求めることが困難であることから,本論文ではユークリッド空間上の点集合を考え,2点間の単位流量当りの費用がその距離で与えられるとする.入力されたグラフを縮約し,問題の規模を小さくする.縮約されたグラフにおけるヒッチコック型輸送問題の最小費用が縮約を行う前のグラフにおける最小費用の下界を与えることを示す.また,最小費用と閾値の差が小さく,縮約されたグラフでは判定を行えない場合に,最初に与えられた問題を解くことになっても計算量が増加しないことを示す.
- 社団法人電子情報通信学会の論文
- 2002-11-22