001 package net.sf.cpsolver.studentsct.heuristics.selection;
002
003 import java.util.Collections;
004 import java.util.Enumeration;
005 import java.util.Vector;
006
007 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
008 import net.sf.cpsolver.ifs.model.Neighbour;
009 import net.sf.cpsolver.ifs.solution.Solution;
010 import net.sf.cpsolver.ifs.solver.Solver;
011 import net.sf.cpsolver.ifs.util.DataProperties;
012 import net.sf.cpsolver.ifs.util.Progress;
013 import net.sf.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection;
014 import net.sf.cpsolver.studentsct.model.Request;
015
016 /**
017 * Use backtrack neighbour selection.
018 * For all unassigned variables (in a random order),
019 * {@link RandomizedBacktrackNeighbourSelection} is being used.
020 *
021 * <br><br>
022 *
023 * @version
024 * StudentSct 1.1 (Student Sectioning)<br>
025 * Copyright (C) 2007 Tomáš Müller<br>
026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 * Lazenska 391, 76314 Zlin, Czech Republic<br>
028 * <br>
029 * This library is free software; you can redistribute it and/or
030 * modify it under the terms of the GNU Lesser General Public
031 * License as published by the Free Software Foundation; either
032 * version 2.1 of the License, or (at your option) any later version.
033 * <br><br>
034 * This library is distributed in the hope that it will be useful,
035 * but WITHOUT ANY WARRANTY; without even the implied warranty of
036 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 * Lesser General Public License for more details.
038 * <br><br>
039 * You should have received a copy of the GNU Lesser General Public
040 * License along with this library; if not, write to the Free Software
041 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
042 */
043
044 public class BacktrackSelection implements NeighbourSelection {
045 private RandomizedBacktrackNeighbourSelection iRBtNSel = null;
046 private Enumeration iRequestEnumeration = null;
047
048 public BacktrackSelection(DataProperties properties) {
049 }
050
051 public void init(Solver solver, String name) {
052 Vector unassigned = new Vector(solver.currentSolution().getModel().unassignedVariables());
053 Collections.shuffle(unassigned);
054 iRequestEnumeration = unassigned.elements();
055 if (iRBtNSel==null) {
056 try {
057 iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties());
058 iRBtNSel.init(solver);
059 } catch (Exception e) {
060 throw new RuntimeException(e.getMessage(),e);
061 }
062 }
063 Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, unassigned.size());
064 }
065
066 public void init(Solver solver) {
067 init(solver, "Backtracking...");
068 }
069
070 public Neighbour selectNeighbour(Solution solution) {
071 while (iRequestEnumeration.hasMoreElements()) {
072 Request request = (Request)iRequestEnumeration.nextElement();
073 Progress.getInstance(solution.getModel()).incProgress();
074 Neighbour n = iRBtNSel.selectNeighbour(solution, request);
075 if (n!=null) return n;
076 }
077 return null;
078 }
079
080 }