Re: [eclipse-clp-users] typical sources of duplicate solutions

From: Oliver Shycle <oliver.shycle_at_googlemail.com>
Date: Mon, 21 Jun 2010 14:24:59 +0200
Thanks for the hint Thorsten.
This seems to be exactly the case. I am using the search routine provided by
the ic library. Wrapping it as you suggested removes all duplicates.
You probably saved me a lot of time. Thanks again.

On 21 June 2010 13:04, Thorsten Winterer <thorsten_winterer_at_web.de> wrote:

> Am 21.06.2010 11:31, schrieb Oliver Shycle:
> > Dear ECLiPSe community,
> >
> > I am using ECLiPSe to solve a special kind of scheduling problem. My
> > problem is coded as a set of many free vaiables and i have a whole
> > bunch of constraints and reified constraints to express how a valid
> > solution has to look like. Basically everything works pretty fine and
> > as expected :-)
> > The only drawback is that i am sometimes experiencing duplicate
> > solutions, i.e. instantiations of variables that are absolutely
> > identical, when i click the "more" button in the TkEclipse interface.
> > I am asking myself where such duplicates might come from. I know that
> > this potentially is very problem-specific. But maybe there are some
> > "typical sources of duplicates" that I could check? At the moment I
> > would have to start with a trial and error approach, because I don't
> > have a clue where they might come from.
> > Thanks for your help.
> >
> > Oliver.
>
> Hi Oliver,
>
> such a behaviour can occur when your search routine can freely select
> the variables to be labelled. The search tree will then contain branches
> where the variables are selected in different orders but, due to the
> constraints, will be bound to the same values.
>
> Consider the following program:
>
> :- lib(ic).
>
> test :-
>    L = [X,Y],
>    L #:: [0..3],
>    X #= Y + 1,
>    solve(L).
>
> solve([]).
> solve(L) :-
>    delete(V,L,R),
>    get_min(V,V),
>    solve(R).
>
>
> The delete/3 call is non-deterministic. During execution, when L is
> [X,Y], V will be first bound to X. On backtracking, V will be bound to
> Y. In both cases, the same solution (X == 1, Y == 0) will be returned.
>
> In this simple case, wrapping delete/3 with once/1 will be sufficient to
> avoid duplicate solutions. Depending on your problem and search
> strategy, more complex steps may be required.
>
> Cheers,
> Thorsten
>
>
>
> ------------------------------------------------------------------------------
> ThinkGeek and WIRED's GeekDad team up for the Ultimate
> GeekDad Father's Day Giveaway. ONE MASSIVE PRIZE to the
> lucky parental unit.  See the prize list and enter to win:
> http://p.sf.net/sfu/thinkgeek-promo
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
Received on Mon Jun 21 2010 - 13:09:35 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET