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