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