Accelerating A^* algorithms by sweeping out small-degree nodes

• Item type: SIG Technical Reports(1)
• 公開日: 2011-02-28
• タイトル: Accelerating A^* algorithms by sweeping out small-degree nodes
• タイトル / 言語: en
• タイトル: Accelerating A^* algorithms by sweeping out small-degree nodes
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Informatics, Kyoto University.
• 著者所属: Graduate School of Informatics, Kyoto University.
• 著者所属: Graduate School of Informatics, Kyoto University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University.
• 著者名: Liang, Zhao; Pipaporn, Eumthurapojn; Hiroshi, Nagamochi
• 著者名(英): Liang, Zhao; Pipaporn, Eumthurapojn; Hiroshi, Nagamochi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A* is an algorithm framework for calculating point-to-point shortest paths. This paper gives a simple method to accelerate A* algorithms in practice by sweeping out small-degree nodes from the priority queue, which can reduce the running time of the queue operations and the distance estimations. Experiments show that our method is efficient in practice, especially for A* algorithms with a heavy estimation function such as the ALT algorithm (Goldberg and Harrelson, SODA 2005) and its time-dependent generalizations.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A* is an algorithm framework for calculating point-to-point shortest paths. This paper gives a simple method to accelerate A* algorithms in practice by sweeping out small-degree nodes from the priority queue, which can reduce the running time of the queue operations and the distance estimations. Experiments show that our method is efficient in practice, especially for A* algorithms with a heavy estimation function such as the ALT algorithm (Goldberg and Harrelson, SODA 2005) and its time-dependent generalizations.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-134, 号 5, p. 1-4, 発行日 2011-02-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会