What's the difference between greedy and heuristic algorithm?

Question

What's the difference between greedy and heuristic algorithm?

I have read some articles about the argument and it seems to me that they are more or less the same type of algorithm since their main characteristic is to choose the best (local) option at each iteration to solve a problem.

Answer 1

The way that Heuristics have been described to me is that they are "rules of thumb". Their ability to produce a globally optimal solution may not be directly provable but typically, they do a good job. They're often used when the cost of determining an optimal solution is too high. Furthermore, Heuristics often encode a degree of experience on how the problem was solved in the past. A better way to describe a Heuristic is a "Solving Strategy".

A Greedy algorithm is one that makes choices based on what looks best at the moment. In other words, choices are locally optimum but not necessarily globally optimum (it might be if lucky but you can't prove it). Furthermore, a Greedy algorithm doesn't typically refine its solution based on new information. This is but one solving strategy (a.k.a a heuristic).

To provide an example of how a greedy algorithm might work, if you were to use one to help you plan a route to drive from one side of the country to the other in the shortest distance, it would likely choose the short slow roads. It wouldn't necessarily understand that a motorway, although longer and perhaps more direct, would be the better option.

An alternative strategy (heuristic) might seek to cover as much of the journey using motorways (because for most destinations, they tend to be more direct), and then resort to use normal roads to transition between. In some circumstances, it would probably perform quite lousy but in most, it would do quite well, and to be honest, it's probably a similar heuristic we all use when commuting (if not using a satnav).

Wrapping up...

• Are all Heuristics, Greedy Algorithms - No

• Are all Greedy Algorithms, Heuristics - In general, yes.

To help provide some background, one of the first problems I was taught in my algorithms class at university was the Traveling Salesman Problem. It belongs to the NP-complete class of problems meaning that there exists no efficient means of solving. That is to say as the size of the problem grows, the time taken to find a solution grows substantially. There exists a number of proveable algorithms but their performance isn't great and in real world applications, we tend to favour heuristics (which include Greedy Algorithms - see link).

Answer 2

their main characteristic is to choose the best (local) option at each iteration

Not at all true for heuristics. Heuristic algorithms are making choices that are know to be suboptimal in theory, but have been proved in practice to produce reasonable results. Heuristics usually find an approximate solution:

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed.

Greedy is an example of heuristic (make the best local choice and hope for the optimal global result), but that does not mean heuristics are greedy. There are many heuristics completely unrelated to greedy, eg. genetic algorithms are considered heuristic:

In the computer science field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection.

Answer 3

Greedy is said when you aggregate elements one by one to the solution (following some choice strategy) and never backtrack. Example: straight selection sort can be considered a greedy procedure.

Heuristic is a generic term that denotes any ad-hoc/intuitive rule used with the hope of improving the behavior of an algorithm, but without guarantee. Example: the median-of-three rule used to choose the pivot in Quicksort.