backtracking

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

By: rimmy.cool (36 month(s) ago)

good job

By: rimmy.cool (36 month(s) ago)

good job

By: fudu (41 month(s) ago)

plz allow me to download it

By: fudu (41 month(s) ago)

if u got this ppt plz send it to me on my id mandeepdiat7@gmail.com

By: amit0633 (41 month(s) ago)

very good ppt...pls send the link to download this...m in need pls sir....

By: fudu (41 month(s) ago)

if u got this ppt plz send it to me on my id mandeepdiat7@gmail.com

 
See all

Presentation Transcript

BackTracking : 

BackTracking CS255

N-Queens : 

N-Queens The object is to place queens on a chess board in such as way as no queen can capture another one in a single move Recall that a queen can move horz, vert, or diagonally an infinite distance This implies that no two queens can be on the same row, col, or diagonal We usually want to know how many different placements there are

4-Queens : 

4-Queens Lets take a look at the simple problem of placing queens 4 queens on a 4x4 board The brute-force solution is to place the first queen, then the second, third, and forth After all are placed we determine if they are placed legally There are 16 spots for the first queen, 15 for the second, etc. Leading to 16*15*14*13 = 43,680 different combinations Obviously this isn’t a good way to solve the problem

4-Queens : 

4-Queens First lets use the fact that no two queens can be in the same col to help us That means we get to place a queen in each col So we can place the first queen into the first col, the second into the second, etc. This cuts down on the amount of work Now there are 4 spots for the first queen, 4 spots for the second, etc. 4*4*4*4 = 256 different combinations

4-Queens : 

4-Queens However, we can still do better because as we place each queen we can look at the previous queens we have placed to make sure our new queen is not in the same row or diagonal as a previously place queen Then we could use a Greedy-like strategy to select the next valid position for each col

4-Queens : 

4-Queens

4-Queens : 

4-Queens We are stuck!

4-Queens : 

4-Queens So now what do we do? Well, this is very much like solving a maze As you walk though the maze you have to make a series of choices If one of your choices leads to a dead end, you need to back up to the last choice you made and take a different route That is, you need to change one of your earlier selections Eventually you will find your way out of the maze

4-Queens : 

4-Queens

4-Queens : 

4-Queens

4-Queens : 

4-Queens

4-Queens : 

4-Queens

4-Queens : 

4-Queens This type of problem is often viewed as a state-space tree A tree of all the states that the problem can be in We start with an empty board state at the root and try to work our way down to a leaf node Leaf nodes are completed boards

4-Queens : 

4-Queens 1 1 2 3 4 2 X X 1 2 3 4 X X X X 1 2 4 3 X X 1 2 4 3 X X X X X 1 2 3 4 X X X 1 1 2 3 X X

Graph Coloring : 

Graph Coloring Graph coloring is the problem of coloring each vertex in a graph such that no two adjacent vertices are the same color Some direct examples: Map coloring Register assignment

Graph Coloring : 

Graph Coloring The same issues apply as in N-Queens We don’t want to simply pick all subsets Way too many We want to prune the state-space tree as soon as we find something that won’t work This implies that we need a sequence of vertices to color As we color the next vertex we need to make sure it doesn’t conflict with any of its previously colored neighbors We may need to backtrack

Graph Coloring : 

Graph Coloring C A F B E D As an example: The vertices are enumerated in order A-F The colors are given in order: R, G, B

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D Stuck!

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring C A F B E D

Graph Coloring : 

Graph Coloring X X A B C D E F X X X X X X X X C A F B E D

Depth-First Search : 

Depth-First Search One can view backtracking as a Depth-First Search through the State-Space We start our search at the root We end our search when we find a valid leaf node A Depth-First Search expands the deepest node next A child children will be expanded before the child’s siblings are expanded This type of search get you to the leaf nodes as fast as you can How do you implement a Depth-First Search?

Backtracking Framework : 

Backtracking Framework We will try and build a generic backtracking framework that works with problems States All it should need to work with is States State should be generic and not married to any specific problem States should be able to: Tell us if it has more children Produce the next child Tell us if it is solved Tell us if it is feasible (In class design of the State, NQueens problem specific, and Backtracking framework classes)

Depth vs. Breadth First Search : 

Depth vs. Breadth First Search A Breadth first search expands all the children at a particular level before advancing to the next level How can a breadth first search be implemented? Which is better: a depth or breadth first search? Worst case Big-O?

Optimization Problems : 

Optimization Problems The previous examples simply found all the solutions (Nqueens) or any single solution (Graph Coloring) What if we have a cost associated with each solution and we want to find the optimal solution As an example take Weighed Graph Coloring R ? $2, G ? $3, B ? $5, Y ? $2 A fully connected graph of 3 vertices Note that some of the connections on the next slide are missing to keep the picture fairly clean

Weighted Graph Coloring : 

Weighted Graph Coloring X X X X X X X X X X

Weighted Graph Coloring : 

Weighted Graph Coloring Obviously this approach will take a long time since we need to look at every possible combination Is there any way we can prune even more nodes from the tree? Besides the non-feasible ones that we already prune What about a upper or lower bound on a node? An estimate of the potential cost of expanding the node

Bounding : 

Bounding A bound on a node is a guarantee that any solution obtained from expanding the node will be: Greater than some number (lower bound) Or less than some number (upper bound) If we are looking for a minimal optimal, as we are in weighted graph coloring, then we need a lower bound For example, if the best solution we have found so far has a cost of 12 and the lower bound on a node is 15 then there is no point in expanding the node The node cannot lead to anything better than a 15

Bounding : 

Bounding We can compute a lower bound for weighted graph color in the following way: The actual cost of getting to the node Plus a bound on the future cost Min weight color * number of nodes still to color That is, the future cost cannot be any better than this (Interactively draw state space graph on board complete with bounds as given above)

Bounding : 

Bounding Recall that we could either perform a depth-first or a breadth-first search Without bounding, it didn’t matter which one we used because we had to expand the entire tree to find the optimal solution Does it matter with bounding? Hint: think about when you can prune via bounding (Interactively draw the breadth-first bounding case on the board and compare it with depth-first)

Bounding : 

Bounding We prune (via bounding) when: (currentBestSolutionCost <= nodeBound) This tells us that we get more pruning if: The currentBestSolution is low And the nodeBound is high So we want to find a low solution quickly and we want the highest possible lower bound One has to factor in the extra computation cost of computing higher lower bounds vs. the expected pruning savings

Best-first Search : 

Best-first Search Depth-first search found a solution quickly Breadth-first search found all solutions at about the same time (but slowly) Best-first search finds a good solution fairly quickly Not as quickly as depth-first But the solution is often better which will increase the pruning via bounding

Best-first Search : 

Best-first Search Best-first search expands the node with the best bounds next (Interactively show a best-first state-space tree on weighted graph coloring) How would you implement a best-first search? Depth-first is a stack Breadth-first is a queue Best-first is a ???

Traveling Salesperson Problem : 

Traveling Salesperson Problem This is a classic CS problem Given a graph (cities), and weights on the edges (distances) find a minimum weight tour of the cities Start in a particular city Visit all other cities (exactly once each) Return to the starting city Cannot be done by brute-force as this is worst-case exponential or worse running time So we will look to backtracking with pruning to make it run in a reasonable amount of time in most cases

Traveling Salesperson Problem : 

Traveling Salesperson Problem We will build our state space by: Having our children be all the potential cities we can go to next Having the depth of the tree be equal to the number of cities in the graph we need to visit each city exactly once So given a fully connected set of 5 nodes we have the following state space only partially completed

Traveling Salesperson Problem : 

Traveling Salesperson Problem A B C D E A B C D E X A B C D E X X

Traveling Salesperson Problem : 

Traveling Salesperson Problem Now we need to add bounding to this problem It is a minimization problem so we need to find a lower bound We can use: The current cost of getting to the node plus An underestimate of the future cost of going through the rest of the cities The obvious choice is to find the minimum weight edge in the graph and multiply that edge weight by the number of remaining nodes to travel through

Traveling Salesperson Problem : 

Traveling Salesperson Problem As an example assume we have the given adjacency matrix If we started at node A and have just traveled to node B then we need to compute the bound for node B Cost 14 to get from A to B Minimum weight in matrix is 2 times 4 more legs to go to get back to node A = 8 For a grand total of 14 + 8 = 22

Traveling Salesperson Problem : 

Traveling Salesperson Problem Recall that if we can make the lower bound higher then we will get more pruning Note that in order to complete the tour we need to leave node B, C, D, and E The min edge we can take leaving B is min(14, 7, 8, 7) = 7 Similarly, C=4, D=2, E=4 This implies that at best the future underestimate can be 7+4+2+4=17 17 + current cost of 14 = 31 This is much higher than 8 + 14 = 22