2.3.5 Path Finding algorithms

Question 1

Similarities between Dijkstra algorithm and A* algorithm

Answer 1

Both are pathfinding algorithms

Both aim to find the shortest route

Question 2

Differences between Dijkstra algorithm and A* algorithm

Answer 2

A* is considered more efficient than Dijkstra (which is slower)

A* makes use of heuristic (expected) values to find solutions faster.

Question 3

What is a heuristic value?

Answer 3

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

Question 4

What does the Dijkstra algorithm use to achieve finding the shortest route?

Answer 4

A priority queue, which orders the magnitude of distance to each vertex from shortest to longest.

Question 5

What is a pathfinding algorithm?

Answer 5

An algorithm designed to find the shortest path between two nodes on a network

Question 6

What is performance modelling?

Answer 6

A method to model these scenarios in a computer simulation so the full performance test does not need to happen.

Question 7

Why is performance modelling used?

Answer 7

• 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

Question 8

How can a heuristic be calculated

Answer 8

• Euclidean theory
• The Manhattan approach