### BACKTRACKING

Posted:

**Sat Feb 28, 2004 6:08 am**CAN ANYONE PLEASE GIVE ME THE GENERAL VERSION OF ITERATIVE BACTRACKING AND EXPLAIN ITS STRUCTURE?

Page **1** of **1**

Posted: **Sat Feb 28, 2004 6:08 am**

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

Posted: **Sun Feb 29, 2004 12:04 am**

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?

Posted: **Sun Feb 29, 2004 8:00 pm**

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]

Posted: **Sun Mar 14, 2004 7:53 am**

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

M H Rasel

M H Rasel

Posted: **Fri Jun 18, 2004 12:15 am**

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

Posted: **Wed Jul 28, 2004 4:52 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

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