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
