[gecode-users] LDS search

[Christian Schulte]

Dear Stefano,

I just finished thorough tests for all search engines including LDS. Now all
pass the tests (DFS and BAB were of course working, Restart had two small
quirks, and LDS was disgustingly broken). We should have done these tests
much earlier. Sorry, Stefano!

I also improved LDS a lot in that the search engine now detects when the
entire tree has been explored: it will then not continue probing with a
discrepancy limit.

This was the last piece missing for 2.0.1 which should be out either
tomorrow or the day after. That will also be the version on which the next
Gecode/J is based.

Cheers and thanks again
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/






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