Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/30/13 21:16:22 (12 years ago)
Author:
ascheibe
Message:

#2039 improved performance of TSPSimilarityCalculator

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

    r9030 r9413  
    8585
    8686    private static double CalculateRelativeUndirected(Permutation left, Permutation right) {
    87       int[,] edges = new int[right.Length, 2];
    88       for (int i = 0; i < right.Length; i++) {
    89         edges[right[i], 0] = right[(i + 1) % right.Length];
    90         edges[right[i], 1] = right[(i - 1 + right.Length) % right.Length];
    91       }
     87      int[] edgesR = CalculateEdgesVector(right);
     88      int[] edgesL = CalculateEdgesVector(left);
    9289
    9390      double similarity = 0.0;
    9491      for (int i = 0; i < left.Length; i++) {
    95         int targetCity = left[(i + 1) % left.Length];
    96         if (targetCity == edges[left[i], 0] || targetCity == edges[left[i], 1])
     92        if ((edgesL[i] == edgesR[i]) || (edgesL[edgesR[i]] == i))
    9793          similarity++;
    9894      }
    9995
    10096      return similarity / left.Length;
     97    }
     98
     99    private static int[] CalculateEdgesVector(Permutation permutation) {
     100      // transform path representation into adjacency representation
     101      int[] edgesVector = new int[permutation.Length];
     102      for (int i = 0; i < permutation.Length - 1; i++)
     103        edgesVector[permutation[i]] = permutation[i + 1];
     104      edgesVector[permutation[permutation.Length - 1]] = permutation[0];
     105      return edgesVector;
    101106    }
    102107
Note: See TracChangeset for help on using the changeset viewer.