[eclipse-users] Question about branch and bound

From: Dimitris Bilidas <grad0903_at_di.uoa.gr>
Date: Fri, 25 Jan 2008 02:04:18 +0200
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
http://eclipse.crosscoreop.com/examples/queens.ecl.txt 
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?

Thanks in advance,
Dimitris.
Received on Fri Jan 25 2008 - 00:04:35 CET

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