Changeset 6628 for trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

Timestamp:

08/04/11 10:04:09 (13 years ago)

Author:

abeham

Message:

#1541, #1603, #1606, #1607

• merged to trunk

Location:

trunk/sources

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

@@ -49 +49 @@
     }
 
+    /// <summary>
+    /// Calculates the quality of the move <paramref name="move"/> by evaluating the changes.
+    /// The runtime complexity of this method is O(N) with N being the size of the permutation.
+    /// </summary>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The move that is to be evaluated if it was applied to the current permutation.</param>
+    /// <param name="weights">The weights matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
     public static double Apply(Permutation assignment, Swap2Move move, DoubleMatrix weights, DoubleMatrix distances) {
       if (move.Index1 == move.Index2) return 0;
@@ -73 +82 @@
     }
 
+    /// <summary>
+    /// Is able to compute the move qualities faster O(1) in some cases if it knows the quality of
+    /// performing the move <paramref name="move"/> previously. In other cases it performs a
+    /// standard move quality calculation with runtime complexity O(N).
+    /// </summary>
+    /// <remarks>
+    /// The number of cases that the calculation can be performed faster grows with N^2
+    /// while the number of cases which require a larger recalculation grows linearly with N.
+    /// Larger problem instances thus benefit from this faster method to a larger degree.
+    /// </remarks>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The current move that is to be evaluated.</param>
+    /// <param name="previousQuality">The quality of that move as evaluated for the previous permutation.</param>
+    /// <param name="weights">The weigths matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <param name="lastMove">The move that was applied to transform the permutation from the previous to the current one.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
+    public static double Apply(Permutation assignment, Swap2Move move, double previousQuality,
+      DoubleMatrix weights, DoubleMatrix distances, Swap2Move lastMove) {
+      bool overlapsLastMove = move.Index1 == lastMove.Index1
+                           || move.Index2 == lastMove.Index1
+                           || move.Index1 == lastMove.Index2
+                           || move.Index2 == lastMove.Index2;
+
+      if (!overlapsLastMove) {
+        int r = lastMove.Index1, u = move.Index1, s = lastMove.Index2, v = move.Index2;
+        int pR = assignment[lastMove.Index1], pU = assignment[move.Index1], pS = assignment[lastMove.Index2], pV = assignment[move.Index2];
+
+        return previousQuality
+          + (weights[r, u] - weights[r, v] + weights[s, v] - weights[s, u])
+            * (distances[pS, pU] - distances[pS, pV] + distances[pR, pV] - distances[pR, pU])
+          + (weights[u, r] - weights[v, r] + weights[v, s] - weights[u, s])
+            * (distances[pU, pS] - distances[pV, pS] + distances[pV, pR] - distances[pU, pR]);
+      } else {
+        return Apply(assignment, move, weights, distances);
+      }
+    }
+
     public override IOperation Apply() {
       Swap2Move move = Swap2MoveParameter.ActualValue;