Coping with the Limitations of Algorithm Power:Exact Solution Strategies.
Coping with the Limitations of Algorithm Power
Tackling Difficult Combinatorial Problems
• There are two principal approaches to tackling difficult combinatorial problems (NP-hard problems):
• Use a strategy that guarantees solving the problem exactly but doesn’t guarantee to find a solution in polynomial time
• Use an approximation algorithm that can find an approximate (sub-optimal) solution in polynomial time
Exact Solution Strategies
• exhaustive search (brute force)
– useful only for small instances
• dynamic programming
– applicable to some problems (e.g., the knapsack problem)
• backtracking
– eliminates some unnecessary cases from consideration
– yields solutions in reasonable time for many instances but worst case is still exponential
• branch-and-bound
– further refines the backtracking idea for optimization problems
Backtracking
• Suppose you have to make a series of decisions, among various choices, where
– You don’t have enough information to know what to choose
– Each decision leads to a new set of choices
– Some sequence of choices (possibly more than one) may be a solution to your problem
• Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”
Backtracking : A Scenario
A tree is composed of nodes
Backtracking can be thought of as searching a tree for a particular “goal” leaf node
• Each non-leaf node in a tree is a parent of one or more other nodes (its children)
• Each node in the tree, other than the root, has exactly one parent
The backtracking algorithm
• Backtracking is really quite simple--we “explore” each node, as follows:
• To “explore” node N:
1. If N is a goal node, return “success”
2. If N is a leaf node, return “failure”
3. For each child C of N,
3.1. Explore C
3.1.1. If C was successful, return “success”
4. Return “failure”
• Construct the state-space tree
– nodes: partial solutions
– edges: choices in extending partial solutions
• Explore the state space tree using depth-first search
• “Prune” nonpromising nodes
– dfs stops exploring subtrees rooted at nodes that cannot lead to a solution and backtracks to such a node’s parent to continue the search
Example: n-Queens Problem
Place n queens on an n-by-n chess board so that no two of them are in the same row, column, or diagonal
State-Space Tree of the 4-Queens Problem
N-Q ueens Problem:
• 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
• 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
• 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
• 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
• 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
• 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
Eight Queen Problem
• The solution is a vector of length 8 (a(1), a(2), a(3), ...., a(8)).
a(i) corresponds to the column where we should place the i-th queen.
• The solution is to build a partial solution element by element until it is complete.
• We should backtrack in case we reach to a partial solution of length k, that we couldn't expand any more.
Eight Queen Problem: Implementation
• Define an 8 by 8 array of 1s and 0s to represent the chessboard
• The array is initialized to 1s, and when a queen is put in a position (c,r), board[r][c] is set to zero
• Note that the search space is very huge: 16,772, 216 possibilities.
• Is there a way to reduce search space? Yes Search Pruning.
• We know that for queens:
each row will have exactly one queen each column will have exactly one queen
each diagonal will have at most one queen
• This will help us to model the chessboard not as a 2-D array, but as a set of rows, columns and diagonals.
Hamiltonian Cycle
• Hamiltonian Cycle:
– a cycle that contains every node exactly once
• Problem:
– Given a graph, does it have a Hamiltonian cycle?
Background
• NP-complete problem:
– Most difficult problems in NP (non- deterministic polynomial time)
• A decision problem D is NP-complete if it is complete for NP, meaning that:
– it is in NP
– it is NP-hard (every other problem in NP is reducible to it.)
• As they grow large, we are not able to solve them in a reasonable time (polynomial time)
Alternative Definition
• . NP Problem such as Hamiltonian Cycle :
– Cannot be solved in Poly-time
– Given a solution, easy to verify in poly-time
Sum of subsets
• Problem: Given n positive integers w1, ... wn and a positive integer S. Find all subsets of w1, ... wn that sum to S.
• Example:
n=3, S=6, and w1=2, w2=4, w3=6
• Solutions:
{2,4} and {6}
• We will assume a binary state space tree.
• The nodes at depth 1 are for including (yes, no) item 1, the nodes at depth 2 are for item 2, etc.
• The left branch includes wi, and the right branch excludes wi.
• The nodes contain the sum of the weights included so far
Sum of subset Problem: State SpaceTree for 3 items
A Depth First Search solution
• Problems can be solved using depth first search of the (implicit) state space tree.
• Each node will save its depth and its (possibly partial) current solution
• DFS can check whether node v is a leaf.
– If it is a leaf then check if the current solution satisfies the constraints
– Code can be added to find the optimal solution
A DFS solution
• Such a DFS algorithm will be very slow.
• It does not check for every solution state (node) whether a solution has been reached, or whether a partial solution can lead to a feasible solution
• Is there a more efficient solution?
Backtracking solution to Sum of Subsets
• Definition: We call a node nonpromising if it cannot lead to a feasible (or optimal) solution, otherwise it is promising
• Main idea: Backtracking consists of doing a DFS of the state space tree, checking whether each node is promising and if the node is nonpromising backtracking to the node’s parent
• The state space tree consisting of expanded nodes only is called the pruned state space tree
• The following slide shows the pruned state space tree for the sum of subsets example
• There are only 15 nodes in the pruned state space tree
• The full state space tree has 31 nodes
Checknode
• Checknode uses the functions:
– promising(v) which checks that the partial solution represented by v can lead to the required solution
– aSolutionAt(v) which checks whether the partial solution represented by node v solves the problem.
Sum of subsets – when is a node “promising”?
• Consider a node at depth i
• weightSoFar = weight of node, i.e., sum of numbers included in partial solution node represents
• totalPossibleLeft = weight of the remaining items i+1 to n (for a node at depth i)
• A node at depth i is non-promising
if (weightSoFar + totalPossibleLeft < S )
or (weightSoFar + w[i+1] > S )
• To be able to use this “promising function” the wi must be sorted in non-decreasing order
Comments
Post a Comment