Dynamic Programming American University in Cairo开罗的美国大学.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Prof. Amr Goneid, AUC * (d) Complexity Analysis Skeletal Algorithm: for j = 1 to n-1 do { // sub-tree has j+1 nodes for i = 1 to n-j do { // for each of the n-j sub-tree combinations for k = i to i+j do { find cost of each of the j+1 configurations and determine minimum cost } } } T(n) = ?1? j ? n-1 ( j + 1) (n – j) = O(n3) , S(n) = O(n2) Prof. Amr Goneid, AUC * Exercise Find the optimal binary search tree for the following words with the associated frequencies: a (18) , and (22) , I (19) , it (20) , or (21) Answer: Min cost = 20 + 2*43 + 3*37 = 217 it or and I a 20 22 21 18 19 Prof. Amr Goneid, AUC * 9. Dynamic Programming Algorithms for Graph Problems Various optimization graph problems have been solved using Dynamic Programming algorithms. Examples are: Dijkstras algorithm solves the single-source shortest path problem for a graph with nonnegative edge path costs Floyd–Warshall algorithm for finding all pairs shortest paths in a weighted graph (with positive or negative edge weights) and also for finding transitive closure The Bellman–Ford algorithm computes single-source shortest paths in a weighted digraph for graphs with negative edge weights. These will be discussed later under “Graph Algorithms”. Prof. Amr Goneid, AUC * 10. Comparison with Greedy and Divide Conquer Methods Greedy vs. DP : Both are optimization techniques, building solutions from a collection of choices of individual elements. The greedy method computes its solution by making its choices in a serial forward fashion, never looking back or revising previous choices. DP computes its solution bottom up by synthesizing them from smaller subsolutions, and by trying many possibilities and choices before it arrives at the optimal set of choices. There is no a priori test by which one can tell if the Greedy method will lead to an optimal solution. By contrast, ther