Section 8 Chapter 48 - Optimisation Algorithms

Question 1

Examples of optimisation problems (4)

Answer 1

• Scheduling
• Finding the best move in a chess problem
• Timetabling
• Finding the shortest path

Question 2

Application of shortest path algorithm (2)

Answer 2

Finding the shortest route by road

Navigating a maze

Question 3

Djikstra’s algorithm

Answer 3

Finds the shortest path between two nodes in a graph. It is a breadth first search, but uses a priority queue rather than a FIFO queue