# Greedy Algorithm **A type of optimisation algorithm design which divides an optimisation problem into successive subproblems.** ![[ActivitySelectionGreedy.svg|500]] *The activity selection problem[^1] is a common example of a greedy algorithm problem* A **greedy algorithm** is a type of optimisation algorithm design which divides optimisation problems with a notion of a beginning and an end into *successive subproblems*. At each stage, the algorithm chooses from a set of possible solutions the *locally optimal solution* and adds it to its globally optimal solution. A problem solvable by a greedy algorithm must have an *optimal substructure* which means that the optimal solution consists solely of optimal solutions to its subproblems. ## Failure In most cases, greedy algorithms can only *approximate* a globally optimal solution when run in a *reasonable amount of time* and there are problems for which a greedy algorithm can never find the optimal solution. The main reason a greedy algorithm fails is due to the fact that each choice may depend on previous choices but they never depend on *future choices* or *all current possible choices*, thus resulting in the horizon effect. Additionally, since greedy algorithms run iteratively through successive stages, they *never reconsider old choices*. These properties distinguish greedy algorithms from more exhaustive [[dynamic programming]] algorithms. ## Proof of correctness There are two common methods of proving the correctness of a greedy algorithm: a *greedy stays ahead* proof and an *exchange argument*. ### Greedy stays ahead A *greedy stays ahead* proof involves proving that every sequence of choices made by the algorithm is always *at least as good as or better* than any other possible sequence of choices, by some sort of measure. Typically a greedy stays ahead proof relies on induction to prove correctness across all stages of the algorithm. > [!Example]- Example - activity selection algorithm > Consider the greedy algorithm demonstrated in the graphic above. > > > [!Algorithm] > > From the activities that do not conflict with previously chosen ones, choose the activity with the earliest end time. > > Let $A=\{i_{1},\dots, i_{k}\}$ and $O=\{j_{1},\dots,j_{m}\}$ be the solution provided by the greedy algorithm and an optimal solution respectively, sorted by their finish times. > > In a process similar to mathematical induction, it can be proved that for all $n\le k$, $i_n$ always finishes earlier than or at the same time as $j_n$. > > For the base case $n=1$, it is clear that $i_1$ finishes *earlier than* or *at the same time as* $j_1$, since the algorithm always chooses the activity with the earliest end time and there are no activities to conflict with yet. > > Assuming the statement is true for any $n=t$, it must also be true that $i_{t+1}$ has an earlier or equal finish time to $j_{t+1}$, since any activity $j_{t+1}$ must: > - start after $j_{m}$ ends for all $m\le t$; in order to not overlap > - start after $i_{k}$ ends for all $k\le t$; assuming the statement is true for any $n=t$. > > This means that $j_{t+1}$ is a valid activity that can be added to the greedy solution $A$ and thus the statement is also true for any $n=t+1$. > > Therefore, it is true that for all $n\le k$, $i_n$ has an *earlier or equal finish time* to $j_n$. > > Suppose the greedy solution $A$ was *not optimal*, which means the optimal solution $O$ has more activities - i.e. $m > k$ - and there is an activity $j_{k+1}$ not in $A$. As this activity must start after $j_{k}$ ends, the above proof implies that it also starts after $i_{k}$ ends. If this was the case, it must be *also be within the greedy solution* which is a contradiction. > > Thus, the greedy solution *is optimal*. Some authors argue that it is more intuitive to refer to this type of proof as *greedy never falls behind* due to how the these types of proofs are actually set out. ### Exchange argument In an *exchange argument*, some alternative optimal solution is compared to the greedy solution by demonstration of the existence of an [[injective function]] between corresponding parts of the solution. This is done by *progressively substituting* parts of the greedy solution into the alternative solution and proving that it *remains the same or improves* in terms of performance. The argument is complete when the alternative solution is transformed into the greedy solution. > [!Example]- Example - activity selection algorithm > Consider the greedy algorithm demonstrated in the graphic above. > > [!Algorithm] > > From the activities that do not conflict with previously chosen ones, choose the activity with the earliest end time. > > A graphical illustration of the timeline of activities helps make the exchange argument: > > ![[ActivitySelectionGreedyExchangeArgument.svg|550]] > *The alternative solution (red) being transformed through substitutions (orange) until it becomes the greedy solution (yellow)* > > As every exchange from the alternative to the greedy solution did not change the number of activities during the transformation, the greedy solution is also an optimal solution. [^1]: The *activity selection problem* involves finding a set of the most non-overlapping activities.