001package org.cpsolver.coursett.neighbourhoods; 002 003import java.util.Collection; 004import java.util.Map; 005 006import org.cpsolver.coursett.heuristics.NeighbourSelectionWithSuggestions; 007import org.cpsolver.coursett.model.Lecture; 008import org.cpsolver.coursett.model.Placement; 009import org.cpsolver.ifs.assignment.Assignment; 010import org.cpsolver.ifs.model.Neighbour; 011import org.cpsolver.ifs.solution.Solution; 012import org.cpsolver.ifs.util.DataProperties; 013import org.cpsolver.ifs.util.ToolBox; 014 015/** 016 * A simple neighbor selection based on {@link NeighbourSelectionWithSuggestions}, 017 * only triggering when there is an unassigned class. The selection picks a random unassigned 018 * class and tries to do a limited-depth search up to the Neighbour.SuggestionDepth 019 * depth. If successful, the returned suggestion is always considered improving as 020 * it finds an assignment that increases the number of assigned classes. 021 * <br> 022 * 023 * @version IFS 1.3 (Iterative Forward Search)<br> 024 * Copyright (C) 2014 Tomáš Müller<br> 025 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 026 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 027 * <br> 028 * This library is free software; you can redistribute it and/or modify 029 * it under the terms of the GNU Lesser General Public License as 030 * published by the Free Software Foundation; either version 3 of the 031 * License, or (at your option) any later version. <br> 032 * <br> 033 * This library is distributed in the hope that it will be useful, but 034 * 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. <br> 037 * <br> 038 * You should have received a copy of the GNU Lesser General Public 039 * License along with this library; if not see 040 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 041 */ 042public class Suggestion extends NeighbourSelectionWithSuggestions { 043 044 public Suggestion(DataProperties properties) throws Exception { 045 super(properties); 046 } 047 048 @Override 049 public Neighbour<Lecture, Placement> selectNeighbour(Solution<Lecture, Placement> solution) { 050 Collection<Lecture> unassigned = solution.getModel().unassignedVariables(solution.getAssignment()); 051 if (!unassigned.isEmpty()) { 052 Lecture lecture = ToolBox.random(unassigned); 053 int depth = Math.max(2, ToolBox.random(iSuggestionDepth)); 054 Neighbour<Lecture, Placement> neigbour = selectNeighbourWithSuggestions(solution, lecture, depth); 055 if (neigbour != null) 056 return new SuggestionNeighbour(neigbour); 057 } 058 return null; 059 } 060 061 /** Simple @{link Neighbour} wrapper always returning -1 as the value */ 062 static class SuggestionNeighbour implements Neighbour<Lecture, Placement> { 063 Neighbour<Lecture, Placement> iNeigbour; 064 065 SuggestionNeighbour(Neighbour<Lecture, Placement> neigbour) { 066 iNeigbour = neigbour; 067 } 068 069 @Override 070 public void assign(Assignment<Lecture, Placement> assignment, long iteration) { 071 iNeigbour.assign(assignment, iteration); 072 } 073 074 @Override 075 public double value(Assignment<Lecture, Placement> assignment) { 076 return -1; 077 } 078 079 @Override 080 public Map<Lecture, Placement> assignments() { 081 return iNeigbour.assignments(); 082 } 083 } 084}