Notes:
0) Making the locally optimum choice at each stage with the hope of finding the global optimum.
1) Greedy algorithms do not consistently find the globally optimal solution, because they usually do not operate exhaustively on all the data. e.g. graph coloring problem, NP-complete.
2) But it's useful because they are quick to think up and give good approximations to the optimum.
3) If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice. e.g. Kruskal and Prim for finding MST, optimum Huffman trees, Matroids theory.
4) They have 5 pillars:
♦ A candidate set, from which a solution is created
♦ A selection function, which chooses the best candidate to be added to the solution
♦ A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
♦ An objective function, which assigns a value to a solution, or a partial solution
♦ A solution function, which will indicate when we have discovered a complete solution
5) Basic Idea: "build large solutions up from smaller ones"
6) Keeps only the best solution, unlike other approaches!
7) Fast, Linear to quadratic, Little memory, Easy to code and debug, Run quickly, Defining a good Algorithm.
8) DON'T WORK FOR ALL PROBLEMS!!! (They usually aren't correct)
9) TWO basic problems:
1- How to Build? How does one create larger solutions from smaller ones?
THIS IS A FUNCTION OF THE PROBLEM.
2- Does it work?
DOESN'T ALWAYS WORK. (even if it works for sample input, random input and all the
cases...there's a case - at least one case where it won't work!)
10) Greedy algorithms can be proven by Reductio Argument.
11) Greedy doesn't work for Coin Change problems. THEY AREN'T GREEDY! (It just works one the U.S. coin system with coins 1, 5, 10, 25!)
12) Topological Sort can be solved with Greedy:
1- Create a DAG (Directed Acyclic Graph)
2- Find a node with in-degree of 0
(there's no topological sort for the DAG, if there isn't any node with in-degree of 0)
3- Place it on the end of ordering
4- Delete all of its out-arcs
5- Go to step 2
13) If a greedy solution exists, USE IT!
Sample Problems:
0) Making the locally optimum choice at each stage with the hope of finding the global optimum.
1) Greedy algorithms do not consistently find the globally optimal solution, because they usually do not operate exhaustively on all the data. e.g. graph coloring problem, NP-complete.
2) But it's useful because they are quick to think up and give good approximations to the optimum.
3) If a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice. e.g. Kruskal and Prim for finding MST, optimum Huffman trees, Matroids theory.
4) They have 5 pillars:
♦ A candidate set, from which a solution is created
♦ A selection function, which chooses the best candidate to be added to the solution
♦ A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
♦ An objective function, which assigns a value to a solution, or a partial solution
♦ A solution function, which will indicate when we have discovered a complete solution
5) Basic Idea: "build large solutions up from smaller ones"
6) Keeps only the best solution, unlike other approaches!
7) Fast, Linear to quadratic, Little memory, Easy to code and debug, Run quickly, Defining a good Algorithm.
8) DON'T WORK FOR ALL PROBLEMS!!! (They usually aren't correct)
9) TWO basic problems:
1- How to Build? How does one create larger solutions from smaller ones?
THIS IS A FUNCTION OF THE PROBLEM.
2- Does it work?
DOESN'T ALWAYS WORK. (even if it works for sample input, random input and all the
cases...there's a case - at least one case where it won't work!)
10) Greedy algorithms can be proven by Reductio Argument.
11) Greedy doesn't work for Coin Change problems. THEY AREN'T GREEDY! (It just works one the U.S. coin system with coins 1, 5, 10, 25!)
12) Topological Sort can be solved with Greedy:
1- Create a DAG (Directed Acyclic Graph)
2- Find a node with in-degree of 0
(there's no topological sort for the DAG, if there isn't any node with in-degree of 0)
3- Place it on the end of ordering
4- Delete all of its out-arcs
5- Go to step 2
13) If a greedy solution exists, USE IT!
Sample Problems:
No comments:
Post a Comment