19.2. Greedy Algorithms Overview

Let us take another look at greedy algorithms. So, we are looking at algorithms where we need to achieve a global optimum by making a sequence of choices. In a greedy strategy, what we do is we make the next choice based on some local criteria. We only pick one of the possible choices based on what looks good at the moment, and we never go back to revise an earlier decision. This drastically reduces the space in which we have to search.

Greedy algorithms work by making a series of decisions that seem best at each moment, without looking ahead. This means that at every step, the algorithm picks the option that appears to be the most beneficial. For instance, if you are trying to find the best route to get somewhere and you choose the road with the least traffic at every intersection, that’s a greedy algorithm in action. However, this approach can lead to suboptimal solutions because the immediate best option may not lead to the best overall outcome.

Think about a friend choosing a sequence of movies to watch. If their friend picks the movie with the most exciting cover art for their first choice, that might seem like a great idea. But later, if they miss watching a highly-rated film that was released earlier—one that could have been more enjoyable—this shows how going for immediate appeal rather than considering the overall experience can lead to a less satisfying movie night.

We have seen three algorithms so far which follow this greedy paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem. In this algorithm, we kept burning vertices and at each stage, we froze the distance to the nearest unburnt vertex. The global optimum here is the shortest distance from the source.

In Dijkstra's algorithm, we start from one point (the source) and explore the closest vertices incrementally, ensuring that we always have the shortest known distance to each vertex during the process. This method allows us to efficiently find the shortest paths in a network, like navigating a city using the shortest roads. The greedy nature of picking the nearest point allows for quick calculations, avoiding exhaustive searches.

Imagine you are in a new city. You want to visit several places and decide to head to the closest one first. After that, you choose the next closest location from where you are. By always going to the nearest site, you simplify your journey without having to assess every possible route from scratch—just like how Dijkstra’s algorithm works in finding the shortest path!

A closely related algorithm is Prim’s algorithm for the minimum cost spanning tree. Here, we incrementally build up a tree by adding the nearest vertex that is not yet in the tree. Another algorithm for minimum cost spanning tree is Kruskal’s algorithm. Instead of building up a tree directly, we collect edges to form a connected component, adding the smallest edge that does not create a cycle.

Prim’s algorithm focuses on expanding a growing tree by always selecting the edge with the minimum cost that connects a new vertex to the tree. In contrast, Kruskal’s algorithm builds the spanning tree by sorting and adding edges in the order of their weight, ensuring no cycles form. Both methods are examples of how greedy approaches can efficiently find an optimal solution for connecting points at minimal cost.

Consider a community garden where you want to lay out paths connecting different flower beds. Prim’s algorithm would suggest adding paths from one bed to the closest unconnected one. On the other hand, Kruskal’s algorithm would start by identifying small pathways and gradually building connections, ensuring no paths intersect where they shouldn't. Using either method helps you to efficiently plan the layout without unnecessary overlaps or costs.

Now, let us look at a completely different problem called interval scheduling. Suppose we have a special video classroom where different teachers want to book the classroom. Our task is to choose a subset of bookings such that no two overlapping bookings are chosen, thus maximizing the number of teachers who get to use the room.

The interval scheduling problem involves making choices from a set of intervals (or time slots) while ensuring that no two slots overlap. A greedy solution could start by selecting the booking that ends the earliest, thereby leaving room for more teaching slots afterward. This strategy works because choosing shorter bookings can allow for more total bookings in the long run, maximizing usage of resources.

Imagine a conference room where different groups want to hold meetings. If you have several groups wishing to use that room, you want to allocate time slots to maximize the use of the room. If you always start with the group that needs the shortest time first, you might find that more groups can successfully hold meetings throughout the day, rather than letting a single long meeting take up an entire morning.

If we follow a greedy approach, we pick one booking based on some local strategy and remove all conflicting bookings. However, there are many potential strategies, and not all will yield the optimal solution. For example, just picking the earliest starting time can lead to suboptimal solutions.

When applying a greedy algorithm, one must carefully consider the criteria for making decisions. Some strategies, such as always choosing the earliest start time, may seem effective but can lead to missed opportunities for maximizing total bookings. Counterexamples can show that different approaches yield better results, which emphasizes the importance of testing the chosen strategy against various scenarios.

Picture a restaurant where tables can be reserved for groups. If the restaurant manager always reserves the earliest table, they may end up with many early reservations that do not optimally fill the restaurant throughout the evening. A better strategy might be to assess the size of the bookings and arrange them to keep tables filled at all times, maximizing the restaurant’s capacity.

One promising strategy in the scheduling problem is to choose the booking whose finish time is the earliest. This strategy proves to be successful, and we can formally outline this algorithm.

Choosing the booking with the earliest finish time ensures that other potential bookings can still fit into the schedule afterward. By developing an algorithm that selects the booking with the shortest duration first, we can maximize the total number of non-overlapping bookings. The process entails removing any conflicting schedules as new bookings are added consecutively.

Imagine trying to fit as many tasks into your day as possible. If you always complete the tasks that take the least time first, you create 'gaps' where other longer, more meaningful tasks can fit later, thereby expanding what you can accomplish throughout the day.

--