Optimisation and Heuristics

Many real-world problems require finding the best solution from a large set of possibilities — the shortest route, the minimum cost, the maximum profit. These are optimisation problems. When the search space is too large to explore exhaustively, we turn to heuristics — strategies that find good (but not necessarily optimal) solutions in a reasonable time.

---

What Is an Optimisation Problem?

An optimisation problem has:

1. A set of possible solutions (the search space)
2. An objective function that assigns a value to each solution
3. A goal to minimise or maximise the objective function

Example: The Travelling Salesman Problem (TSP)

• Input: A set of cities and the distances between each pair.
• Objective: Find the shortest route that visits every city exactly once and returns to the start.
• Search space: All possible orderings of cities = n! permutations.

For 20 cities: 20! = 2.4 × 10¹⁸ possible routes. Even a computer checking 1 billion routes per second would take 76 years to check them all.

---

Tractable, Intractable, and Computable Problems