An
AbstractSearchLoop object is part of the
Solver object and the way to guide the search, it builds the
tree search.
When the initial propagation does not lead to a solution but a fix point, some decisions have to be applied to find solutions. It also deals with
IEnvironment worlds backups and rollbacks, ie the backtracking system.
By default, a
AbstractSearchLoop object is a flatten representation of a recurcive concept. Once a fix point is reached, a decision is taken to restart the propagation loop and find solutions or detect fails. This is decomposed in 6 steps:
INIT: initializes the internal structures and statistics,INITIAL_PROPAGATION: runs the initial propagations, checks the root node feasiblity,OPEN_NODE: checks if the current state is a solution -- every variables are instantiated-- (next step is STOP) or if fix point is reached, requiring a new decision, (next step is DOWN_LEFT_BRANCH);DOWN_LEFT_BRANCH: backs up the current state, applies a decision (commonly domain reduction to a singleton), then propagates this new information on the Constraint network. If a contradiction occurs, it reconsiders the current decision (next step is UP_BRANCH), otherwise, a new fix point is reached (next step is OPEN_NODE;UP_BRANCH: rolls back the previous state, reconsiders the previsous decision then propagates this new information on the Constraint network. If a contradiction occurs, it reconsiders the decision before (next step is UP_BRANCH), otherwise, requires a new decision (next step is DOWN_LEFT_BRANCH;RESTART: restarts the search from a previous node, commonly the root node.
@author Xavier Lorca
@author Charles Prud'homme
@version 0.01, june 2010
@since 0.01