学位論文 Prize Collecting Steiner Tree 問題に対するヒューリスティクス

細川, 祐樹

pp.1 - 49 , 2016-03-24 , 法政大学大学院理工学研究科
内容記述
Prize Collecting Steiner Tree(PCST) 問題は,組合せ最適化の重要な問題である.PCST 問題は整数計画問題に定式化することで最適解を求めることができる.しかし整数計画問題の制約条件は入力の点数に比例して増加し,最適解を実時間内で求められないことがある.そのため,最適解を近似的に求める必要がある.本研究は PCST 問題に対して,2 つのヒューリスティクス(H1, H2)を提案する.各ヒューリスティクスは,2段階からなる.第1段階では,全域木を求める.第2段階では,全域木から目的関数を最小にする部分木を求める.部分木を求めるために新たに最適部分木問題を定義し,それを最適に解くアルゴリズムを用いる.入力をランダムグラフと 5 つのグループ K, P, C, D, Cologne のベンチマークとし,計算実験を行った.計算実験の結果,2 つのヒューリスティクスは現実問題に基づいた K と Cologne の入力に対して,平均 1.3 未満の近似比を得た.これは P, C, Dの入力と比べて,良好な結果である.サイズの大きな入力に対して,H1 は H2 と比べて高速に近似解を出力できるため,現実的な問題に適用できると考える.
本文を読む

http://repo.lib.hosei.ac.jp/bitstream/10114/12504/1/16_thesis_master14R6207%e7%b4%b0%e5%b7%9d%e7%a5%90%e6%a8%b9.pdf

このアイテムのアクセス数:  回

その他の情報