2.3.5 Path Finding algorithms
No description yet. This curated deck is ready for daily study.
Card preview (8)
Similarities between Dijkstra algorithm and A* algorithm
Both are pathfinding algorithms Both aim to find the shortest route
Differences between Dijkstra algorithm and A* algorithm
A* is considered more efficient than Dijkstra (which is slower) A* makes use of heuristic (expected) values to find solutions faster.
What is a heuristic value?
a problem-solving strategy or method that is not guaranteed to find the optimal solution, but is designed to find a satisfactory solution in a reasonable amount of time. or a mental shortcut commonly used to simplify problems and avoid cognitive overload
What does the Dijkstra algorithm use to achieve finding the shortest route?
A priority queue, which orders the magnitude of distance to each vertex from shortest to longest.
What is a pathfinding algorithm?
An algorithm designed to find the shortest path between two nodes on a network
What is performance modelling?
A method to model these scenarios in a computer simulation so the full performance test does not need to happen.
Why is performance modelling used?
• To simulate/model behaviour of the system (before it is) used under load • Because it would be too expensive/unsafe/time critical to test the real system
How can a heuristic be calculated
• Euclidean theory • The Manhattan approach