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.

Roentgenology

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).

Demark

A greedy algorithm can be proven to yield a global optimum in many cases. An example is the unweighted interval selection problem. – Thermometer

A slight correction, because a problem belongs to the NP-complete class doesn't mean that there exists no efficient means of solving it. It just means that one hasn't been discovered and it is very unlikely that it exist. en.wikipedia.org/wiki/NP-completeness. Also see simple.wikipedia.org/wiki/P_versus_NP. This basically proposes the question of if we can check the solution of a problem in polynomial time, does this mean we can also solve it in polynomial time. – Makkah

I disagree. Dijkstra is greedy (the next node we choose is the best option available in a local vicinity) yet it is not heuristic! (as in that choice is not based on a heuristic or an ad-hoc prediction, but rather on facts/pre-existing knowledge). Dijkstra also refines itself based on new information, despite being greedy by and that's exactly why it's complete. – Scandian

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.

Logorrhea

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.

Boatswain

Answer 4

These are two different things: greedy algorithms try to take "the best choice" upon every iteration (for example, if you choose edges in a graph by their length, it'll pick the longest/shortest edge possible in every iteration). Greedy algorithms supply an exact solution!

Heuristic algorithms use probability and statistics in order to avoid running through all the possibilities and provide an "estimated best solution" (which means that if a better solution exists, it will be only slightly better).

Partlow

"Greedy algorithms supply an exact solution!" - Not sure about that. I call 'greedy' all algorithms that use a greedy approach, even if they don't result in an exact solution. – Ithyphallic

"Exact" as in "optimal"? No, most greedy algorithms aren't optimal. – Orvas

“A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.” – Pressey

@Dukeling: I think he meant "exact" as in "not approximate". Which, imo, is not correct either. – Ithyphallic

@Ithyphallic mind providing an example of a greedy algorithm that doesn't provide an exact solution ? – Partlow

@alfasin Yes, that's what I was talking about too. You don't have to look far to find a few examples of where greedy algorithms fail ("fail" as in either no solution, or a less-than-optimal one) - any decent resource on greedy algorithms should mention the non-optimality, and should give an example. – Orvas

@alfasin matrix chain multiplication, at every step make the "smaller" multiplication (the one which requires the least number of operations). Greedy, yet inexact solution. e.g A = 100x5; B = 5x20; C = 20x10000; D = 10000x1 Greedy algorithm: ABCD->(AB)CD->(AB)(CD)->((AB)(CD)) = 212000 Better solution: ABCD->AB(CD)->A(B(CD))->(A(B(CD))) = 200600 – Ithyphallic

@Dukeling, LesertS: if a greedy algorithm fails to solve a problem it means that it's not the right tool for the problem - not that there is a problem with this type of algorithms. Maybe it was too obvious to me but I should have stated it anyways: not every problem has a greedy algorithm that solves it. – Partlow

It could be the 'right' tool, even if it doesn't find the optimal solution, because the solution may be 'good enough' for whomever is using it. You can't justify saying that greedy algorithms provide an optimal solution (always, i.e. for all problems, is implied) by saying that greedy algorithm don't provide an optimal solution for certain problems - that's a contradiction - you could, however, say that greedy algorithms exist that (always) provide an optimal solution for some problems. – Orvas

@Dukeling I never used the word "optimal" - you used it :) I said that greedy algorithms provide an "exact solution" vs. Heuristic algorithms which provide a "good enough" solution. Second, you keep misinterpreting what I write. It's like I'm saying that a car drives and you keep saying "but not in the water". An algorithm, by definition, provides exact steps to solve a problem. If the steps don't solve the problem - this is not a good algorithm (tool), greedy or not. Since there isn't one family of algorithms that can solve ALL the problems, your comments are pointless... – Partlow

You said "exact", I asked "optimal", you didn't comment on that, so I assumed you meant optimal. I can't justifiably use the term "exact" since I'm not extensively familiar with it used in terms of algorithms, and I find it somewhat ambiguous, thus I opted for "optimal", which, by the way (unambiguously) means "the best possible [solution]". For all problems that you can create a greedy algorithm for is implied. And "good enough" is based on the application, so you can't say heuristics are "good enough". – Orvas

Answer 5

Notice: I am not sure what follows applies to me and my "social circle" or is a standard - global concept.

In my mind an heuristic algorithm is, as Wikipedia puts it:

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.

A greedy algorithm, on the other hand, is what you described: an algorithm that tries to find the best solution by selecting the best option at every step. That's pretty much it. This doesn't imply anything about the solution: sometimes a greedy algorithm provides the perfect and optimal solution, while some other times it may just be an heuristic -> approximate (not perfect) but faster solution.

Ithyphallic