多数のランドマークを用いるための ALT アルゴリズム拡張

• Item type: SIG Technical Reports(1)
• 公開日: 2009-01-23
• タイトル: 多数のランドマークを用いるための ALT アルゴリズム拡張
• タイトル / 言語: en
• タイトル: Extending ALT algorithm to use multiple landmarks
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学大学院基幹理工学研究科
• 著者所属: 早稲田大学メディアネットワークセンター
• 著者所属: 早稲田大学理工学術院／国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Fundamental Science and Engineering, Waseda University
• 著者所属(英): en
• 著者所属(英): Media Network Center, Waseda University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics / National Institute of Informatics
• 著者名: 松永, 拓; 平手, 勇宇; 山名, 早人
• 著者名(英): Taku, Matsunaga; Yu, Hirate; Hayato, Yamana
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，汎用的なグラフ構造に対しての最短経路探索の高速化手法として， ALT アルゴリズムが提案されている． ALT アルゴリズムでは，ランドマークと呼ばれるノードと他のノードの距離を保存しておくことにより， A *探索における距離推定のためのヒューリスティック関数を提供する．しかし， ALT アルゴリズムでは，事前保存領域がランドマーク数増加に対して線形に増加し，多くのランドマークを設定することは，多くの事前保存領域を必要としてしまう． そこで本稿では， ALT アルゴリズムにおけるヒューリスティック関数を 2 ランドマークを用いて推定するように拡張し，ランドマークの追加による事前保存領域が線形には増加しない手法を提案する．道路ネットワークを用いた実験の結果，提案手法においてランドマークをランダムに選択した場合， ALT アルゴリズムにおいてランドマークをランダムに選択した場合よりも，少ない事前保存領域で，平均して少ない探索空間で最短経路を得るができることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, the ALT algorithm is proposed as a speed-up algorithm to compute shortest paths in general graph structures. The ALT algorithm offers a landmark based heuristic function to estimate distance in A* search. Before computing shortest paths, the ALT algorithm computes distances between all nodes and landmarks, and stores them to prepared memory or storage space. However, as the number of landmarks increases, the required prepared space increases linearly. To solve this problem, in this paper, we propose a novel heuristic function for computing shortest paths in general graph structures. Our approach for providing heuristic function uses two landmarks to decrease the size of prepared space so that prepared space will not increase linearly as the number of landmarks increases. For evaluation, we applied a road network graph structure to our proposed algorithm and the ALT algorithm. Our evaluation shows that our approach with random landmark selection requires less prepared space and less search space than the ALT algorithm with random landmark selection.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009, 号 9(2009-AL-122), p. 75-80, 発行日 2009-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会