Hi Christian, I have read again the original papers on LDS (by Harvey&Ginsberg) and on Improved-LDS (by Korf).
My observation was half right, half wrong: - half right: it is possible to implement DFS and LDS where the only implementation difference consists in using a simple-queue instead of a stack. I did in Oz last night, and if you like I can share the code. By implementing LDS in that way every node is visited exactly once, but unfortunately it requires exponential memory (worst case) for the queue... as BFS ... - half wrong: it boils LDS down to a BFS-like search, that is, LDS could be implemented as a BFS (with a priority queue, instead of a queue) where the cost function of a node is its number of discrepancy, as suggested in the paper of Korf. cheers, Stefano On Jan 28, 2008, at 2:18 PM, Christian Schulte wrote: > Hi Stefano, > > The number of fails can be higher as LDS might explore the same > parts of the > tree more than once (You probe the tree several times with > increasing max > discrepancy). The details I have to check again. > > Your second observation I do not really buy into: when you turn a > stack into > a queue you get BFS but not LDS! LDS is really unique in that it > iterates > probes with an increasing number of discrepancies allowed. > > Cheers > Christian > > -- > Christian Schulte, www.ict.kth.se/~cschulte/ > > > -----Original Message----- > From: Stefano Gualandi [mailto:[EMAIL PROTECTED] > Sent: Wednesday, January 23, 2008 10:00 AM > To: [EMAIL PROTECTED] > Cc: [EMAIL PROTECTED] > Subject: Re: [gecode-users] LDS search > > Dear Christian, > well, I have been working a bit more on LDS... my suggestion is more a > work-around than a fix. > I have noticed one more thing: > > - when solving the example I sent you with max discrepancy equal to > 1000, we > get 1999 fails! > Altough, we should get the same number of fails of using DFS, since > it is > just visiting the same tree with a different order... > > I did try to get trough the Gecode sources but, so far, I have not > succeed > in fixing it. > > Thus, I have tried to figure out how to implement LDS by my own, > and I have > just realized that LDS is exactly like DFS, but using a queue > instead of a > stack (see the attached examples). In that way, it is not necessary > to use a > max-discrepancy parameter when calling the search engine. Do you > agree? > > thanks (a lot) in advance, > Stefano > > _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
