| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 5F |
| セッション名 |
| GA |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| F会場（9号館2F 921教室） |
| 講演番号 |
| F-004 |
| タイトル |
| コストの変動する重み付きグラフにおける経路探索の為のグラフ分割手法の提案 |
| 著者名 |
| 島影 秀征, 山口 崇志, マッキン ケネス ジェームス, 永井 保夫, |
| キーワード |
| ヒューリスティクス, 探索問題 |
| 抄録 |
|
近年、カーナビゲーションシステムや乗り換え案内サービスなど、地点間の経路決定を支援するシステムが広く普及している。 本研究では、テーマパークやイベント会場を回る際に、限られた時間内に目的の場所を如何に効率的に巡るかという問題について検討する。これは地点間の移動時間を最小にするという、最短経路問題の様な側面と、如何に多くの目的地を巡る事が出来るかという、ナップサック問題の様な側面を持っている。 検討する問題は粒度が細かい為にノード数が増加し問題空間が大きくなり、計算量が膨大になる特徴を持つ。その為、混雑度の変化量を基にしたグラフ分割を用いて問題空間を縮小するヒューリスティックな手法を提案する。 |
| 本文pdf |
| PDF download (315.1KB) |