Algorithm StrategiesGeneral ConceptsSome Algorithm StrategiesRecursive AlgorithmRecursive Algorithm – ExamplesBacktracking AlgorithmBacktracking Algorithm – ExampleSlide 8Divide and ConquerDivide and Conquer – ExamplesDynamic Programming AlgorithmFibonacci AlgorithmDynamic Programming – ExampleSlide 14Greedy AlgorithmGreedy Algorithm – ExampleBrute Force AlgorithmBrute Force Algorithm – ExampleBranch and Bound AlgorithmBranch and Bound – ExampleHeuristic AlgorithmHeuristic Algorithm – ExampleSummaryAlgorithm StrategiesFawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkGeneral ConceptsAlgorithm strategyApproach to solving a problemMay combine several approachesAlgorithm structureIterative execute action in loopRecursive reapply action to subproblem(s)Problem typeSatisfying find any satisfactory solutionOptimization find best solutions (vs. cost metric)Some Algorithm StrategiesRecursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithms Brute force algorithmsBranch and bound algorithmsHeuristic algorithmsRecursive AlgorithmBased on reapplying algorithm to subproblemApproach1. Solves base case(s) directly2. Recurs with a simpler subproblem3. May need to convert solution(s) to subproblemsRecursive Algorithm – Examples To count elements in listIf list is empty, return 0Else skip 1st element and recur on remainder of listAdd 1 to resultTo find element in listIf list is empty, return falseElse if first element in list is given value, return trueElse skip 1st element and recur on remainder of listBacktracking AlgorithmBased on depth-first recursive searchApproach1. Tests whether solution has been found2. If found solution, return it3. Else for each choice that can be madea) Make that choiceb) Recurc) If recursion returns a solution, return it4. If no choices remain, return failureSome times called “search tree”Backtracking Algorithm – ExampleFind path through mazeStart at beginning of mazeIf at exit, return trueElse for each step from current locationRecursively find pathReturn with first successful stepReturn false if all steps failBacktracking Algorithm – ExampleColor a map with no more than four colorsIf all countries have been colored return successElse for each color c of four colors and country nIf country n is not adjacent to a country that has been colored cColor country n with color cRecursively color country n+1If successful, return successReturn failureDivide and ConquerBased on dividing problem into subproblemsApproach1. Divide problem into smaller subproblems Subproblems must be of same typeSubproblems do not need to overlap2. Solve each subproblem recursively3. Combine solutions to solve original problemUsually contains two or more recursive callsDivide and Conquer – ExamplesQuicksortPartition array into two parts around pivotRecursively quicksort each part of arrayConcatenate solutionsMergesortPartition array into two partsRecursively mergesort each halfMerge two sorted arrays into single sorted arrayDynamic Programming AlgorithmBased on remembering past resultsApproach1. Divide problem into smaller subproblems Subproblems must be of same typeSubproblems must overlap2. Solve each subproblem recursivelyMay simply look up solution3. Combine solutions into to solve original problem4. Store solution to problemGenerally applied to optimization problemsFibonacci AlgorithmFibonacci numbersfibonacci(0) = 1 fibonacci(1) = 1 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) Recursive algorithm to calculate fibonacci(n)If n is 0 or 1, return 1Else compute fibonacci(n-1) and fibonacci(n-2)Return their sumSimple algorithm exponential time O(2n)Dynamic Programming – ExampleDynamic programming version of fibonacci(n)If n is 0 or 1, return 1Else solve fibonacci(n-1) and fibonacci(n-2)Look up value if previously computedElse recursively compute Find their sum and storeReturn resultDynamic programming algorithm O(n) timeSince solving fibonacci(n-2) is just looking up valueDynamic Programming – ExampleDjikstra’s Shortest Path Algorithm{ S } = C[X] = 0C[Y] = for all other nodeswhile ( not all nodes in { S } )find node K not in { S } with smallest C[K]add K to { S }for each node M not in { S } adjacent to K C[M] = min ( C[M] , C[K] + cost of (K,M) )Stores results of smaller subproblemsGreedy AlgorithmBased on trying best current (local) choiceApproach At each step of algorithmChoose best local solutionAvoid backtracking, exponential time O(2n)Hope local optimum lead to global optimumGreedy Algorithm – ExampleKruskal’s Minimal Spanning Tree Algorithmsort edges by weight (from least to most)tree = for each edge (X,Y) in orderif it does not create a cycleadd (X,Y) to treestop when tree has N–1 edgesPicks best local solution at each stepBrute Force AlgorithmBased on trying all possible solutionsApproachGenerate and evaluate possible solutions untilSatisfactory solution is foundBest solution is found (if can be determined)All possible solutions foundReturn best solutionReturn failure if no satisfactory solutionGenerally most expensive approachBrute Force Algorithm – ExampleTraveling Salesman Problem (TSP)Given weighted undirected graph (map of cities)Find lowest cost path visiting all nodes (cities) onceNo known polynomial-time general solutionBrute force approachFind all possible paths using recursive backtrackingCalculate cost of each pathReturn lowest cost path Requires exponential time O(2n)Branch and Bound AlgorithmBased on limiting search using current solutionApproach Track best current solution found Eliminate partial solutions that can not improve upon best current solutionReduces amount of backtrackingNot guaranteed to avoid exponential time O(2n)Branch and Bound – ExampleBranch and bound algorithm for TSPFind possible paths using recursive backtrackingTrack cost of best current solution foundStop searching path if cost > best current solutionReturn lowest cost path If good solution found early, can reduce searchMay still require exponential time O(2n)Heuristic AlgorithmBased on trying to guide search for solutionHeuristic “rule of thumb”ApproachGenerate and evaluate possible solutionsUsing “rule of thumb”Stop if satisfactory solution is foundCan reduce complexityNot guaranteed to yield best solutionHeuristic Algorithm – ExampleHeuristic algorithm for TSPFind possible paths using recursive
View Full Document
Unlocking...