001package org.cpsolver.ifs.heuristics; 002 003import java.util.Collection; 004import java.util.Map; 005 006import org.cpsolver.ifs.assignment.Assignment; 007import org.cpsolver.ifs.assignment.context.AssignmentContext; 008import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 009import org.cpsolver.ifs.model.Neighbour; 010import org.cpsolver.ifs.model.Value; 011import org.cpsolver.ifs.model.Variable; 012import org.cpsolver.ifs.solution.Solution; 013import org.cpsolver.ifs.solution.SolutionListener; 014import org.cpsolver.ifs.solver.Solver; 015import org.cpsolver.ifs.util.DataProperties; 016 017/** 018 * Simple extension of a provided {@link NeighbourSelection} that halts the construction 019 * heuristic or the IFS search when the underlying heuristic is unable to improve the 020 * number of assigned variables. When a given number of non-improving iterations is reached, 021 * the {@link MaxIdleNeighbourSelection} extension starts returning null. The counter gets 022 * automatically reset every time a solution with more variables assigned is stored as best 023 * solution. 024 025 * @see NeighbourSelection 026 * 027 * @version IFS 1.4 (Iterative Forward Search)<br> 028 * Copyright (C) 2024 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see <a href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>. 044 * 045 * @param <V> Variable 046 * @param <T> Value 047 **/ 048public class MaxIdleNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V, T, MaxIdleNeighbourSelection<V, T>.MaxIdleContext> implements SolutionListener<V, T> { 049 protected NeighbourSelection<V, T> iParent = null; 050 protected int iMaxIdle = 1000; 051 protected int iBestAssigned = 0; 052 053 public MaxIdleNeighbourSelection(DataProperties properties, NeighbourSelection<V, T> parent, int maxIdle) { 054 iParent = parent; 055 iMaxIdle = maxIdle; 056 } 057 058 @Override 059 public void init(Solver<V, T> solver) { 060 super.init(solver); 061 iParent.init(solver); 062 solver.currentSolution().addSolutionListener(this); 063 } 064 065 066 @Override 067 public void solutionUpdated(Solution<V, T> solution) { 068 } 069 070 @Override 071 public void getInfo(Solution<V, T> solution, Map<String, String> info) { 072 } 073 074 @Override 075 public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) { 076 } 077 078 @Override 079 public void bestCleared(Solution<V, T> solution) { 080 } 081 082 @Override 083 public void bestSaved(Solution<V, T> solution) { 084 if (solution.getAssignment().nrAssignedVariables() > iBestAssigned) 085 getContext(solution.getAssignment()).reset(); 086 iBestAssigned = solution.getAssignment().nrAssignedVariables(); 087 } 088 089 @Override 090 public void bestRestored(Solution<V, T> solution) { 091 } 092 093 @Override 094 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 095 MaxIdleContext context = getContext(solution.getAssignment()); 096 if (context.inc() >= iMaxIdle) 097 return null; 098 return iParent.selectNeighbour(solution); 099 } 100 101 @Override 102 public MaxIdleContext createAssignmentContext(Assignment<V, T> assignment) { 103 return new MaxIdleContext(assignment); 104 } 105 106 public class MaxIdleContext implements AssignmentContext { 107 private int iCounter = 0; 108 109 public MaxIdleContext(Assignment<V, T> assignment) { 110 } 111 112 public int inc() { return iCounter++; } 113 public void reset() { iCounter = 0; } 114 115 } 116}