001package net.sf.cpsolver.ifs.dbt; 002 003import net.sf.cpsolver.ifs.extension.Extension; 004import net.sf.cpsolver.ifs.heuristics.VariableSelection; 005import net.sf.cpsolver.ifs.model.Value; 006import net.sf.cpsolver.ifs.model.Variable; 007import net.sf.cpsolver.ifs.solution.Solution; 008import net.sf.cpsolver.ifs.solver.Solver; 009import net.sf.cpsolver.ifs.util.DataProperties; 010 011/** 012 * Selection of a variable for dynamic backtracking. <br> 013 * <br> 014 * <li>Returns null if all variables are assigned. <li>Checks if there is a 015 * varaible with all values marked as nogood (and pick it if there is any). <li> 016 * Returns the first unassigned variable. <br> 017 * <br> 018 * This IFS solver variable selection heuristics is to be used only in case of 019 * dynamic backtracking and it has no parameters. 020 * 021 * 022 * @version IFS 1.2 (Iterative Forward Search)<br> 023 * Copyright (C) 2006 - 2010 Tomáš Müller<br> 024 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 025 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 026 * <br> 027 * This library is free software; you can redistribute it and/or modify 028 * it under the terms of the GNU Lesser General Public License as 029 * published by the Free Software Foundation; either version 3 of the 030 * License, or (at your option) any later version. <br> 031 * <br> 032 * This library is distributed in the hope that it will be useful, but 033 * WITHOUT ANY WARRANTY; without even the implied warranty of 034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 035 * Lesser General Public License for more details. <br> 036 * <br> 037 * You should have received a copy of the GNU Lesser General Public 038 * License along with this library; if not see 039 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 040 */ 041public class DbtVariableSelection<V extends Variable<V, T>, T extends Value<V, T>> implements VariableSelection<V, T> { 042 private DbtPropagation<V, T> iProp = null; 043 044 public DbtVariableSelection(DataProperties properties) { 045 } 046 047 /** 048 * Heuristics initialization 049 * 050 * @see VariableSelection#init(Solver) 051 */ 052 @Override 053 public void init(Solver<V, T> solver) { 054 for (Extension<V, T> extension : solver.getExtensions()) { 055 if (extension instanceof DbtPropagation<?, ?>) { 056 iProp = (DbtPropagation<V, T>) extension; 057 } 058 } 059 } 060 061 /** 062 * Variable selection 063 * 064 * @see VariableSelection#selectVariable(Solution) 065 */ 066 @Override 067 public V selectVariable(Solution<V, T> solution) { 068 if (solution.getModel().nrUnassignedVariables() == 0) { 069 return null; 070 } 071 if (iProp != null) { 072 for (V variable : solution.getModel().unassignedVariables()) { 073 if (iProp.goodValues(variable).isEmpty()) { 074 return variable; 075 } 076 } 077 } 078 return solution.getModel().unassignedVariables().iterator().next(); 079 } 080 081}