|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface VariableSelection<V extends Variable<V,T>,T extends Value<V,T>>
Variable selection criterion.
The IFS algorithm requires a function that selects a variable to be
(re)assigned during the current iteration step. This problem is equivalent to
a variable selection criterion in constraint programming. There are several
guidelines for selecting a variable. In local search, the variable
participating in the largest number of violations is usually selected first.
In backtracking-based algorithms, the first-fail principle is often used,
i.e., a variable whose instantiation is most complicated is selected first.
This could be the variable involved in the largest set of constraints or the
variable with the smallest domain, etc.
We can split the variable selection criterion into two cases. If some
variables remain unassigned, the �worst� variable among them is selected,
i.e., first-fail principle is applied. This may, for example, be the variable
with the smallest domain or with the highest number of hard and/or soft
constraints.
The second case occurs when all variables are assigned. Because the algorithm
does not need to stop when a complete feasible solution is found, the
variable selection criterion for such case has to be considered as well. Here
all variables are assigned but the solution is not good enough, e.g., in the
sense of violated soft constraints. We choose a variable whose change of a
value can introduce the best improvement of the solution. It may, for
example, be a variable whose value violates the highest number of soft
constraints.
It is possible for the solution to become incomplete again after such an
iteration because a value which is not consistent with all hard constraints
can be selected in the value selection criterion. This can also be taken into
account in the variable selection heuristics.
Solver
Method Summary | |
---|---|
void |
init(Solver<V,T> solver)
Initialization |
V |
selectVariable(Solution<V,T> solution)
Variable selection |
Method Detail |
---|
void init(Solver<V,T> solver)
V selectVariable(Solution<V,T> solution)
solution
- current solution
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |