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

From: Thorsten Winterer <thorsten_winterer_at_...126...>
Date: Mon, 21 Jun 2010 15:12:05 +0200
Hi Oliver,

wrapping ic:search/6 with once/1 will not quite do what you want: you
will get only the first solution. All others will be cut. As I
understood you question, you only want to cut the duplicate solutions,
but get non-duplicate solutions on clicking "More".

Also, the pre-defined search methods are stable, so this shouldn't be
the source of the problem, unless you use your own selection method.
Likewise with the value selection methods.

If you do use your own search & selection methods, concentrate your
efforts there. Use the debugger to find out what happens when you click
"More", i.e., why the variable selection is not stable.

Cheers,
Thorsten



Am 21.06.2010 14:24, schrieb Oliver Shycle:
> 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@...126...
> <mailto:thorsten_winterer@...126...>> 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
>     <mailto:ECLiPSe-CLP-Users_at_lists.sourceforge.net>
>     https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>
>
Received on Mon Jun 21 2010 - 13:12:22 CEST

This archive was generated by hypermail 2.2.0 : Mon Jul 09 2018 - 02:05:29 CEST