BACKTRACKING

[jagadish]

CAN ANYONE PLEASE GIVE ME THE GENERAL VERSION OF ITERATIVE BACTRACKING AND EXPLAIN ITS STRUCTURE?

[playerX]

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?

[zsepi]

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]

[Master]

you can try the book Algorithm written by shahni. As much as i remember there describe an iterative mathod.

M H Rasel

[Alessandro]

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

[Pavl0]

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