大規模な多種結線実現問題の発見的解法

• Item type: Journal(1)
• 公開日: 1984-03-15
• タイトル: 大規模な多種結線実現問題の発見的解法
• タイトル / 言語: en
• タイトル: A Heuristic Algorithm for Solving Large Scale Multi - Connection Assignment Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 広島大学工学部第2類（電気系）
• 著者所属: 広島大学工学部第2類（電気系）
• 著者所属: 広島大学工学部第2類（電気系）
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者名: 丸本, 悟; 岸本, 一男; 翁長, 健治
• 著者名(英): Satoshi, Marumoto; Kazuo, Kishimoto; Kenji, Onaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 枝の使用回数に制限のあるネットワークにおいて q個のソース・シンク対間のおのおのに要求された本数の結線群を実現する問題を 多種結線実現問題という.本論文は 「翁長の多重フロー定理」に立脚した発見的アルゴリズムを考案し （）大規模ネットワークヘの適応と高速化 （）アルゴリズムの多様化の2点を重視して開発した実用的プログラムの精度と計算時間の特性を計算実験により明らかにしたものである.ネットワーク規模の制約よりLP IP の適用が不可能であるため 結線実現の難易度は高いが結線解の存在が自明な問題に対する結線復元率を精度の目安とすることにした.主要な結果として 計算時間がlVl^<1.2>q log Rに比例することおよび平均復元率96%を得た.ただし lVlは節点数 qはソース・シンク対数 Rは結線要求総本数である.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 25, 号 2, p. 329-336, 発行日 1984-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764