Reach for A*: an Efficient Point-to-Point Shortest Path Algorithm

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=5_tCZvripzc


Duration: 1:07:00
925 views
9

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We consider two approaches to the problem. The classical A* search directs the search towards the goal. A recent reach-based approach of Gutman identifies local vertices during preprocessing, which allows it to prune these vertices during searches. These approaches can be combined, resulting in further reduction of the search space. We discuss efficient implementations of these approaches and their combination. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications.



Other Videos By Microsoft Research


2016-09-07The Jasons: The Secret History of Science's Postwar Elite           
2016-09-07UPCRC Multicore Applications Workshop - Session # 4 - Speech and Audio
2016-09-07Literacy Bridge and the Talking Book Project
2016-09-07Stencil Computation Auto-tuning on Modern Multicore Architectures
2016-09-07MSPAC Discussion and Book Signing with Senator John Kerry and Teresa Heinz Kerry
2016-09-07Mark-Region and Other Advances in Garbage Collection
2016-09-07The Medea Hypothesis: Is Life on Earth Ultimately Self Destructive?
2016-09-07WaveScope: Stream Programming on Heterogeneous Wireless Devices
2016-09-07Bags of words: the search engine
2016-09-07Intrinsic Robustness of the Price of Anarchy
2016-09-07Reach for A*: an Efficient Point-to-Point Shortest Path Algorithm
2016-09-07ABC-MART: Recent Improvements in Boosting, Trees and Classification Algorithms
2016-09-07Intelligent Fault Notification through Understanding Developer Behavior
2016-09-07Contextual Link Analysis for Web Search
2016-09-07Scheduling Parallel Functional Programs
2016-09-07Working at the boundaries: how intersections can inform innovation
2016-09-07Denial of Service or Denial of Security? How Attacks on Reliability can Compromise Anonymity
2016-09-07Chemotaxis. Do we understand it all?
2016-09-07Graphical Models and Statistical Mechanics in Communications and Storage Applications
2016-09-07Model Abstraction Methodology for Temporal Behavior Analysis of Multiscale Biological Systems
2016-09-07Active Learning with Model Selection in Linear Regression


Tags:
microsoft research