Accelerating A<sup>*</sup> algorithms by sweeping out small-degree nodes
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人情報処理学会の論文
- 2011-02-28
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nagamochi
Graduate School Of Informatics Kyoto University
-
Nagamochi Hiroshi
Graduate School Of Informatics Kyoto University
-
Hiroshi Nagamochi
Department Of Applied Mathematics And Physics Kyoto University
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Liang Zhao
Graduate School Of Informatics Kyoto University.
-
Pipaporn Eumthurapojn
Graduate School of Informatics, Kyoto University.
-
Pipaporn Eumthurapojn
Graduate School Of Informatics Kyoto University.
関連論文
- Constant Time Generation of Trees with Degree Bounds
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- Survivable Network Design Problems with Weighted Degree Constraints (Combinatorial Optimization and Discrete Algorithms)
- Contention-Free λ-Planes in Optically Burst-Switched WDM Networks(Internet)
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- Protein complex prediction via improved verification methods using constrained domain-domain matching
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Indexing All Rooted Subgraphs of a Rooted Graph
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A note on distance dominating in maximal outerplanar graphs