## BACKTRACKING

Moderator: Board moderators

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

### BACKTRACKING

CAN ANYONE PLEASE GIVE ME THE GENERAL VERSION OF ITERATIVE BACTRACKING AND EXPLAIN ITS STRUCTURE?
playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
I really don't know the answer, I'm just posting becuase I've been curious about an iterative version of quicksort, anyone knows anything about it?
be cool...
zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

### 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]
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.
Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Contact:
you can try the book Algorithm written by shahni. As much as i remember there describe an iterative mathod.

M H Rasel
Alessandro
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
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it
Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm
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