Greedy Algorithm: Optimal Substructure

Question

I don't have a CS degree but I have recently taken up studying algorithms very seriously.

I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.

e.g. I don't understand what they mean by optimal solution, what constitutes an optimal solution, how can I define it?

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem

Answer 1

Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.

To answer your question, let's look at a simple example, change-making problem:

Given a set of integer values of coins $C = \{c_1, …, c_n\}$ and an amount $W$, what is the minimum number of coins to add-up to the amount $W$?

The classical greedy approach is the following:

While W > 0
   pick the largest coin c that is <= W
   W <- W - c

For example, with $C = \{1, 2, 5\}$ and $W = 13$, you will pick $5$, $5$, $2$ and $1$, and you can show that the minimum number of coins required is indeed $4$.

However, this algorithm does not always provide an optimal solution. For example, if $C = \{1, 4, 5\}$ and $W = 8$, the greedy algorithm will choose coins $5, 1, 1, 1$ when there is a solution $4, 4$ using less coins.

Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $C$

Answer 2

Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function.

For example, take the following problem: You are a cashier in a shop, and a customer gave you an $n$-dollar bill (your country has bills of all kinds! very intriguing), for an item that costs only $k<n$ dollars, and you want to give the customer correct change. However, your cashing station has only limited amount of bills of each type, and this information is given to you in a list with tuples of the form (dollar value, number of dollars in cashing station). But, you also want to keep the number of bills in your station as large as possible, so you could give change to other customers as well.

In this problem, a "solution" would be a way to give change to the customer, and an "optimal solution" is a solution that also keeps as many bills as possible in the station

Answer 3

Check e.g. Jeff Erickson's Algorithms (warning, somewhat though going), it has a thorough chapter on greedy algorithms. He also warns that greedy algorithms very rarely give optimal results (The underlying problem has to have a very particular structure for them to work in all cases, see e.g. Jeremy Kun's "When Greedy Algorithms are Perfect". Sure, several very important algorithms are greedy algorithms.).

Greedy algorithms are attractive as a way to get approximate solutions, as they are usually simple to code and very fast, and they sometimes get good solutions (can be proved are within some reasonable factor of the optimal solution).