[gecode-users] LDS search

[Christian Schulte]

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