First-Cut Techniques The Greedy Approach Graph Traversal A common characteristic of both greedy algorithms and graph traversal is that they are fast,as they involve making local decisions
First-Cut Techniques ◼ The Greedy Approach ◼ Graph Traversal ⚫ A common characteristic of both greedy algorithms and graph traversal is that they are fast, as they involve making local decisions
The Greedy Approach As in the case of dynamic programming algorithms, greedy algorithms are usually designed to solve optimization problems in which a quantity is to be minimized or maximized. Unlike dynamic programming algorithms,greedy algorithms typically consist of a n iterative procedure that tries to find a local optimal solution. In some instances,these local optimal solutions translate to global optimal solutions.In others,they fail to give optimal solutions
The Greedy Approach ◼ As in the case of dynamic programming algorithms, greedy algorithms are usually designed to solve optimization problems in which a quantity is to be minimized or maximized. ◼ Unlike dynamic programming algorithms, greedy algorithms typically consist of a n iterative procedure that tries to find a local optimal solution. ◼ In some instances, these local optimal solutions translate to global optimal solutions. In others, they fail to give optimal solutions
The Greedy Approach A greedy algorithm makes a correct guess on the basis of little calculation without worrying about the future.Thus,it builds a solution step by step.Each step increases the size of the partial solution and is based on local optimization. The choice make is that which produces the /argest immediate gain while maintaining feasibility. ■ Since each step consists of little work based on a small amount of information,the resulting algorithms are typically efficient
The Greedy Approach ◼ A greedy algorithm makes a correct guess on the basis of little calculation without worrying about the future. Thus, it builds a solution step by step. Each step increases the size of the partial solution and is based on local optimization. ◼ The choice make is that which produces the largest immediate gain while maintaining feasibility. ◼ Since each step consists of little work based on a small amount of information, the resulting algorithms are typically efficient
The Fractional Knapsack Problem Given n items of sizes s,s,...,s and values v, v,...,and size C the knapsack capacity,the objective is to find nonnegative real numbers, X2,...,that maximize the sum i=1 subject to the constraint ∑xs,≤C i=1
The Fractional Knapsack Problem ◼ Given n items of sizes s1 , s2 , …, sn , and values v1 , v2 , …, vn and size C, the knapsack capacity, the objective is to find nonnegative real numbers x1 , x2 , …, xn that maximize the sum = n i i i x v 1 = n i xi si C 1 subject to the constraint
The Fractional Knapsack Problem This problem can easily be solved using the following greedy strategy: For each item computey=/s the ratio of its value to its size. Sort the items by decreasing ratio,and fill the knapsack with as much as possible from the first item,then the second,and so forth. This problem reveals many of the characteristics of a greedy algorithm discussed above:7he algorithm consists of a simple iterative procedure that selects that item which produces that largest immediate gain while maintaining feasibility
The Fractional Knapsack Problem ◼ This problem can easily be solved using the following greedy strategy: ➢ For each item compute yi=vi /si , the ratio of its value to its size. ➢ Sort the items by decreasing ratio, and fill the knapsack with as much as possible from the first item, then the second, and so forth. ◼ This problem reveals many of the characteristics of a greedy algorithm discussed above: The algorithm consists of a simple iterative procedure that selects that item which produces that largest immediate gain while maintaining feasibility