GREEDY ALGORITHM

An algorithm is intended to accomplish ideal answer for a given issue. In greedy algorithm approach, choices are produced using the given arrangement space. The name itself suggests that the nearest arrangement which gives appearance of ideal arrangement is chosen by this algorithm. Greedy is an algorithmic worldview that develops an answer bit by bit, continually picking the following bit that offers the most self-evident and prompt advantage. A few issues have no productive arrangement; however, a greedy algorithm may give an answer that is near ideal.

Greedy Algorithms have their own advantages and disadvantages . It is very simple to think of a greedy calculation for an issue. Breaking down the run time for greedy algorithms will by and large be a lot simpler than for different procedures. For the Divide and conquer strategy, it isn’t certain whether the method is quick or moderate. This is on the grounds that at each degree of recursion the size of gets more modest and the quantity of sub-issues increments. The troublesome part is that for greedy algorithms you need to work a lot harder to comprehend rightness issues. Indeed, even with the right calculation, it is difficult to demonstrate why it is right. Where to utilize Greedy algorithms?

An issue should contain these two segments for a greedy calculation to work:

· It has ideal bases. The ideal answer for the issue contains ideal answers for the sub-issues.

· It has a greedy property . In the event that you settle on a decision that appears to be the awesome the second and take care of the leftover sub-issues later, you actually arrive at an ideal arrangement. You won’t ever need to reevaluate your prior decisions.

How would you choose which decision is ideal? Expect that you have a target work that should be either maximized or minimized at a given point. A Greedy calculation settles on greedy decisions at each progression to guarantee that the target work is streamlined. The Greedy calculation has simply one shot to figure the ideal arrangement with the goal that it never returns and turns around the choice. Greedy algorithms have five parts:

· A selection function, which picks the best candidate to be added to the solution

· A solution function, which will show when we have found a total solution

A candidate set, from which a solution is made

· An objective function, which allots a worth to a solution, or an incomplete solution, and

· A feasibility function, that is utilized to decide whether a candidate can be utilized to add to a solution

How to create a Greedy Algorithm? Given a cluster ‘x’ of integers , one has to calculate maximum number of things that could be done by him/her in given time. To complete the calculation, you must:

1. Sort the cluster an of every a non-diminishing request.

2. Select each to-do item individually.

3. Add the time that it will take to complete that to-do item into presenttime.

5. Repeat this as long as the presenttime is not exactly or equivalent to ‘t’.

Greedy algorithms give the global ideal solution every time . Some of these algorithms are:

a. Dijkstra’s Algorithm(this one has been explained for example) :

Dijkstra’s algorithm finds the shortest path from a node to each and every node in the graph. for eg we’ll be using a weighted directed graph. Each edge has a course, and each edge has a weight. It very well may be useful inside road networks. We also use the algorithm for:

IP Routing

A* Algorithm

Telephone networks

The algorithm follows these rules:

Every time we have to go to a new node , the node with smallest known distance is chosen. Whenever we’ve moved to the node, we check each of its adjoining nodes. Calculation of the distance from the adjoining nodes to the root nodes is done by adding the cost of the edges . In the event that the distance to a node is less than a known distance, we’ll update the smallest distance.

b. Kruskal’s calculation

c. Prim’s calculation

d. Huffman trees

. . .

CONCLUSION

Greedy algorithms are quick, yet may not give the ideal arrangement. They are likewise simpler to code than others. Works by settling on the most ideal decision right now .Doesn’t generally track down the ideal arrangement, yet is extremely quick. Requires practically no memory.