Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Greedy Search
A greedy algorithm builds a solution one part at a time. At each step it adds the part chosen by a greedy rule (heuristic): the best choice for this one step only, which is called locally optimal.
Key points:
- a greedy algorithm may or may not be globally optimal (the best overall)
- it is short-sighted: it only looks one step ahead, and a misleading heuristic can send it the wrong way
- exhaustive methods such as linear search, binary search, BFS and DFS are guaranteed to find the global optimum
- for some easier problems a greedy algorithm is guaranteed to be optimal: shortest paths (Dijkstra) and minimum spanning trees (Kruskal)
Example: to find the leaf with the largest payload in a binary tree where each internal value is only a "likelihood" signpost, always stepping to the larger child can miss the best leaf. DFS or BFS will always find it.
Travelling Salesman Problem
Given cities and the distance between every pair, find the shortest route that visits each city exactly once and returns to the start. Applications include planning and logistics, microchip manufacturing and DNA sequencing.
Two approaches:
- exhaustive search: the next city has choices, then , and so on, so there are routes, which grows faster than exponential and is useless beyond about cities
- greedy (nearest neighbour): from the current city always go to the closest unvisited city, which costs but may not find the shortest route
4-City Example
There are routes. Starting at A, the greedy route takes the short edges first () but is then forced to use the long edge back to A.
| Route | Length | Note |
|---|---|---|
| 1 (greedy) | not optimal | |
| 2 | optimal | |
| 3 | another optimal route (route 2 reversed) | |
| 4 | worst | |
| 5 | worst | |
| 6 |
