what does it mean to be a greedy algorithm

Structure of a Greedy Algorithm

Greedy algorithms have all of the data in a item problem, and then gear up a rule for which elements to add together to the solution at each step of the algorithm. In the animation above, the set of data is all of the numbers in the graph, and the rule was to select the largest number available at each level of the graph. The solution that the algorithm builds is the sum of all of those choices.

If both of the backdrop beneath are true, a greedy algorithm can be used to solve the problem.

• Greedy choice property: A global (overall) optimal solution can be reached by choosing the optimal selection at each step.
• Optimal substructure: A trouble has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.

In other words, greedy algorithms work on issues for which it is true that, at every step, there is a choice that is optimal for the problem up to that footstep, and afterward the last stride, the algorithm produces the optimal solution of the consummate problem.

To make a greedy algorithm, identify an optimal substructure or subproblem in the problem. And so, make up one's mind what the solution will include (for case, the largest sum, the shortest path, etc.). Create some sort of iterative way to go through all of the subproblems and build a solution.

4 to 5 to 8 iv to 7 to 3 4 to 5 to 4 to nine four to 7 to 2 to ten

If there is a greedy algorithm that will traverse a graph, selecting the largest node value at each bespeak until it reaches a leaf of the graph, what path will the greedy algorithm follow in the graph below?

What is the length of the longest path through the graph below? Calculate the length by adding the values of the nodes.

Sometimes greedy algorithms fail to find the globally optimal solution because they do not consider all the data. The pick made by a greedy algorithm may depend on choices it has made then far, just it is non enlightened of future choices information technology could make.

In the graph below, a greedy algorithm is trying to observe the longest path through the graph (the number inside each node contributes to a full length). To practise this, information technology selects the largest number at each footstep of the algorithm. With a quick visual inspection of the graph, it is clear that this algorithm volition not arrive at the right solution. What is the correct solution? Why is a greedy algorithm sick-suited for this problem?

An case of greedy algorithm, searching the largest path in a tree^[2]

---

The right solution for the longest path through the graph is $7, 3, 1, 99$ . This is articulate to us considering nosotros tin can see that no other combination of nodes will come close to a sum of $99$ , and then any path we choose, nosotros know information technology should accept $99$ in the path. There is only one option that includes $99$ : $seven, iii, 1, 99$ .

The greedy algorithm fails to solve this problem because it makes decisions purely based on what the all-time answer at the time is: at each step information technology did choose the largest number. Notwithstanding, since there could be some huge number that the algorithm hasn't seen yet, it could end upward selecting a path that does not include the huge number. The solutions to the subproblems for finding the largest sum or longest path do not necessarily appear in the solution to the total problem. The optimal substructure and greedy option backdrop don't hold in this type of trouble. $_\foursquare$

Hither, we will look at i form of the knapsack problem. The knapsack problem involves deciding which subset of items you should have from a set of items if you lot want to optimize some value: perhaps the worth of the items, the size of the items, or the ratio of worth to size.

In this problem, we will assume that we can either accept an item or get out it (we cannot accept a fractional part of an item). We will also assume that in that location is only one of each item. Our knapsack has a fixed size, and we desire to optimize the worth of the items we have, so we must choose the items we take with care.^[3]

Our knapsack tin can hold at about 25 units of space.

Here is the list of items and their worths.

Item	Size	Price
Laptop	22	12
PlayStation	x	9
Textbook	ix	ix
Basketball game	7	six

Which items exercise nosotros choose to optimize for price?

---

There are two greedy algorithms we could advise to solve this. One has a rule that selects the item with the largest price at each step, and the other has a dominion that selects the smallest sized item at each step.

• Largest-price Algorithm: At the beginning step, we have the laptop. We gain $12$ units of worth, but can now only carry $25-22 = 3$ units of additional infinite in the knapsack. Since no items that remain will fit into the bag, we tin only take the laptop and take a full of $12$ units of worth.
• Smallest-sized-item Algorithm: At the kickoff stride, we will take the smallest-sized item: the basketball. This gives u.s. $6$ units of worth, and leaves us with $25-vii = 18$ units of space in our bag. Next, we select the side by side smallest item, the textbook. This gives u.s. a total of $six+9 =fifteen$ units of worth, and leaves us with $eighteen-nine = ix$ units of infinite. Since no remaining items are $ix$ units of space or less, nosotros can have no more than items.

The greedy algorithms yield solutions that give usa $12$ units of worth and $15$ units of worth. But neither of these are the optimal solution. Inspect the tabular array yourself and encounter if you tin determine a better selection of items.

Taking the textbook and the PlayStation yields $nine+9=xviii$ units of worth and takes upwards $x+ix=19$ units of infinite. This is the optimal answer, and nosotros can see that a greedy algorithm will non solve the knapsack problem since the greedy option and optimal substructure properties practice not hold. $_\square$

In issues where greedy algorithms fail, dynamic programming might be a better approach.

At that place are many applications of greedy algorithms. Below is a cursory explanation of the greedy nature of a famous graph search algorithm, Dijkstra's algorithm.

Dijkstra's Algorithm

Dijkstra'southward algorithm is used to discover the shortest path between nodes in a graph. The algorithm maintains a set of unvisited nodes and calculates a tentative distance from a given node to some other. If the algorithm finds a shorter mode to get to a given node, the path is updated to reflect the shorter altitude. This trouble has satisfactory optimization substructure since if $A$ is connected to $B,$ $B$ is connected to $C$ , and the path must become through $A$ and $B$ to get to the destination $C$ , and so the shortest path from $A$ to $B$ and the shortest path from $B$ to $C$ must exist a part of the shortest path from $A$ to $C$ . So the optimal answers from the subproblems do contribute to the optimal answer for the total problem. This is because the algorithm keeps track of the shortest path possible to whatever given node.

Dijkstra'southward algorithm to detect the shortest path between a and b. Information technology picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbour, and updates the neighbor'south distance if smaller. Mark visited (set to red) when done with neighbors.^[four]

Huffman Coding

Huffman encoding is another example of an algorithm where a greedy approach is successful. The Huffman algorithm analyzes a message and depending on the frequencies of the characters used in the bulletin, it assigns a variable-length encoding for each symbol. A more usually used symbol will accept a shorter encoding while a rare symbol will have a longer encoding.

The Huffman coding algorithm takes in information about the frequencies or probabilities of a particular symbol occurring. It begins to build the prefix tree from the bottom upwards, starting with the ii least likely symbols in the list. It takes those symbols and forms a subtree containing them, and and so removes the individual symbols from the list. The algorithm sums the probabilities of elements in a subtree and adds the subtree and its probability to the list. Next, the algorithm searches the listing and selects the ii symbols or subtrees with the smallest probabilities. It uses those to brand a new subtree, removes the original subtrees/symbols from the list, and then adds the new subtree and its combined probability to the listing. This repeats until in that location is 1 tree and all elements take been added. At each subtree, the optimal encoding for each symbol is created and together composes the overall optimal encoding.

For many more than applications of greedy algorithms, see the Run across Too section.

• A* Search
• Dijkstra's Shortest Path Algorithm
• The Travelling Salesman Problem
• Huffman Encoding
• Dynamic Programming

1. , Due south. Greedy-search-path-example. Retrieved May ii, 2016, from https://en.wikipedia.org/wiki/File:Greedy-search-path-case.gif
2. , S. Greedy-search-path. Retrieved May 4, 2016, from https://eatables.wikimedia.org/wiki/File:Greedy-search-path.gif
3. Okie , . Greedy Algorithms. Retrieved May 2, 2016, from http://world wide web.radford.edu/~nokie/classes/360/greedy.html
4. , I. Dijkstra Animation. Retrieved May 2, 2016, from https://commons.wikimedia.org/wiki/File:Dijkstra_Animation.gif

cranfordhillieve.blogspot.com

Source: https://brilliant.org/wiki/greedy-algorithm/

Share this post