Re: [eclipse-users] Question about branch and bound

From: Joachim Schimpf (Independent Contractor) <"Joachim>
Date: Fri, 25 Jan 2008 00:50:18 +0000
Dimitris Bilidas wrote:
> Hello all, 
> I am a little confused, so sorry if my question is somehow naive or something.
> Let's say that we have the problem of the N-queens as it is solved here
> in which additionally every solution has a specific cost.  So we have changed
> the labeling predicate with one more variable Cost in which we assign the
> numeric value of the cost for every solution. For example:
> labeling(a, AllVars, BT, Cost) :-
>         search(AllVars, 0, input_order, indomain, complete, [backtrack(BT)]),
>         computeCost(AllVars, Cost).
> Now we call this like that:
> branch_and_bound:minimize(labeling(Strategy, Board, BT, Cost), Cost)
> If we write something like that, will we have any pruning at all? From what I
> have understood no, because the cost is being computed only after a final
> solution has been found. So what should we do if we wanted to start pruning
> possible solutions earlier?

You are right, you won't get any pruning if you write it like that.
That's why you should express the cost in terms of a constraint,
and do it before starting the search, i.e.

    Cost #= ...,
    branch_and_bound:minimize(labeling(Board), Cost).

E.g. to minimize the distance between adjacent queens:

    ( fromto(Board, [Qi,Qj|Qs], [Qj|Qs], [_Qn]), foreach(D,Ds) do
        D #= abs(Qi-Qj)
    Cost #= sum(Ds),
    branch_and_bound:minimize(labeling(Board), Cost).

-- Joachim
Received on Fri Jan 25 2008 - 00:50:42 CET

This archive was generated by hypermail 2.3.0 : Sun Aug 25 2019 - 03:15:37 CEST