Greedymethod

OUTLINE Greedy introduction Characteristics and features Optimization Problem Pseudo code for greedy algorithm Greedy approach The coin changing problem Container overloading Comparison with DP Pros and Cons

GREEDY INTRODUCTION Greedy algorithms are simple and straightforward. They are shortsighted in their approach A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the sub problems do not have to be known at each stage, instead a "greedy" choice can be made of what looks best for the moment.

CHARACTERISTICS AND FEATURES To construct the solution in an optimal way. Algorithm Maintains two sets, -One contains chosen items and -The other contains rejected items. Greedy algorithms make good local choices in the hope that They result in, -An optimal solution. -Feasible solutions.

CONTINUED… The greedy algorithm consists of four (4) function. A function that checks whether chosen set of items provide a solution. A function that checks the feasibility of a set. The selection function tells which of the items is the most promising. An objective function, which does not appear explicitly, gives the value of a solution.

OPTIMIZATION PROBLEMS An optimization problem: Given a problem instance, a set of constraints and an objective function . Find a feasible solution for the given instance for which the objective function has an optimal value. Either maximum or minimum depending on the problem being solved.A feasible solution that does this is called optimal solution .

Continued… Feasible : A feasible solution satisfies the problem’s constraints Constraints : The constraints specify the limitations on the required solutions.

GREEDY PROPERTY It consists of two property, 1. " greedy-choice property " ->It says that a globally optimal solution can be arrived at by making a locally optimal choice. 2. " optimal substructure " ->A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems. are two ingredients in the problem that lend to a greedy strategy.

Pseudo-code for Greedy Algorithm Algorithm Greedy (a,n) //a[1:n]contains the n inputs. { solution:=0;//initialize the solution. for i:=1 to n do { x:=Select(a); if Feasible( solution, x) then solution:=Union(solution,x); } return solution; }

CONTINUED… Select () selects an input from a[] and removes it. the selected input value is assigned to x. Feasible () is a boolean-valued function that determines whether x can be included into the solution vector(no constraints are violated). Union() combines x with the solution and updates the objective function.

GREEDY APPROACH Greedy Algorithm works by making the decision that seems most promising at any moment; it never reconsiders this decision, whatever situation may arise later. As an example consider the problem of " Making Change". Coins available are: 100 cents 25 cents 10 cents 5 cents 1 cent

CONTINUED… Problem: Make a change of a given amount using the smallest possible number of coins. Solution: The coin is selected using greedy criterion: at each stage increases the total amount of change constructed as much as possible. To assure feasibility i.e., the change given exactly equals the desired amount of the solution

Coin changing problem Algorithm: Make change for n units using the least possible number of coins. MAKE-CHANGE (n) C ← {100, 25, 10, 5, 1} // constant. S← {}; // set that will hold the solution set. Sum ← 0 sum of item in solution set WHILE sum not = n x = largest item in set C such that sum + x ≤ n IF no such item THEN RETURN "No Solution" S ← S {value of x} sum ← sum + x RETURN S

CONTAINER OVERLOADING The overall Time complexity of loading container is O ( n log n )

CONTINUED… Algorithm Container Loading(c,capacity,number of containers,x ) //greedy algorithm for container loading //set x[i]=1 iff container c[i],i>=1 is loaded. { //sort into increasing order of weight Sort(c,number of Containers); n:=number of Containers; //initialize x for i:=1 to n do x[i]:=0;

CONTINUED… //select containers in order of weight i :=1; While (i<=n&& c[i].weight<=capacity) { //enough capacity for container c[i].id X[c[i].id]:=1; Capacity-=c[i].weight;//remaining capacity i++; } }

COMPARISON WITH DP Greedy and Dynamic Programming are methods for solving optimization problems. Greedy algorithms are usually more efficient than DP solutions. However, often you need to use dynamic programming since the optimal solution cannot be guaranteed by a greedy algorithm. DP provides efficient solutions for some problems for which a brute force approach would be very slow

PROS AND CONS PROS: They are easier to implement, they require much less computing resources, they are much faster to execute. Greedy algorithms are used to solve optimization problems CONS: Their only disadvantage being that they not always reach the global optimum solution; on the other hand, even when the global optimum solution is not reached, most of the times the reached sub-optimal solution is a very good solution.

Greedymethod

Recommended

More Related Content

What's hot (20)

Similar to Greedymethod (20)

More from Meenakshi Devi (7)

Recently uploaded (20)

Greedymethod