電子情報通信学会総合大会講演要旨
D-1-1
Prize Collecting Steiner Tree問題に対するヒューリスティクス
○細川祐樹・千葉英史(法政大)
Prize Collecting Steiner Tree (PCST) 問題は,組合せ最適化において重要な問題である.PCST問題の応用として,電線・ケーブル,水道管などのインフラや,広告看板などを効果的に配置することができる.
本研究では,PCST問題に対する新しいヒューリスティクスを提案する.計算実験を通して,既存の定数近似比の保証を持った近似アルゴリズムとの比較を行う.比較の結果,提案するヒューリスティクスは,既存の定数近似アルゴリズムと比べ,大幅な計算時間の改善に成功した.またグラフの枝数が少ないときに関して,提案するヒューリスティクスは近似率が良くなる結果を得た.