- 著者
-
堀山 貴史
樋口 康介
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.109, no.108, pp.17-21, 2009-06-22
- 参考文献数
- 22
最長路問題は、各辺に非負整数の距離が与えられた無向グラフに対し、始点s、終点t間のシンプルなパスで、その上の距離の総和が最大となるものを求める問題である。最長路問題は、効率的な多項式時間アルゴリズムが古くから知られている最短路問題とは異なった性質を持つ。例えば、各辺に関連付けられた距離の正負を反転させた最短路問題を解くことで最長路が得られるように一見思われるが、負の閉路(距離の総和が負となる閉路)が存在するため、最短路問題のアルゴリズムを適用することはできない。本研究では、最長路問題、s-t最長路問題、全点対最長路問題を定式化し、全探索および0-1整数計画法に基づく厳密最適化アルゴリズムを提案する。また、JR大都市近郊区間の大回りをベンチマークとして利用し、各手法の実装および評価を与える。