文献

J-GLOBAL ID：200902239357473289   整理番号：09A0177373

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

Extending ALT algorithm to use multiple landmarks

著者 (4件)： 松永拓 (早稲田大 大学院基幹理工学研究科) ,  平手勇宇 (早稲田大 メディアネットワークセ) ,  山名早人 (早稲田大 理工学術院) ,  山名早人 (国立情報学研)
資料名： 情報処理学会研究報告  (IPSJ SIG Technical Reports)
巻： 2009  号： 9(AL-122)  ページ： 75-80  発行年： 2009年01月23日 
JST資料番号： Z0031B  ISSN： 0919-6072  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 近年,汎用的なグラフ構造に対しての最短経路探索の高速化手法として,ALTアルゴリズムが提案されている。ALTアルゴリズムでは,ランドマークと呼ばれるノードと他のノードの距離を保存しておくことにより,A^*探索における距離推定のためのヒューリスティック関数を提供する。しかし,ALTアルゴリズムでは,事前保存領域がランドマーク数増加に対して線形に増加し,多くのランドマークを設定することは,多くの事前保存領域を必要としてしまう。そこで本稿では,ALTアルゴリズムにおけるヒューリスティック関数を2ランドマークを用いて推定するように拡張し,ランドマークの追加による事前保存領域が線形には増加しない手法を提案する。道路ネットワークを用いた実験の結果,提案手法においてランドマークをランダムに選択した場合,ALTアルゴリズムにおいてランドマークをランダムに選択した場合よりも,少ない事前保存領域で,平均して少ない探索空間で最短経路を得るができることを確認した。(著者抄録)

シソーラス用語： *グラフ ,  *最短路問題 ,  標識 ,  *高速アルゴリズム ,  発見的方法 ,  *探索問題 ,  道路網 ,  評価試験 ,  無作為抽出 ,  空間
準シソーラス用語： *ALTアルゴリズム ,  ヒューリスティック ,  ランダムサンプリング ,  ランドマーク ,  探索空間

分類 (4件)： グラフ理論基礎  (IA02020S) ,  ネットワーク法  (KA03040X) ,  計算理論  (JB02000A) ,  人工知能  (JE08000Z)

引用文献 (10件)：

• GOLDBERG, A. V. Computing the Shortest Path : A* Search Meets Graph Theory. Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, 2005. 2005, 156-165
• GOLDBERG, A. V. Computing Point-to-Point Shortest Paths from External Memory. Proc. 7^ International Workshop on Algorithm Engineering and Experiments, 2005. 2005, 26-40
• HART, P. E. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on System Science and Cybernetics. 1968, SSC-4, 2, 100-107
• DIJKSTRA, E. W. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik. 1959, 1, 269-271
• DANTZIG, G. B. Linear Programming and Extensions. 1962

タイトルに関連する用語 (4件)： ランドマーク ,  ALT ,  アルゴリズム ,  拡張