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

Classification	Definition	Example
Tractable	Can be solved in polynomial time — O(nᵏ) for some constant k	Sorting: O(n log n)
Intractable	Cannot be solved in polynomial time for all inputs; best known algorithms are exponential or factorial	TSP: O(n!) brute force
Computable	Can be solved by an algorithm (may take a very long time)	TSP (brute force does terminate)
Non-computable	Cannot be solved by any algorithm	The Halting Problem

Exam Tip: Tractable does NOT mean "easy" — it means solvable in polynomial time. O(n¹⁰⁰) is technically tractable but impractical. In practice, we consider O(n²) or O(n³) as "reasonable".

---

Why Brute Force Fails for Intractable Problems

n	n²	2ⁿ	n!
10	100	1,024	3,628,800
20	400	1,048,576	2.4 × 10¹⁸
50	2,500	1.1 × 10¹⁵	3 × 10⁶⁴
100	10,000	1.3 × 10³⁰	9.3 × 10¹⁵⁷

For exponential and factorial problems, brute force becomes impossible even for moderate n. This is why we need heuristics.

---

What Is a Heuristic?

A heuristic is a problem-solving strategy that produces a good enough solution in a reasonable time, without guaranteeing the optimal solution.

Properties of Heuristics

Property	Detail
Not guaranteed optimal	The solution may not be the absolute best, but it is close
Much faster	Runs in polynomial time instead of exponential/factorial
Problem-specific	Different problems require different heuristics
Trade-off	Speed vs solution quality

---

Common Heuristic Approaches

1. Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping to find a globally good solution.

Nearest Neighbour Heuristic for TSP:

1. Start at any city.
2. Travel to the nearest unvisited city.
3. Repeat until all cities are visited.
4. Return to the start.

This runs in O(n²) — much faster than O(n!) — but does not guarantee the shortest route.

Example: