[ library(tentative) | Reference Manual | Alphabetic Index ]

tent_minimize_random(+MoveGenerator, ?Violations, -MoveId)

Find a move that minimizes violations
MoveGenerator
A goal
Violations
A tentative variable
MoveId
Placeholder for move identifier

Description

This metapredicate finds a local search move that minimizes violations. It requries that the tentative variables and constraints over them have been set up beforehand.

MoveGenerator is a nondeterministic goal that implements a local search step. It should explore all neighbours on backtracking. A move should be made by changing tentative values, and instantiating MoveId to a unique identifier for every move.

Violations should be a tentative variable that reflects the total problem violations that are to be minimized.

MoveId is a variable which occurs in MoveGenerator. At the end of minimization, it will contain the ID of the best move. If there are multiple moves of the same quality, a random one is returned.

After tent_minimize_random/3 succeeds, all the trial moves are undone and the computation state is as before the call. Only the MoveId contains the identifier of the best move. This move can then be committed to by performing it again according to MoveId.

Modules

This predicate is sensitive to its module context (tool predicate, see @/2).

Fail Conditions

Fails if MoveGenerator fails

Examples


    % This example tries 8 moves that lead to different tentative values
    % of Viol. One of the moves that lead to a value of 1 is selected.

    ?-  Viol tent_set 0,
	tent_minimize_random((
		between(1, 8, 1, MoveId),
		arg(MoveId, viol(9,5,6,1,3,6,1,9), N),
		Viol tent_set N
	    ), Viol, MoveId).
     ...
     MoveId = 7		% 4 or 7, the result is random!
     Yes (0.00s cpu)
    

See Also

tent_set / 2