Backtracking.java
package net.splitcells.gel.solution.optimization.meta;
import net.splitcells.dem.environment.config.framework.Option;
import net.splitcells.gel.rating.framework.Rating;
import net.splitcells.gel.solution.Solution;
import net.splitcells.gel.solution.optimization.OnlineOptimization;
import net.splitcells.gel.solution.optimization.space.EnumerableOptimizationSpace;
import java.util.Optional;
import java.util.stream.IntStream;
import static net.splitcells.gel.solution.optimization.primitive.enumerable.Initializer.initializer;
import static net.splitcells.gel.solution.optimization.space.EnumerableOptimizationSpaceI.enumerableOptimizationSpace;
/**
* <p>This is an implementation of the backtracking algorithm.
* The backtracking exits, when the {@link Solution#isComplete()} is {@link true}.
* This implementation backtracks,
* if a given {@link Solution} is worse than the previous {@link Solution}
* found via {@link EnumerableOptimizationSpace#parent()}.</p>
* <p>TODO Record best found {@link Solution},
* that is not specific to an optimizer.</p>
*/
public class Backtracking implements OnlineOptimization {
public static Backtracking backtracking() {
return new Backtracking();
}
private Backtracking() {
}
@Override
public void optimize(Solution solution) {
final var searchSpace = enumerableOptimizationSpace(solution, initializer());
final var startRating = searchSpace.currentState().constraint().rating();
optimize(searchSpace, startRating);
}
private EnumerableOptimizationSpace optimize(EnumerableOptimizationSpace searchSpace, Rating startRating) {
if (searchSpace.currentState().isComplete()) {
return searchSpace;
}
for (int i = 0; i < searchSpace.childrenCount(); ++i) {
final var nextChild = searchSpace.child(i);
if (nextChild.currentState().constraint().rating().betterThanOrEquals(startRating)) {
final var resultingChild = optimize(nextChild, startRating);
if (resultingChild.currentState().isOptimal()) {
return resultingChild;
}
}
searchSpace = nextChild.parent().get();
}
return searchSpace;
}
}