代写代考 Algorithms & Data Structures (Winter 2022) Algorithm Paradigms

Algorithms & Data Structures (Winter 2022) Algorithm Paradigms – Complete Search

Announcements
Comp 251(c) 2022

Algorithmic Paradigms
• General approaches to the construction of correct and efficient solutions to problems.
• Such methods are of interest because:
• They provide templates suited to solving a broad range of diverse
• They can be translated into common control and data structures provided by most high-level languages.
• The temporal and spatial requirements of the algorithms can be precisely analyzed.
• Although more than one technique may be applicable to a specific problem, it is often the case that an algorithm constructed by one approach is clearly superior to equivalent solutions built using alternative techniques.

Algorithmic Paradigms
• Complete Search.
• Divide and Conquer.
• Dynamic Programming. • Greedy

Complete search
• Also know (related) as recursive backtracking or brute force. • Backtracking is a sort of refined brute force
• It is a method for solving a problem by searching (up to) the entire search space to obtain the required solution.
• The search space can be large but finite.
• Does not exist an algorithm that uses a method other than exhaustive search.
• Need for developing techniques of searching, with the hope of cutting down the search space to possibly a much smaller space. Backtracking can be
described as an organized exhaustive search which often avoids searching all possibilities.
Comp 251(c) 2022

Recursive Backtracking – example
• Problem: In chess (with a standard 8×8 board), it is possible to place eight queens on the board so that no queen can be taken by any other. Write a program that will determine all such possible arrangements.
Comp 251(c) 2022

Recursive Backtracking – example
• Solution 1:
• Use a solution vector where ai is true iff there is a queen on the ith
• There are 264 ≈ 1.84×1019 different true/false vectors for 8X8 board.
• Solution 2:
• Have the ith element of a solution vector explicitly list the square where
the ith queen resides. ai will be an integer from 1 to n2. • There are 648 ≈ 2.81×1014 vectors.
Comp 251(c) 2022

Recursive Backtracking – example
• Solution 3:
• Prune solution 2 by removing symmetries. Ensure that the queen in ai
sits on a higher number square that the queen in ai-1
• How many ways can you choose k things from a set of n items?
• In this case there are 64 squares and we want to choose 8 of them to put queens on.
• This change will reduce the search space to (648) = 4.426X109
• Includes lots of set ups with multiple queens in the same column.
Comp 251(c) 2022

Recursive Backtracking – example
• Solution 4:
• Note that there must be exactly one queen per column for a n-queens solution. Then you can limit the candidates of the ith queen to the eight squares on the ith column.
• There are 88 ≈ 1.67×107 vectors for 8X8 board.
• Solution 5:
• Since no two queens can share the row column, we know that the n
columns of a complete solution must form a permutation of n. • We reduce then our search space to just 8! = 40320 vectors.
Comp 251(c) 2022

Recursive Backtracking – example
• Solution 6:
• You can improve solution 5 by knowing that no two queens can share
any of the two diagonals.
• Solution 7:
• Identify the 12 unique (or fundamental) solutions. You can utilize this fact by only generating the 12 unique solutions and, if needed, generate the whole 92 by rotating and reflecting these 12 unique solutions
Comp 251(c) 2022

Recursive Backtracking – Solution 4
• Solution 4:
• There are 88 ≈ 1.67×107 vectors for 8X8 board.
• If number of queens is fixed and I realize there can’t be more than one queen per column I can iterate through the rows for each column.
Comp 251(c) 2022

Recursive Backtracking – Solution 4
• What about if you do not have 8, but N queens: • You do not know how many for loops to write.
• Do the problem recursively – backtracking.
• Recursive because later versions of the problem are just slightly simpler versions of the original.
• Youhaven–iqueenstoadd.
• Backtracking because we may have to try different alternatives.
• Problemspaceconsistsofstates(nodes)[chessboard]andactions(pathsthatleadto new states) [placing a queen].
• Ifanodeonlyleadstofailuregobacktoits”parent”node.Tryotheralternatives
Comp 251(c) 2022

Recursive Backtracking
• Escaping a Maze. • A view form above.
• Exit out there, some where to the south!
Comp 251(c) 2022

Recursive Backtracking
• Exit out there, some where to the south!
Comp 251(c) 2022

Recursive Backtracking – N Queen
• WerepresentthepositionsofthequeensusinganarrayQ[1..n],whereQ[i] indicates which square in row i contains a queen.
• Theindexristheindexofthefirstemptyrow.
• The prefix Q[1 ..r-1] contains the positions of the first r -1 queens.
All possible placements of a queen on row r
Checks whether a placement is consistent with the queens already on the first r-1 rows
Comp 251(c) 2022

N Queens – recursion tree
Recursion calls
be further extended
Solutions that can not
Comp 251(c) 2022

N Queens – recursion tree
Comp 251(c) 2022

Recursive Backtracking
Image Credit: [wikipedia]
• You must practice!!!
• Learn to recognize problems that
fit the pattern
• Clearly define your search space.
Correctness
Efficiency
aware of your resources.
solutions or a solution?
Find a path to success
Find all paths to success Find the best path to success
Comp 251(c) 2022

Recursive Backtracking – template
If at a solution, report success
for (every possible choice from current state / node) • Make that choice and take one step along path
• Use recursion to try to solve the problem for the new node / state
• If the recursive call succeeds, report the success to the previous level • Back out of the current choice to restore the state at the beginning of
the loop. Report failure
Comp 251(c) 2022

Recursive Backtracking – Sudoku
• 9 by 9 matrix with some
numbers filled in
• all numbers must be between 1 and 9
• Goal: Each row, each column, and each mini matrix must contain the numbers between 1 and 9 once each
• no duplicates in rows, columns, or mini matrices
Comp 251(c) 2022

Recursive Backtracking – Sudoku
• Brute force Sudoku
• if not open cells, solved
• scan cells from left to right, top to bottom for first open cell
• When an open cell is found start cycling through digits 1 to 9.
• When a digit is placed check that the set up is legal
• now solve the board
Comp 251(c) 2022

Recursive Backtracking – Sudoku
Comp 251(c) 2022

Recursive Backtracking – Sudoku
• When the search reaches a dead end it backs up to the previous cell it was trying to fill and goes onto to the next digit.
• Wewouldbackuptothecellwitha9 and that turns out to be a dead end as well so we back up again
• so the algorithm needs to remember what digit to try next
• Nowinthecellwiththe8.Wetryand9 and move forward again.
Comp 251(c) 2022

Recursive Backtracing – Conclusions
• Generating versus Filtering:
• Programs that generate lots of candidate solutions and then choose the ones that are correct are called ‘filters’ – recall the naive 8-queens solvers.
• Those that hone in exactly to the correct answer without any false starts are called ‘generators’ – recall the improved 8-queens solver with 12 solutions.
• Generally, filters are easier to code but run slower. Do the math to see if a filter is good enough
• Prune Infeasible Search Space Early: • Utilize Symmetries.
• In the 8-queens problem, there are 92 solutions but there are only 12 unique (or fundamental) solutions as there are rotations and reflections symmetries in this problem. You can utilize this fact by only generating
the 12 unique solutions and, if needed, generate the whole 92 by rotating
and reflecting these 12 unique solutions.
Comp 251(c) 2022

Recursive Backtracing – Conclusions
• Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints.
• In the n-queens problem, the goal is a sequence of queen positions, one in each row, such that no two queens attack each other. For each row, the algorithm decides where to place the queen.
• In each recursive call to the backtracking algorithm, we need to make exactly one decision, and our choice must be consistent with all previous decisions.
• For the n-queens problem, we must pass in not only the number of empty rows, but the positions of all previously placed queens.
• Finally, once we’ve figured out what recursive problem we really need to solve, we solve that problem by recursive brute force:
• Try all possibilities for the next decision that are consistent with past
decisions, and let the recursion worry about the rest.
Comp 251(c) 2022

Recursive Backtracing – Conclusions
• Useful to solve decision, optimization and enumeration problems.
• A lot of applications. • Puzzles
• Combinatorial optimization
• Logic programming
• Constraint satisfaction problems
• Huge in artificial intelligence.
• Smart agent searching an O(264) space VS naïve agent searching an O(12)
• Machine learning (deep learning, reinforce learning)
Comp 251(c) 2022

Recursive Backtracing – Conclusions
• Problems that are solved by backtracking can usually use the same recursive strategy to solve many different variants of the same problem.
Brute-Force is slow.
• Prune your search space.
• Is it the only way to solve it?
• What type of solutions do I need (all, any, the optimal?)
Taken from https://www.explainxkcd.com
Comp 251(c) 2022

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees. • Recall that:
• The running time for a successful search in a binary search tree is proportional to the depth of the tree (i.e., the number of ancestors of the target node).
• To minimize the worst-case search time, the height of the tree should be as small as possible.
• The ideal tree is perfectly balanced (remember AVL and red-black trees).
Comp 251(c) 2022

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees. • However:
• In many BST applications, it is more important to minimize the total cost
of several searches rather than the worst-case cost of a single search.
• If x is a more frequent search target than y, we can save time by building a tree where the depth of x is smaller than the depth of y, even if that means increasing the overall depth of the tree.
Comp 251(c) 2022

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees.
• Given an array of sorted keys A[1 .. n] and an array of corresponding access frequencies f[1 .. n]. Our task is to ‘build’ the binary search tree that minimizes the total search time, assuming that there will be exactly f[i] searches for each key A[i].
• Let T be a BST. Let v1,v2,…,vn be the nodes of T such that each node vi stores the corresponding key A[i].
• The total cost (ignoring constant factors) of performing all the searches is
v1 v3 v5 v7
18 28 190 213
A = [18,26,28,56,190,200,213]
Comp 251(c) 2022

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees.
• Now suppose vr is the root of T.
• vr is an ancestor of every node in T.
• If i < r, then all ancestors of vi (except the root) are in the left subtree of T. • If i > r, then all ancestors of vi (except the root) are in the right subtree of T. • Then, we can partition the cost function into three parts:
Comp 251(c) 2022

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees.
• So far, we have two ways to express the cost.
• Note that the second and third summations of the second equation look exactly like our first equation.
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees.
• Simple substitution give us a recurrence for the cost.
• The task now is to compute the tree Topt that minimize this cost function.
• Once we choose the correct key to store at the root, the recursion (i.e., recursive backtracking) will construct the rest of the optimal tree.
• The left subtree left(Topt) must be the optimal BST for the keys A[1..r-1] and access frequencies f[1..r-1].
• The right subtree right(Topt) must be the optimal BST for the keys A[r+1..n] and access frequencies f[r+1..n].
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• Optimal Binary Search Trees.
• More generally, let OptCost(i,k) denote the total cost of the optimal
search tree for the interval of frequencies f[i..k].
• This recursive definition can be translated into a recursive backtracking algorithm to compute OptCost(1,n).
• We one by one try all nodes as root (r varies from i to k in second term)
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
Picture from https://www.geeksforgeeks.org/ • The running time satisfies the recurrence:
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• The running time satisfies the recurrence:
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• The running time satisfies the recurrence (supplemental):
1 2 3 4 5 6 7 8
T(0) T(1) T(2) T(3) T(4) T(5) T(6) T(7)
k left right
T(7) T(6) T(5) T(4) T(3) T(2) T(1) T(0)
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• The running time satisfies the recurrence:
• By solving the recurrence (supplemental material). Replacing O() with a constant
Recurrence for T(n-1)
Substracting the recurrences Simplifying the recurrence
Recursion tree method (topic of next class)
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• The running time satisfies the recurrence:
• The number of binary search trees with n vertices satisfies the recurrence:
Note: No obvious: https://math.stackexchange.com/questions/1986247/asymptotic-approximation-of-catalan-numbers
Comp 251(c) 2021

Recursive Backtracking + Divide and Conquer
• The running time satisfies the recurrence:
• The number of binary search trees with n vertices satisfies the
recurrence:
• The analysis implies:
• Our recursive algorithm does not examine all possible BST.
• Our algorithm saves considerable time by searching independently for the optimal left and right subtrees for each root.
• A full enumeration of binary search trees would consider all possible pairs of left and right subtrees (hence the product in the recurrence for N(n))
Comp 251(c) 2021

Algorithmic Paradigms
• Complete Search.
• Divide and Conquer.
• Dynamic Programming. • Greedy

Divide and Conquer
• Recursive in structure
• Divide the problem into sub-problems that are similar to the original but
smaller in size
• Conquer the sub-problems by solving them recursively. If they are small enough, just solve them in a straightforward manner.
• Combine the solutions to create a solution to the original problem
Comp 251(c) 2022

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts