Greedy Algorithm

All data structures are combined, and the concept is used to form a specific algorithm. All algorithms are designed with a motive to achieve the best solution for any particular problem. In the greedy algorithm technique, choices are being made from the given result domain. As being greedy, the next to a possible solution that looks to supply the optimum solution is chosen.

The greedy method is used to find restricted most favorable result which may finally land in globally optimized answers. But usually, greedy algorithms do not give globally optimized solutions.

A game like chess can be won only by having ideas ahead: a player who is alert entirely on immediate benefit is easy to defeat. But in some other games such as Scrabble, it is likely to do quite well by just making whichever move seems finest at the moment and not worrying too much regarding the future consequences or cost.

These kind of myopic activities are easy and suitable for making this a smart logarithmic strategy. Greedy algorithms build up a solution piece by piece, by constantly choosing the next piece which offers the most obvious and instant benefit. Although this kind of approach can be disastrous for some computational jobs yet there are many for which it is best suitable. The first example that you will be going to understand is the minimum spanning trees.

Minimum Spanning Trees

Suppose you are invited to create a networked collection of computers by connecting selected pairs of those computers. This translates this into a graph problem wherein all nodes are computers, undirected edges are possible links, and the objective is to pick enough of these edges which the nodes are associated with. And that is not all; each link has a maintenance cost which will reflect in those edge's weight. What is the cheapest possible network?

So what you can do is make a graph that will be having six vertices/nodes named A, B, C, D, E, and F and assign each edge with a value. So it will be an undirected weighted graph.

undirected weighted graph

One instant study is that the optimal set of edges will not contain a cycle as because taking away or removing an edge from this cycle would lessen the cost without cooperating connectivity:

Removing a cycle edge will not disconnect a graph. Hence, the answer must be connected and acyclic: undirected graphs of this type are termed as trees. The particular tree you want to put is the one with the least total weight that is called as the minimum spanning tree. Here is its proper symbolic definition:

minimum spanning tree

Most of the networking algorithms used today utilize the concept of a greedy approach. Here is a list of few of such problems:

  1. Travelling Salesman Problem
  2. Prim's Minimal Spanning Tree Algorithm
  3. Kruskal's Minimal Spanning Tree Algorithm
  4. Dijkstra's Minimal Spanning Tree Algorithm
  5. Graph - Map Coloring
  6. Graph - Vertex Cover
  7. Knapsack Problem
  8. Job Scheduling Problem

Furthermore, there are lots of related problems that use the concept of the greedy algorithm for finding the most favorable solution.