001package org.cpsolver.ifs.algorithms.neighbourhoods; 002 003import java.util.List; 004 005import org.cpsolver.ifs.assignment.Assignment; 006import org.cpsolver.ifs.heuristics.NeighbourSelection; 007import org.cpsolver.ifs.model.Model; 008import org.cpsolver.ifs.model.Neighbour; 009import org.cpsolver.ifs.model.SimpleNeighbour; 010import org.cpsolver.ifs.model.Value; 011import org.cpsolver.ifs.model.Variable; 012import org.cpsolver.ifs.solution.Solution; 013import org.cpsolver.ifs.solver.Solver; 014import org.cpsolver.ifs.util.DataProperties; 015import org.cpsolver.ifs.util.ToolBox; 016 017 018/** 019 * Try to assign a variable with a new value. A variable is selected randomly, a 020 * different (available) value is randomly selected for the variable -- the variable is 021 * assigned with the new value if there is no conflict. 022 * <br> 023 * 024 * @version IFS 1.3 (Iterative Forward Search)<br> 025 * Copyright (C) 2014 Tomáš Müller<br> 026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 027 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 028 * <br> 029 * This library is free software; you can redistribute it and/or modify 030 * it under the terms of the GNU Lesser General Public License as 031 * published by the Free Software Foundation; either version 3 of the 032 * License, or (at your option) any later version. <br> 033 * <br> 034 * This library is distributed in the hope that it will be useful, but 035 * 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. <br> 038 * <br> 039 * You should have received a copy of the GNU Lesser General Public 040 * License along with this library; if not see 041 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 042 * @param <V> Variable 043 * @param <T> Value 044 */ 045public class RandomMove<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, HillClimberSelection { 046 protected boolean iHC = false; 047 048 public RandomMove(DataProperties config) { 049 } 050 051 @Override 052 public void setHcMode(boolean hcMode) { 053 iHC = hcMode; 054 } 055 056 @Override 057 public void init(Solver<V, T> solver) { 058 } 059 060 @Override 061 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 062 Model<V, T> model = solution.getModel(); 063 Assignment<V, T> assignment = solution.getAssignment(); 064 int varIdx = ToolBox.random(model.variables().size()); 065 for (int i = 0; i < model.variables().size(); i++) { 066 V variable = model.variables().get((i + varIdx) % model.variables().size()); 067 List<T> values = variable.values(solution.getAssignment()); 068 if (values.isEmpty()) continue; 069 int valIdx = ToolBox.random(values.size()); 070 for (int j = 0; j < values.size(); j++) { 071 T value = values.get((j + valIdx) % values.size()); 072 if (!model.inConflict(assignment, value)) { 073 SimpleNeighbour<V, T> n = new SimpleNeighbour<V, T>(variable, value); 074 if (!iHC || n.value(assignment) <= 0) return n; 075 } 076 } 077 } 078 return null; 079 } 080}