大規模な多種結線実現問題の発見的解法
スポンサーリンク
概要
- 論文の詳細を見る
枝の使用回数に制限のあるネットワークにおいて, q個のソース・シンク対間のおのおのに要求された本数の結線群を実現する問題を, 多種結線実現問題という. 本論文は,「翁長の多重フロー定理」に立脚した発見的アルゴリズムを考案し, (i)大規模ネットワークヘの適応と高速化, (ii)アルゴリズムの多様化の2点を重視して開発した実用的プログラムの精度と計算時間の特性を計算実験により明らかにしたものである. ネットワーク規模の制約よりLP, IPの適用が不可能であるため, 結線実現の難易度は高いが結線解の存在が自明な問題に対する結線復元率を精度の目安とすることにした. 主要な結果として, 計算時間が∣V∣^<1.2>q log Rに比例することおよび平均復元率96%を得た. ただし, ∣V∣は節点数, qはソース・シンク対数, Rは結線要求総本数である.
- 一般社団法人情報処理学会の論文
- 1984-03-15
著者
関連論文
- 広島大学工学部第二類(電気系)回路システム工学大講座情報回路網工学研究室
- 競争型反応-拡散方程式系の棲み分け解について (Mathematical Topics in Biology)
- 一般化メ-ビウス関数とその直積定理(技術談話室)
- 組合せ論的システム特集号を編集して (組合せ論的システム特集号)
- 組合せ論的システムのモデリングとその解析 (組合せ論的システム特集号)
- フロ-理論とその組合せ論的システム解析への応用-2-
- フロ-理論とその組合せ論的システム解析への応用-1-
- フロ-理論とその組合せ論的システム解析への応用-4-(講義)
- フロ-理論とその組合せ論的システム解析への応用-3-(講義)
- フロ-理論とその組合せ論的システム解析への応用-5-(講座)
- オフィス手続き自動化システムOPAの障害回復機能の設計
- GreenOfficeのアーキテクチャ
- GreenOfficeのOfficeware
- GreenOfficeの基本コンセプト
- 数式処理システムREDUCE3への和分機能のインプリメント
- 大規模な多種結線実現問題の発見的解法
- ネットワ-クにおける多種結線実現問題とその近似算法
- 海岸線の真の長さとは何か
- 拡張マ-ク・グラフにおける発火スケジュ-ルの性質とその計算法
- プロセッサ・アレイにおける最大フロ-実現の分散アルゴリズム
- 時不変ネットワ-クにおける変動入力粒子フロ-流の時最適伝送
- シグナルフロ-グラフのカット変換(技術談話室)
- 容量制限のある計算グラフのスケジュ-リング
- ネットワ-クにおける集合(ブ-ル)フロウの諸性質
- ネットワ-クにおける集合(ブ-ル)テンションとポテンシャルの諸性質
- ウェーブフロント・コントロール・アルゴリズムを実行する帯型連立一次方程式専用計算機の設計