[gecode-users] LDS search

[Christian Schulte]

The version of LDS I use has the advantage that memory is limited by the
number of discrepancies made. That's not too bad, as discrepancies tend to
be small.

Emulating any search via priority queue is a cute model and works for some
cases but not here apparently...

Christian

On 1/31/08 4:05 PM, "Stefano Gualandi" <gualandi at elet.polimi.it> wrote:

> 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:gualandi at elet.polimi.it]
>> Sent: Wednesday, January 23, 2008 10:00 AM
>> To: cschulte at kth.se
>> Cc: users at gecode.org
>> 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
>> 
>> 
> 

--
Christian Schulte, web.ict.kth.se/~cschulte/