Pathfinding Algorithms for Mutating Weight


Unformatted text preview:

Pathfinding Algorithms for Mutating Weight Graphs Research Paper Haitao Mao Computer Systems Lab 2007 2008 1 Abstract Consider a map of an unknown place represented as a graph where vertices represent landmarks and edges represent connections between landmarks You have current information on the time it will take to travel between landmarks as well as an archive about how the travel times changed through the past You have a preset destination that you want to reach as fast as possible Pathfinding algorithms for static graphs involve computing the whole path from start to destination but if the weights are rapidly changing due to some extreme condition of the place then calculating the whole path in the beginning will not be feasible The purpose of this project is to design and compare different pathfinding algorithms for a graph whose edge weights mutate randomly to a significant extent Algorithms may involve probabilistic theory dynamic programming heuristics genetic programming and variations of standard shortest path algorithms such as Dijkstra s algorithm 2 Purpose and Scope The plan is to create a sturdy algorithm for the general case of the problem as well as variations for specific cases where the main algorithm would not be as effective Algorithms will be compared and analyzed to determine the circumstances for which each one is best This project will involve more theory and design than actual programming 3 Background Literature There are little to no studies available concerning graphs with randomly mutating weights so research has been focused on graph theory in general 1 as well as the more specific topic of dynamic graphs which may change in structure General shortest path and flow algorithms have been reviewed Dynamic graph algorithms and query update algorithms have been reviewed lightly The results from this project are expected to be completely new and original 4 Theory and Algorithms Define randomized distance as the distance to destination node

Loading Unlocking...

Join to view Pathfinding Algorithms for Mutating Weight and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pathfinding Algorithms for Mutating Weight and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?