閲覧可能ファイル 

ファイル	フォーマット	サイズ	閲覧回数	説明
16_thesis_master14R6207細川祐樹	pdf	2.16 MB	177

論文情報

ファイル出力

アイテムタイプ	学位論文
タイトル	Prize Collecting Steiner Tree 問題に対するヒューリスティクス
著者	著者名 細川, 祐樹
	著者名 HOSHOKAWA, Yuuki
言語	jpn
開始ページ	1
終了ページ	49
発行年	2016-03-24
著者版フラグ	Not Applicable (or Unknown)
学位授与年月日	2016-03-24
学位名	修士(工学)
学位授与機関	機関名 法政大学 (Hosei University)
内容記述	理工学研究科システム工学（経営システム工学）専攻; 指導教授: 五島洋行
抄録	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 と比べて高速に近似解を出力できるため，現実的な問題に適用できると考える．
資源タイプ	Thesis
インデックス	資料タイプ別 ＞ 学位論文 ＞ 修士論文 ＞ 理工学研究科
	112 理工学部・理工学研究科 ＞ 学位論文 ＞ 修士論文

ホームへ戻る