1Algorithm 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)2Some Algorithm StrategiesRecursive algorithmsBacktracking algorithmsDivide and conquer algorithmsDynamic programming algorithmsGreedy algorithms Brute force algorithmsBranch and bound algorithmsHeuristic algorithms Recursive AlgorithmBased on reapplying algorithm to subproblemApproach1. Solves base case(s) directly2. Recurs with a simpler subproblem3. May need to convert solution(s) to subproblems3Recursive Algorithm – Examples To count elements in listIf list is empty, return 0Else skip 1stelement 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 1stelement 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”4Backtracking 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 failure5Divide 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 array6Dynamic 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) = 1fibonacci(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)7Dynamic 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 subproblems8Greedy 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 step9Brute 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)10Branch 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)11Heuristic 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 solution Heuristic Algorithm – ExampleHeuristic algorithm for TSPFind possible paths using recursive backtrackingSearch 2 lowest cost edges at each node firstCalculate cost of each pathReturn lowest cost path from first 100 solutionsNot guaranteed to find best solutionHeuristics used frequently in real applications12SummaryWide range of strategiesChoice depends onProperties of problemExpected problem sizeAvailable
View Full Document
Unlocking...