BACKTRACKING
Moderator: Board moderators
BACKTRACKING
CAN ANYONE PLEASE GIVE ME THE GENERAL VERSION OF ITERATIVE BACTRACKING AND EXPLAIN ITS STRUCTURE?
iterative backtracking
use a stack - every time when you'd go one more level into the recursion, store all your variables on the top of the stack, and modify the variables to values they would have taken in the next recursion step. when you would return from a recursion call, just pop the top of the stack and store them in the variables you use.
haven't done it myself yet, but this is the general idea to go about it. Once I get finished with this ^$&* paper, I might actually implement it[/code]
haven't done it myself yet, but this is the general idea to go about it. Once I get finished with this ^$&* paper, I might actually implement it[/code]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.
-
- New poster
- Posts: 27
- Joined: Mon Jun 14, 2004 10:33 pm
- Location: Latina, Italy
I agree with zsepi, Backtracking isn't nothing more than a depth-first search, so it can be written using a stack. Moreover, it can be transformed in a breadth-first search changing the Pop() operation (pop the element from the head of the container instead from the tail).
Consider that, IMHO, a recursive function is more expensive but more clear and flexible to use than a iterative one. But it's my personal opinion, and I'm not an expert programmer
Goodbye
Ale
Consider that, IMHO, a recursive function is more expensive but more clear and flexible to use than a iterative one. But it's my personal opinion, and I'm not an expert programmer

Goodbye
Ale
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it
Email: alex.ander@infinito.it
same problems can be slove by itteration by cheacking all ways witchaut backtraicing for example knapsack problem can be sloved by backtraicing
end also you can benerate all numbers in binary
n=3
000
001
010
100
011
....
means you take thing where is 1
all numbers can be grenrate witchaut bactraicing ,by adding 1 in bin
2'nd example is NQP
for 8 :
all of 8 quuens must be on o of 64(8x8) position
so you can check em all
in this way:
for(quen1 )
for(quen2 )
for(quen3 )
for(quen4 )
for(quen5 )
for(quen6 )
for(quen7 )
for(quen8 )
for( all position)
{
check if is correct();
}
but in most problems backtaracing can be more effective becose a some ansers can be cuted
end also you can benerate all numbers in binary
n=3
000
001
010
100
011
....
means you take thing where is 1
all numbers can be grenrate witchaut bactraicing ,by adding 1 in bin
2'nd example is NQP
for 8 :
all of 8 quuens must be on o of 64(8x8) position
so you can check em all
in this way:
for(quen1 )
for(quen2 )
for(quen3 )
for(quen4 )
for(quen5 )
for(quen6 )
for(quen7 )
for(quen8 )
for( all position)
{
check if is correct();
}
but in most problems backtaracing can be more effective becose a some ansers can be cuted