[gecode-users] LDS search

[Stefano Gualandi]

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
>
>