1 files changed, 228 insertions, 0 deletions

diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java
new file mode 100644
index 00000000..fe5604a1
--- /dev/null
+++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.dse/src/org/eclipse/viatra/dse/api/strategy/impl/BestFirstStrategy.java
@@ -0,0 +1,228 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Andras Szabolcs Nagy and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package org.eclipse.viatra.dse.api.strategy.impl;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.PriorityQueue;
+
+import org.apache.log4j.Logger;
+import org.eclipse.viatra.dse.api.strategy.interfaces.IStrategy;
+import org.eclipse.viatra.dse.base.ThreadContext;
+import org.eclipse.viatra.dse.objectives.Fitness;
+import org.eclipse.viatra.dse.objectives.ObjectiveComparatorHelper;
+import org.eclipse.viatra.dse.solutionstore.SolutionStore;
+
+/**
+ * This exploration strategy eventually explorers the whole design space but goes in the most promising directions
+ * first, based on the {@link Fitness}.
+ * 
+ * There are a few parameter to tune such as
+ * <ul>
+ * <li>maximum depth</li>
+ * <li>continue the exploration from a state that satisfies the hard objectives (the default that it will
+ * backtrack),</li>
+ * <li>whether to continue the exploration from the newly explored state if it is at least equally good than the
+ * previous one or only if it is better (default is "at least equally good").</li>
+ * </ul>
+ * 
+ * @author Andras Szabolcs Nagy
+ *
+ */
+public class BestFirstStrategy implements IStrategy {
+
+    private ThreadContext context;
+    private SolutionStore solutionStore;
+
+    private int maxDepth;
+    private boolean isInterrupted = false;
+    private boolean backTrackIfSolution = true;
+    private boolean onlyBetterFirst = false;
+
+    private PriorityQueue<TrajectoryWithFitness> trajectoiresToExplore;
+    private Logger logger = Logger.getLogger(IStrategy.class);
+
+    private static class TrajectoryWithFitness {
+
+        public Object[] trajectory;
+        public Fitness fitness;
+
+        public TrajectoryWithFitness(Object[] trajectory, Fitness fitness) {
+            super();
+            this.trajectory = trajectory;
+            this.fitness = fitness;
+        }
+
+        @Override
+        public String toString() {
+            return Arrays.toString(trajectory) + fitness.toString();
+        }
+
+    }
+
+    /**
+     * Creates a new best-first search algorithm without depth limit.
+     */
+    public BestFirstStrategy() {
+        this(-1);
+    }
+
+    /**
+     * Creates a new best-first search algorithm with depth limit.
+     * 
+     * @param maxDepth
+     *            A negative <code>maxDepth</code> means no depth limit, zero means the checking of the initial state.
+     */
+    public BestFirstStrategy(int maxDepth) {
+        if (maxDepth < 0) {
+            this.maxDepth = Integer.MAX_VALUE;
+        } else {
+            this.maxDepth = maxDepth;
+        }
+    }
+
+    public BestFirstStrategy continueIfHardObjectivesFulfilled() {
+        backTrackIfSolution = false;
+        return this;
+    }
+
+    public BestFirstStrategy goOnOnlyIfFitnessIsBetter() {
+        onlyBetterFirst = true;
+        return this;
+    }
+
+    @Override
+    public void initStrategy(ThreadContext context) {
+        this.context = context;
+        this.solutionStore = context.getGlobalContext().getSolutionStore();
+        final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper();
+
+        trajectoiresToExplore = new PriorityQueue<TrajectoryWithFitness>(11,
+                (o1, o2) -> objectiveComparatorHelper.compare(o2.fitness, o1.fitness));
+    }
+
+    @Override
+    public void explore() {
+        final ObjectiveComparatorHelper objectiveComparatorHelper = context.getObjectiveComparatorHelper();
+
+        boolean globalConstraintsAreSatisfied = context.checkGlobalConstraints();
+        if (!globalConstraintsAreSatisfied) {
+            logger.info("Global contraint is not satisifed in the first state. Terminate.");
+            return;
+        }
+
+        final Fitness firstFittness = context.calculateFitness();
+        if (firstFittness.isSatisifiesHardObjectives()) {
+            context.newSolution();
+            logger.info("First state is a solution. Terminate.");
+            return;
+        }
+
+        if (maxDepth == 0) {
+            return;
+        }
+
+        final Object[] firstTrajectory = context.getTrajectory().toArray(new Object[0]);
+        TrajectoryWithFitness currentTrajectoryWithFittness = new TrajectoryWithFitness(firstTrajectory, firstFittness);
+        trajectoiresToExplore.add(currentTrajectoryWithFittness);
+
+        mainLoop: while (!isInterrupted) {
+
+            if (currentTrajectoryWithFittness == null) {
+                if (trajectoiresToExplore.isEmpty()) {
+                    logger.debug("State space is fully traversed.");
+                    return;
+                } else {
+                    currentTrajectoryWithFittness = trajectoiresToExplore.element();
+                    if (logger.isDebugEnabled()) {
+                        logger.debug("New trajectory is chosen: " + currentTrajectoryWithFittness);
+                    }
+                    context.getDesignSpaceManager().executeTrajectoryWithMinimalBacktrackWithoutStateCoding(currentTrajectoryWithFittness.trajectory);
+                }
+            }
+
+            Collection<Object> activationIds = context.getUntraversedActivationIds();
+            Iterator<Object> iterator = activationIds.iterator();
+
+            while (!isInterrupted && iterator.hasNext()) {
+                final Object nextActivation = iterator.next();
+                if (!iterator.hasNext()) {
+                    logger.debug("Last untraversed activation of the state.");
+                    trajectoiresToExplore.remove(currentTrajectoryWithFittness);
+                }
+
+                if (logger.isDebugEnabled()) {
+                    logger.debug("Executing new activation: " + nextActivation);
+                }
+                context.executeAcitvationId(nextActivation);
+                if (context.isCurrentStateAlreadyTraversed()) {
+                    logger.info("The new state is already visited.");
+                    context.backtrack();
+                } else if (!context.checkGlobalConstraints()) {
+                    logger.debug("Global contraint is not satisifed.");
+                    context.backtrack();
+                } else {
+                    final Fitness nextFitness = context.calculateFitness();
+                    if (nextFitness.isSatisifiesHardObjectives()) {
+                        solutionStore.newSolution(context);
+                        logger.debug("Found a solution.");
+                        if (backTrackIfSolution) {
+                            context.backtrack();
+                            continue;
+                        }
+                    }
+                    if (context.getDepth() >= maxDepth) {
+                        logger.debug("Reached max depth.");
+                        context.backtrack();
+                        continue;
+                    }
+
+                    TrajectoryWithFitness nextTrajectoryWithFittness = new TrajectoryWithFitness(
+                            context.getTrajectory().toArray(), nextFitness);
+                    trajectoiresToExplore.add(nextTrajectoryWithFittness);
+
+                    int compare = objectiveComparatorHelper.compare(currentTrajectoryWithFittness.fitness,
+                            nextTrajectoryWithFittness.fitness);
+                    if (compare < 0) {
+                        logger.debug("Better fitness, moving on: " + nextFitness);
+                        currentTrajectoryWithFittness = nextTrajectoryWithFittness;
+                        continue mainLoop;
+                    } else if (compare == 0) {
+                        if (onlyBetterFirst) {
+                            logger.debug("Equally good fitness, backtrack: " + nextFitness);
+                            context.backtrack();
+                            continue;
+                        } else {
+                            logger.debug("Equally good fitness, moving on: " + nextFitness);
+                            currentTrajectoryWithFittness = nextTrajectoryWithFittness;
+                            continue mainLoop;
+                        }
+                    } else {
+                        logger.debug("Worse fitness.");
+                        currentTrajectoryWithFittness = null;
+                        continue mainLoop;
+                    }
+                }
+            }
+
+            logger.debug("State is fully traversed.");
+            trajectoiresToExplore.remove(currentTrajectoryWithFittness);
+            currentTrajectoryWithFittness = null;
+
+        }
+        logger.info("Interrupted.");
+    }
+
+    @Override
+    public void interruptStrategy() {
+        isInterrupted = true;
+    }
+
+}