What is a greedy algorithm

Greedy algorithm

You don't know what Greedy algorithms are and what they are, for example, with shortest routes have to do? Then you are exactly right here!

  • Greedy algorithm definition
    in the text
  • Example of a greedy procedure
    in the text

Greedy algorithm definition

Greedy algorithms often find fast a solution, while other algorithms cannot deliver a result in a finite time.

Often, however, it is the solution found by a greedy algorithm Not to the optimal solution for the problem. This is due to the way these algorithms work. It will always be that currently the best decision made regardless of previous choices or the effects of this choice.

To the greedy, so to the greedy algorithms, for example, count the Algorithm of Prim, the Kruskal's algorithm and the Dijkstra's algorithm.

Example of a greedy procedure

Let's take a closer look at a small one example at. You are presented with the following graph:

Your job is that cheapest way of Node Ato F to find.

How do you proceed? Clear! You realize it 2 ways there and choose the one who, in total, the lowest cost Has. So it is possible for you with Cost of 75 from A to F to get. But what would a simple greedy algorithm to do?

Let's start at Node A. The task of the greedy algorithm is now that of the cheapest partial solution to choose. So he sees that the Way from A to B for something better is than that from A to C and thus defines that this is the preferred route.

Since it is now no further options there is more, so becomes a way with Total cost of 351 the way with Cost of 75 preferred just because of very first step cheaper is. This is a good way of seeing why greedy algorithms are so common not the optimal solution deliver.

Then why should you use it? Imagine there were not just two but one very large number of possibilities.

A greedy algorithm just has to go through the graph and always the cheapest option while a normal algorithm would have to test every single possibility. Since this is often not possible in a finite time, these are greedy algorithms essential for many problems.

Great, you know what now Greedy algorithms and what they are used for. You also learned why she was a fast, but not necessarily optimal solution deliver.