Facebook
From fadfasdf, 1 Week ago, written in Java.
Embed
Download Paste or View Raw
Hits: 35
  1. import java.util.*;
  2.  
  3. public class TravelingSalesmanHeldKarp {
  4.  
  5.     private static int INFINITY = 100000000;
  6.  
  7.     private static class Index {
  8.         int currentVertex;
  9.         Set<Integer> vertexSet;
  10.  
  11.         @Override
  12.         public boolean equals(Object o) {
  13.             if (this == o) return true;
  14.             if (o == null || getClass() != o.getClass()) return false;
  15.  
  16.             Index index = (Index) o;
  17.  
  18.             if (currentVertex != index.currentVertex) return false;
  19.             return !(vertexSet != null ? !vertexSet.equals(index.vertexSet) : index.vertexSet != null);
  20.         }
  21.  
  22.         @Override
  23.         public int hashCode() {
  24.             int result = currentVertex;
  25.             result = 31 * result + (vertexSet != null ? vertexSet.hashCode() : 0);
  26.             return result;
  27.         }
  28.  
  29.         private static Index createIndex(int vertex, Set<Integer> vertexSet) {
  30.             Index i = new Index();
  31.             i.currentVertex = vertex;
  32.             i.vertexSet = vertexSet;
  33.             return i;
  34.         }
  35.     }
  36.  
  37.     private static class SetSizeComparator implements Comparator<Set<Integer>>{
  38.         @Override
  39.         public int compare(Set<Integer> o1, Set<Integer> o2) {
  40.             return o1.size() - o2.size();
  41.         }
  42.     }
  43.  
  44.     public int minCost(int[][] distance) {
  45.  
  46.         //stores intermediate values in map
  47.         Map<Index, Integer> minCostDP = new HashMap<>();
  48.         Map<Index, Integer> parent = new HashMap<>();
  49.  
  50.         List<Set<Integer>> allSets = generateCombination(distance.length - 1);
  51.  
  52.         for(Set<Integer> set : allSets) {
  53.             for(int currentVertex = 1; currentVertex < distance.length; currentVertex++) {
  54.                 if(set.contains(currentVertex)) {
  55.                     continue;
  56.                 }
  57.                 Index index = Index.createIndex(currentVertex, set);
  58.                 int minCost = INFINITY;
  59.                 int minPrevVertex = 0;
  60.                 //to avoid ConcurrentModificationException copy set into another set while iterating
  61.                 Set<Integer> copySet = new HashSet<>(set);
  62.                 for(int prevVertex : set) {
  63.                     int cost = distance[prevVertex][currentVertex] + getCost(copySet, prevVertex, minCostDP);
  64.                     if(cost < minCost) {
  65.                         minCost = cost;
  66.                         minPrevVertex = prevVertex;
  67.                     }
  68.                 }
  69.                 //this happens for empty subset
  70.                 if(set.size() == 0) {
  71.                     minCost = distance[0][currentVertex];
  72.                 }
  73.                 minCostDP.put(index, minCost);
  74.                 parent.put(index, minPrevVertex);
  75.             }
  76.         }
  77.  
  78.         Set<Integer> set = new HashSet<>();
  79.         for(int i=1; i < distance.length; i++) {
  80.             set.add(i);
  81.         }
  82.         int min = Integer.MAX_VALUE;
  83.         int prevVertex = -1;
  84.         //to avoid ConcurrentModificationException copy set into another set while iterating
  85.         Set<Integer> copySet = new HashSet<>(set);
  86.         for(int k : set) {
  87.             int cost = distance[k][0] + getCost(copySet, k, minCostDP);
  88.             if(cost < min) {
  89.                 min = cost;
  90.                 prevVertex = k;
  91.             }
  92.         }
  93.  
  94.         parent.put(Index.createIndex(0, set), prevVertex);
  95.         printTour(parent, distance.length);
  96.         return min;
  97.     }
  98.  
  99.     private void printTour(Map<Index, Integer> parent, int totalVertices) {
  100.         Set<Integer> set = new HashSet<>();
  101.         for(int i=0; i < totalVertices; i++) {
  102.             set.add(i);
  103.         }
  104.         Integer start = 0;
  105.         Deque<Integer> stack = new LinkedList<>();
  106.         while(true) {
  107.             stack.push(start);
  108.             set.remove(start);
  109.             start = parent.get(Index.createIndex(start, set));
  110.             if(start == null) {
  111.                 break;
  112.             }
  113.         }
  114.         StringJoiner joiner = new StringJoiner("->");
  115.         stack.forEach(v -> joiner.add(String.valueOf(v)));
  116.         System.out.println("\nTSP tour");
  117.         System.out.println(joiner.toString());
  118.     }
  119.  
  120.     private int getCost(Set<Integer> set, int prevVertex, Map<Index, Integer> minCostDP) {
  121.         set.remove(prevVertex);
  122.         Index index = Index.createIndex(prevVertex, set);
  123.         int cost = minCostDP.get(index);
  124.         set.add(prevVertex);
  125.         return cost;
  126.     }
  127.  
  128.     private List<Set<Integer>> generateCombination(int n) {
  129.         int input[] = new int[n];
  130.         for(int i = 0; i < input.length; i++) {
  131.             input[i] = i+1;
  132.         }
  133.         List<Set<Integer>> allSets = new ArrayList<>();
  134.         int result[] = new int[input.length];
  135.         generateCombination(input, 0, 0, allSets, result);
  136.         Collections.sort(allSets, new SetSizeComparator());
  137.         return allSets;
  138.     }
  139.  
  140.     private void generateCombination(int input[], int start, int pos, List<Set<Integer>> allSets, int result[]) {
  141.         if(pos == input.length) {
  142.             return;
  143.         }
  144.         Set<Integer> set = createSet(result, pos);
  145.         allSets.add(set);
  146.         for(int i=start; i < input.length; i++) {
  147.             result[pos] = input[i];
  148.             generateCombination(input, i+1, pos+1, allSets, result);
  149.         }
  150.     }
  151.  
  152.     private static Set<Integer> createSet(int input[], int pos) {
  153.         if(pos == 0) {
  154.             return new HashSet<>();
  155.         }
  156.         Set<Integer> set = new HashSet<>();
  157.         for(int i = 0; i < pos; i++) {
  158.             set.add(input[i]);
  159.         }
  160.         return set;
  161.     }
  162. }