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

From: Oliver Shycle <oliver.shycle_at_...1...>
Date: Mon, 21 Jun 2010 16:00:32 +0200
Hi again,

you're right. Wrapping search does in my example indeed decrease the amount
of solutions but it is NOT eliminating duplicates. After some more
investigation I found out that the problem was in my model, not in the
search routine usage. Accidentally once/1 led to the results I expected.
So I think I stick to the standard ic_search/6 routine still. So far I
didn't need to implement own variable selection methods. If so, I'll keep
your advice in mind! :-)

Have a nice day,
Oliver.


On 21 June 2010 15:12, Thorsten Winterer <thorsten_winterer_at_...126...> wrote:

>  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_at_...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
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>>
>
>
>
>
>
> ------------------------------------------------------------------------------
> 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 - 14:00:43 CEST

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET