30-06-2012, 01:14 PM
Backtracking
Backtracking.ppt (Size: 441.5 KB / Downloads: 370)
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 Algorithm
Based on depth-first recursive search
Approach
Tests whether solution has been found
If found solution, return it
Else for each choice that can be made
Make that choice
Recur
If recursion returns a solution, return it
If no choices remain, return failure
Some times called “search tree”
Backtracking Algorithm – Example
Color a map with no more than four colors
If all countries have been colored return success
Else for each color c of four colors and country n
If country n is not adjacent to a country that has been colored c
Color country n with color c
Recursively color country n+1
If successful, return success
Return failure
Recursive Backtracking
Pseudo code for recursive backtracking algorithms
If at a solution, return success
for( every possible choice from current state / node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next high level
Back out of the current choice to restore the state at the beginning of the loop.
Report failure
Backtracking
Backtracking.ppt (Size: 441.5 KB / Downloads: 370)
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 Algorithm
Based on depth-first recursive search
Approach
Tests whether solution has been found
If found solution, return it
Else for each choice that can be made
Make that choice
Recur
If recursion returns a solution, return it
If no choices remain, return failure
Some times called “search tree”
Backtracking Algorithm – Example
Color a map with no more than four colors
If all countries have been colored return success
Else for each color c of four colors and country n
If country n is not adjacent to a country that has been colored c
Color country n with color c
Recursively color country n+1
If successful, return success
Return failure
Recursive Backtracking
Pseudo code for recursive backtracking algorithms
If at a solution, return success
for( every possible choice from current state / node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next high level
Back out of the current choice to restore the state at the beginning of the loop.
Report failure
Backtracking.ppt (Size: 441.5 KB / Downloads: 370)
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 Algorithm
Based on depth-first recursive search
Approach
Tests whether solution has been found
If found solution, return it
Else for each choice that can be made
Make that choice
Recur
If recursion returns a solution, return it
If no choices remain, return failure
Some times called “search tree”
Backtracking Algorithm – Example
Color a map with no more than four colors
If all countries have been colored return success
Else for each color c of four colors and country n
If country n is not adjacent to a country that has been colored c
Color country n with color c
Recursively color country n+1
If successful, return success
Return failure
Recursive Backtracking
Pseudo code for recursive backtracking algorithms
If at a solution, return success
for( every possible choice from current state / node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next high level
Back out of the current choice to restore the state at the beginning of the loop.
Report failure
Backtracking
Backtracking.ppt (Size: 441.5 KB / Downloads: 370)
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 Algorithm
Based on depth-first recursive search
Approach
Tests whether solution has been found
If found solution, return it
Else for each choice that can be made
Make that choice
Recur
If recursion returns a solution, return it
If no choices remain, return failure
Some times called “search tree”
Backtracking Algorithm – Example
Color a map with no more than four colors
If all countries have been colored return success
Else for each color c of four colors and country n
If country n is not adjacent to a country that has been colored c
Color country n with color c
Recursively color country n+1
If successful, return success
Return failure
Recursive Backtracking
Pseudo code for recursive backtracking algorithms
If at a solution, return success
for( every possible choice from current state / node)
Make that choice and take one step along path
Use recursion to solve the problem for the new node / state
If the recursive call succeeds, report the success to the next high level
Back out of the current choice to restore the state at the beginning of the loop.
Report failure