Greedy Algorithms

It’s best to show how a Greedy algorithm works with an example.

Let’s say we have 3 coins:

10p

20p

50p

What is the minimum number of coins needed to make 80p, £1, or £1.40?

Sure, we could make 80p with 8 10p coins but we want to find a way to do it with the least number of coins, one of the solutions are: 10p + 20p + 50p.

The idea is for every step try to make the best move you can make and keep going until you’re done.

Let’s say we have an undirected connected graph, G, which has edges that are labelled by weight.

This is a weighted graph:

A spanning tree of G is a tree containing all vertices in G.

A minimum spanning tree is a spanning tree of G with minimum weight.

If we have a tree with n vertexes, the number of edges connecting all the vertexes are n — 1. The number of possible spanning trees is:

Kruskal’s Algorithm

Kruskal’s algorithm let’s us find the minimum spanning tree of a graph.

First we sort the edges, so the smallest weighted edge is first.

We then choose the edge with the least weight, and then we continue adding the smallest weight. If we form a cycle, don’t include that edge.

Let’s say we have a graph like so:

How would we go around finding the minimum spanning tree?

Before you say it, yes I have bad hand writing. Should I be ashemed of having bad handwriting? Nope. Don’t worry. If anything looks unreadable I’m going to write it out here so it’s readable for you. Just understand that to be a computer scientist you absolutely do not need to have handwriting other people can read, as we have computers to make readable handwriting for us.

We first must order all the edges from smallest to largest like so:

To save your eyes some strain, here’s the edges in a nice table:

Now we colour in (or choose) the smallest edge. How do we know what’s the smallest edge? We just give the table we made.

And the next one

You can skip a few of these, i’ll write STOP!!!! when something interesting happens.

Next one…

If you take your time to look at every image of this graph, highlight this!

Now the next one to highlight is (H,I). STOPPPP!!!!!!!!!!!!!!!

(H, I)? But that makes a triangle. You can go all around the triangle. Wait, is this a cycle? Yes it is!

See how easy it is to recognise when a cycle happens as a human? As a computer, it’s a lot harder. You can’t just tell it to “see” and “guess” where a cycle will be formed. We’ll come back to this topic later, but for now we’ll skip (H, I).

Look, if we add (H, I) we get a cycle!

So let’s not do that. Now we just need to add (A, H)

If we want to add (B, C) the next smallest edge we will make a cycle so let’s not do that.

We can’t include (E, F) as it’s a cycle. So let’s skip that. Actually, we can’t include any of the remaining edges, since they all form a cycle. So now we have a minimum spanning tree. It’s really quite a simple and greedy algorithm to find a minimum spanning tree of a graph.

Okay, back to detecting cycles. Let’s say you want to insert the edge (E, V) into the minimum spanning tree. We need to check to see if it is possible to get from V, to E, so a path exists from (V, E).

This sounds confusing, so let’s look at this picture again.

So we want to insert edge (H, I). To do that we need to see if a path exists which takes us from I to H already without the added edge. We can see that the path: I > C > F > G > H is a path from I to H. Because this path exists, we cannot add the edge as it would form a cycle.

You can use any of the searches above such as Breadth First Search or DFS to find this path.

You could also check the ancestors of the graph if it is a directed graph. You can navigate up until you find a parent node that is equal to the end of the edge you are wanting to add.

There is lots of ways you could do this.

Dijkstra’s Algorithm

Dijstra’s algorithm finds the shortest path from one node to every other node in the graph.

Dijkstra’s algorithm assumes that the weights of the edges are not negative.

The main concept of this algorithm is to choose the edge adjacent to the chosen vertex such that the cost of the path to the vertex is minimum.

So we start off with a weighted graph. Let’s choose A as our starting node.

We will keep a list of all unvisited nodes as well as the path cost for every node counting from A. The path from A to A is 0, so we write 0.

We don’t know the path cost of the other nodes yet, so we write infinity.

The next step is to find all the edges we can reach from A. We can reach B and C from A, so we update the table with the correct costs.

Because C is the cheapest vertex that hasn’t been visited yet, we choose C.

It only costs 3 to go from A>C>B instead of the higher A>B which costs 4 — so we write 3 in B now.

Now we read from our list of paths, which one is the cheapest? A>C is but we’ve been there (as our unvisited nodes says). We haven’t been to B yet and it’s the second cheapest, so we go there.

We finish up C using the same algorithm as before. Now we pick somewhere to go. D is cheap, so let’s go there. Normally we would read all of the edges connecting D to other nodes, but D does not have any edges connecting it to other nodes. Only edges connecting other nodes to D (directed graph, remember?).

Now the only node left is E, and we can’t get there from D. So we move backwards until we find a point where we can move to E. We can go from B to E, so let’s do that.

Now we have no more nodes to visit. We know this because our unvisited node list is now empty (all nodes are visited).

You may look at this algorithm and think “wow, this only works on graphs where we know what nodes are on it?”. Nope. It’ll work on any graph that is weighted and has nodes on it. Instead of having an unvisited list, we can have a visited list to prevent us from going back to the same place.

To know when the algorithm is completed when using a visited list, when you’re at a node and all of the edges connecting that node have been visited then you can assume that you have visited every node. You may run across a problem of finding a node and not visiting it and being stuck never having visited that node. In this case, keep a list of all nodes you’ve seen but not yet visited.

This is what every single path to every single node from A looks like:

Dijkstra’s algorithm is easy once you understand that it always chooses the path that is cheapest.

I highly recommend this article from Vaidehi Joshi for some extra learning:

Finding The Shortest Path, With A Little Help From Dijkstra

Dijkstra’s algorithm is super cool. Ever wanted to know how your SatNav finds the fastest route from your home to somewhere? It uses this algorithm. Well, their algorithm is probably slightly modified. But it’s the same principles!

Psuedocode

To describe the algorithm using psuedo code we need to give some notations first:

Each vertex, V, is labelled with two labels:

• A numeric label d(V) which indicates the length of the shortest path from the source to v found so far.
• Another label, p(V), which indicates next-to-last vertex on that path. IE the vertexc immeditally preceeding v on that shortest path.

Given a graph, G = (V, E) and a source vertex s:

for every vertex v in the graph:
    set d(v) and p(v) as ∞
set d(s) and Vr = 0
while v or Vr != 0:
    choose the vertex v in v or Vr with minimum d(u)
    set Vr = Vr ∪ u
    for every vertex v in v or Vr that is a neighbour of u:
        if d(u) + w(u, v) < d(v) then
            set d(v) = d(u) + w(u, v) and p(v) = u

Big O notation

Dijkstra’s algorithm is O(n²).

Knapsack Problem

In the Knapsack problem, we have a number of items with 2 attributes:

• Weight
• Value

The value and weight do not have to be scaled together.

Given n items we have:

Fancy way of saying each item has its own weight

For all weight and for values:

And we have a knapsack (bag) with a total capacity W.

We want to find the most valuable subset of items that can fit into the knapsack.

Let’s say our knapsack has a capacity of 10 and we have 3 items:

• Item 1 — Weight = 5, value = 50
• Item 2 — Weight = 2, value = 1
• Item 3 — Weight = 4, value = 7

What items can we put into the knapsack that will cause the knapsack to have the greatest possible value?

To find out we need to calculate every single subset that does not exceed the weight limit of 10. We then pick the right subset which has the maximum value out of every single subset tested.

We have to compute this many subsets:

The -1 is because we don’t have to compute the empty set.

It is 2^n because from Set Theory that’s the formal definition of a size of a powerset.

A slightly different explanation is that we use 0 and 1’s a lot.

We have n items:

_ _ _ _ _ _ …

And in our subset of these n items we can use a 1 to show that the element is in the subset or a 0 to show it is not.

If we have 3 items:

3 5 2

We can say the subset which only contains the third item is:

001

So we can use binary digits to represent the set corresponding to whether a given item is in the subset or not. We are asking how many different sequences you can have in the subset where each digit is either 0 or 1.

This type of function is called exponential as it grows exponentially as n grows.

This is an exhaustive algorithm, we try every single subset to find the correct one. This is very slow. Let’s take a set which contains 10 items and see how many subsets we have to test to find the correct one.

And if we wanted to test 11 items, it’ll be 1024 items to test. It grows exponentially and takes forever to find the correct one.

We can use a greedy algorithm to hasten the computation.

We pick the item with the highest value as long as it doesn’t go over the total weight and we continue picking these items.

Let’s say we have these items:

item 1
w = 10
v = 60

item 2
w = 20
v = 100

item 3
w = 30
v = 120

And a knapsack which can hold a weight of 50.

We pick the item with the largest value which can still fit into the knapsack.

We pick item 3 as it can fit into the knapsack and has the largest value. So our knapsack now has a remaining weight of 20.

We then pick item 2 since it can fit into the knapsack.

Our total value is now 220 and the knapsack is full so we stop.

Instead of continually going through the list to find the item with the largest value it is worthwhile to sort the itesm by most valuable first.

Sometimes the greedy algorithm does nto always work. Maybe it is because we are being greedy on the value alone. Maybe we should include all attributes in our greedy algorithm.

We can do this in our algorithm by calculating value divided by weight for every item. We can sort by the largest value / weight first.

There is another algorithm we can use. Instead of selecting the largest value / weight we can select the smallest.

This greedy algorithm isn’t always the best, but a therom states that this greedy algorithm has an approximation ratio of at least 1/2. It always selects a subset with total value of at least 1/2.