BACKTRACKING

Let's talk about algorithms!

Moderator: Board moderators

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

BACKTRACKING

Post by jagadish » Sat Feb 28, 2004 6:08 am

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

Post by playerX » 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?
be cool...

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

iterative backtracking

Post by zsepi » 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]
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
Location: St. Johns, Canada
Contact:

Post by Master » 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

Alessandro
New poster
Posts: 27
Joined: Mon Jun 14, 2004 10:33 pm
Location: Latina, Italy

Post by Alessandro » 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
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it

User avatar
Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

Post by Pavl0 » 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

Post Reply

Return to “Algorithms”