fork download 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Java Implementation for Unit 4 Assignment Activity (TSP with DP).
  5.  *
  6.  * This file includes:
  7.  * 1) Held–Karp Dynamic Programming solution for TSP (exact, exponential).
  8.  * 2) Brute-force permutation baseline (exact, factorial) for comparison on small n.
  9.  * 3) A test driver that runs instances from n = 5 to 15, reports timing, and prints tours.
  10.  *
  11.  * Notes for the assignment:
  12.  * - Start city is fixed at index 0.
  13.  * - Distances are generated as a reproducible symmetric matrix using a fixed seed.
  14.  * - DP runs for n = 5..15 (as required).
  15.  * - Brute force runs only up to a safe limit (default 10) to avoid excessive runtime.
  16.  */
  17. public class Main {
  18.  
  19.     /**
  20.      * Result container: minimum cost and the full tour (0 -> ... -> 0).
  21.      */
  22.     public static class Result {
  23.         public final double minCost;
  24.         public final List<Integer> tour;
  25.  
  26.         public Result(double minCost, List<Integer> tour) {
  27.             this.minCost = minCost;
  28.             this.tour = tour;
  29.         }
  30.     }
  31.  
  32.     // ============================================================
  33.     // Part 1: Held–Karp Dynamic Programming (Exact)
  34.     // ============================================================
  35.  
  36.     /**
  37.      * Solves TSP using Held–Karp DP.
  38.      *
  39.      * dp[mask][i] = minimum cost to start at 0, visit exactly the cities in "mask",
  40.      * and end at city i.
  41.      *
  42.      * Time Complexity:  O(n^2 * 2^n)
  43.      * Space Complexity: O(n * 2^n)
  44.      *
  45.      * @param dist distance matrix dist[i][j]. Can be symmetric or asymmetric.
  46.      * @return Result containing min tour cost and the reconstructed tour.
  47.      */
  48.     public static Result solveDP(double[][] dist) {
  49.         int n = dist.length;
  50.  
  51.         // Edge case: n=1 => tour is 0 -> 0 with cost 0.
  52.         if (n == 1) {
  53.             return new Result(0.0, Arrays.asList(0, 0));
  54.         }
  55.  
  56.         int ALL = (1 << n) - 1;
  57.  
  58.         // dp[mask][i] best cost to reach i after visiting mask.
  59.         double[][] dp = new double[1 << n][n];
  60.  
  61.         // parent[mask][i] stores the predecessor city that leads to best dp[mask][i].
  62.         int[][] parent = new int[1 << n][n];
  63.  
  64.         // Initialize DP table.
  65.         for (int mask = 0; mask <= ALL; mask++) {
  66.             Arrays.fill(dp[mask], Double.POSITIVE_INFINITY);
  67.             Arrays.fill(parent[mask], -1);
  68.         }
  69.  
  70.         // Base case: only city 0 visited, at city 0, cost = 0.
  71.         dp[1][0] = 0.0;
  72.  
  73.         // Build up solutions by expanding masks that include the start city.
  74.         for (int mask = 1; mask <= ALL; mask++) {
  75.             if ((mask & 1) == 0) continue; // must include city 0
  76.  
  77.             for (int i = 0; i < n; i++) {
  78.                 if ((mask & (1 << i)) == 0) continue; // i not in mask
  79.                 double currentCost = dp[mask][i];
  80.                 if (Double.isInfinite(currentCost)) continue;
  81.  
  82.                 // Try adding a new city k not yet visited.
  83.                 for (int k = 0; k < n; k++) {
  84.                     if ((mask & (1 << k)) != 0) continue; // already visited
  85.                     int nextMask = mask | (1 << k);
  86.                     double nextCost = currentCost + dist[i][k];
  87.  
  88.                     if (nextCost < dp[nextMask][k]) {
  89.                         dp[nextMask][k] = nextCost;
  90.                         parent[nextMask][k] = i;
  91.                     }
  92.                 }
  93.             }
  94.         }
  95.  
  96.         // Close the tour: return to city 0 from the best last city.
  97.         double bestCost = Double.POSITIVE_INFINITY;
  98.         int bestLast = -1;
  99.  
  100.         for (int i = 1; i < n; i++) {
  101.             double cost = dp[ALL][i] + dist[i][0];
  102.             if (cost < bestCost) {
  103.                 bestCost = cost;
  104.                 bestLast = i;
  105.             }
  106.         }
  107.  
  108.         if (Double.isInfinite(bestCost)) {
  109.             // No feasible tour (e.g., disconnected matrix).
  110.             return new Result(Double.POSITIVE_INFINITY, Collections.emptyList());
  111.         }
  112.  
  113.         // Reconstruct the path from parent pointers: state (ALL, bestLast).
  114.         List<Integer> reversed = new ArrayList<>();
  115.         int mask = ALL;
  116.         int cur = bestLast;
  117.  
  118.         reversed.add(cur);
  119.         while (cur != 0) {
  120.             int prev = parent[mask][cur];
  121.             mask = mask ^ (1 << cur); // remove cur from mask
  122.             cur = prev;
  123.             reversed.add(cur);
  124.         }
  125.  
  126.         Collections.reverse(reversed);
  127.         reversed.add(0); // return to start
  128.  
  129.         return new Result(bestCost, reversed);
  130.     }
  131.  
  132.     // ============================================================
  133.     // Part 2: Brute Force Permutations (Exact Baseline)
  134.     // ============================================================
  135.  
  136.     /**
  137.      * Brute-force TSP by enumerating all permutations of cities 1..n-1.
  138.      * This is used as a baseline for small n.
  139.      *
  140.      * Time Complexity:  O((n-1)! * n)
  141.      * Space Complexity: O(n)
  142.      *
  143.      * @param dist distance matrix dist[i][j]
  144.      * @return Result with exact minimum tour cost and tour
  145.      */
  146.     public static Result solveBruteForce(double[][] dist) {
  147.         int n = dist.length;
  148.  
  149.         if (n == 1) {
  150.             return new Result(0.0, Arrays.asList(0, 0));
  151.         }
  152.  
  153.         // Create the list of cities excluding the start city 0.
  154.         int[] cities = new int[n - 1];
  155.         for (int i = 0; i < n - 1; i++) {
  156.             cities[i] = i + 1;
  157.         }
  158.  
  159.         double best = Double.POSITIVE_INFINITY;
  160.         List<Integer> bestTour = Collections.emptyList();
  161.  
  162.         // Generate permutations in-place using Heap's algorithm or next-permutation.
  163.         // Here we use a simple recursive permutation generator for clarity.
  164.         permute(cities, 0, dist, new BestHolder());
  165.  
  166.         // The recursive method stores the best result in a static holder.
  167.         best = BestHolder.bestCost;
  168.         bestTour = BestHolder.bestTour;
  169.  
  170.         return new Result(best, bestTour);
  171.     }
  172.  
  173.     /**
  174.      * Helper class used by brute force to store the best cost/tour found so far.
  175.      * Static fields allow a clean interface for the recursive permute method.
  176.      */
  177.     private static class BestHolder {
  178.         static double bestCost = Double.POSITIVE_INFINITY;
  179.         static List<Integer> bestTour = Collections.emptyList();
  180.  
  181.         BestHolder() {
  182.             // Reset between calls
  183.             bestCost = Double.POSITIVE_INFINITY;
  184.             bestTour = Collections.emptyList();
  185.         }
  186.     }
  187.  
  188.     /**
  189.      * Recursive permutation of cities[] from index "pos" onward.
  190.      * For each full permutation, compute tour cost: 0 -> perm -> 0.
  191.      */
  192.     private static void permute(int[] cities, int pos, double[][] dist, BestHolder holder) {
  193.         int n = dist.length;
  194.  
  195.         if (pos == cities.length) {
  196.             // Evaluate tour for the current permutation.
  197.             double cost = 0.0;
  198.             int prev = 0;
  199.  
  200.             for (int city : cities) {
  201.                 cost += dist[prev][city];
  202.                 prev = city;
  203.             }
  204.             cost += dist[prev][0]; // return to start
  205.  
  206.             if (cost < BestHolder.bestCost) {
  207.                 BestHolder.bestCost = cost;
  208.  
  209.                 // Build the best tour list [0, perm..., 0].
  210.                 List<Integer> tour = new ArrayList<>();
  211.                 tour.add(0);
  212.                 for (int city : cities) tour.add(city);
  213.                 tour.add(0);
  214.                 BestHolder.bestTour = tour;
  215.             }
  216.             return;
  217.         }
  218.  
  219.         for (int i = pos; i < cities.length; i++) {
  220.             swap(cities, pos, i);
  221.             permute(cities, pos + 1, dist, holder);
  222.             swap(cities, pos, i); // backtrack
  223.         }
  224.     }
  225.  
  226.     private static void swap(int[] a, int i, int j) {
  227.         int t = a[i];
  228.         a[i] = a[j];
  229.         a[j] = t;
  230.     }
  231.  
  232.     public static void runNamedExample() {
  233.         String[] offices = {"Madrid", "Sevilla", "Valencia", "Bilbao", "Zaragoza"};
  234.  
  235.         // Symmetric example distances (km-like toy values)
  236.         double[][] dist = {
  237.             {0, 530, 360, 400, 320},
  238.             {530, 0, 650, 880, 800},
  239.             {360, 650, 0, 610, 310},
  240.             {400, 880, 610, 0, 300},
  241.             {320, 800, 310, 300, 0}
  242.         };
  243.  
  244.         Result dpRes = solveDP(dist);        
  245.         System.out.println("Example input (offices): " + Arrays.toString(offices));
  246.         printDistanceMatrix(offices, dist);
  247.         System.out.println("DP minimum cost: " + String.format("%.2f", dpRes.minCost));
  248.         System.out.println("DP tour (indices): " + dpRes.tour);
  249.         System.out.println("DP tour (names): " + tourToNames(dpRes.tour, offices));
  250.         System.out.println();
  251.  
  252.         Result bfRes = solveBruteForce(dist);
  253.         System.out.println("(Brute force shown for Q3 comparison)");
  254.         System.out.println("Brute force minimum cost: " + String.format("%.2f", bfRes.minCost));
  255.         System.out.println("Brute force tour (names): " + tourToNames(bfRes.tour, offices));
  256.         System.out.println();
  257.     }
  258.  
  259.     public static void printDistanceMatrix(String[] offices, double[][] dist) {
  260.         System.out.println("Distance matrix (dist[i][j]):");
  261.  
  262.         // Header row
  263.         System.out.printf("%12s", "");
  264.         for (String name : offices) {
  265.             System.out.printf("%12s", name);
  266.         }
  267.         System.out.println();
  268.  
  269.         // Each row i
  270.         for (int i = 0; i < offices.length; i++) {
  271.             System.out.printf("%12s", offices[i]);
  272.             for (int j = 0; j < offices.length; j++) {
  273.                 System.out.printf("%12.0f", dist[i][j]); // 0 decimals because our example uses integers
  274.             }
  275.             System.out.println();
  276.         }
  277.         System.out.println();
  278.     }
  279.  
  280.     // ============================================================
  281.     // Part 3: Test Driver (n = 5..15) + Timing
  282.     // ============================================================
  283.  
  284.     /**
  285.      * Generates a random symmetric distance matrix with integer weights in [minW, maxW].
  286.      * Fixed seed makes results reproducible for the report and screenshots.
  287.      */
  288.     public static double[][] randomSymmetricMatrix(int n, int minW, int maxW, long seed) {
  289.         Random rnd = new Random(seed);
  290.         double[][] dist = new double[n][n];
  291.  
  292.         for (int i = 0; i < n; i++) dist[i][i] = 0.0;
  293.  
  294.         for (int i = 0; i < n; i++) {
  295.             for (int j = i + 1; j < n; j++) {
  296.                 int w = minW + rnd.nextInt(maxW - minW + 1);
  297.                 dist[i][j] = w;
  298.                 dist[j][i] = w;
  299.             }
  300.         }
  301.         return dist;
  302.     }
  303.  
  304.     /**
  305.      * Measures the average runtime (ms) of DP over "repeats" runs.
  306.      * This reduces noise from JVM warm-up and short-duration timing.
  307.      */
  308.     public static double measureDPAvgMs(double[][] dist, int repeats) {
  309.         // Warm-up (helps JIT stabilize a little before timing)
  310.         solveDP(dist);
  311.  
  312.         long totalNs = 0L;
  313.         for (int r = 0; r < repeats; r++) {
  314.             long t0 = System.nanoTime();
  315.             solveDP(dist);
  316.             long t1 = System.nanoTime();
  317.             totalNs += (t1 - t0);
  318.         }
  319.         return (totalNs / (double) repeats) / 1_000_000.0;
  320.     }
  321.  
  322.     public static String tourToNames(List<Integer> tour, String[] offices) {
  323.         StringBuilder sb = new StringBuilder();
  324.         for (int i = 0; i < tour.size(); i++) {
  325.             sb.append(offices[tour.get(i)]);
  326.             if (i < tour.size() - 1) sb.append(" -> ");
  327.         }
  328.         return sb.toString();
  329.     }    
  330.  
  331.     /**
  332.      * Main: prints outputs explicitly mapped to the three assignment tasks.
  333.      * - Q1 (Task 1): Shows an explicit input (city names + distance matrix) and outputs the minimum tour.
  334.      * - Q2 (Task 2): Runs DP scalability tests for n = 5..15 (DP-only table).
  335.      * - Q3 (Task 3): Compares DP vs brute force for small n (separate comparison table).
  336.      */
  337.     public static void main(String[] args) {
  338.  
  339.         // =========================
  340.         // Q1 (Task 1): Explicit input
  341.         // =========================
  342.         System.out.println("====================================================================");
  343.         System.out.println("Q1 (Task 1): DP TSP on an explicit input (cities + distance matrix)");
  344.         System.out.println("====================================================================");
  345.         runNamedExample(); // includes cities + matrix + DP output (and BF note if you kept it)
  346.  
  347.         // Shared parameters
  348.         final int MIN_N = 5;
  349.         final int MAX_N = 15;
  350.  
  351.         final int BRUTE_FORCE_LIMIT = 10;
  352.         final int DP_REPEATS = 5;
  353.  
  354.         final int MIN_W = 1;
  355.         final int MAX_W = 100;
  356.         final long BASE_SEED = 12345L;
  357.  
  358.         // =========================
  359.         // Q2 (Task 2): DP scalability table (n=5..15)
  360.         // =========================
  361.         System.out.println("====================================================================");
  362.         System.out.println("Q2 (Task 2): Scalability test for DP (n = 5..15 offices)");
  363.         System.out.println("====================================================================");
  364.         System.out.println("Distances: random symmetric [1..100] generated with a fixed seed (reproducible).");
  365.         System.out.println("DP timing: average of " + DP_REPEATS + " runs (ms).");
  366.         System.out.println("--------------------------------------------------------------------");
  367.         System.out.printf("%-4s %-12s %-12s %-14s%n", "n", "DP_cost", "DP_time(ms)", "DP_tour_len");
  368.         System.out.println("--------------------------------------------------------------------");
  369.  
  370.         for (int n = MIN_N; n <= MAX_N; n++) {
  371.             double[][] dist = randomSymmetricMatrix(n, MIN_W, MAX_W, BASE_SEED + n);
  372.  
  373.             Result dpRes = solveDP(dist);
  374.             double dpMs = measureDPAvgMs(dist, DP_REPEATS);
  375.             int tourLen = dpRes.tour.size();
  376.  
  377.             System.out.printf("%-4d %-12.2f %-12.3f %-14d%n", n, dpRes.minCost, dpMs, tourLen);
  378.         }
  379.  
  380.         System.out.println("--------------------------------------------------------------------");
  381.         System.out.println();
  382.  
  383.         // =========================
  384.         // Q3 (Task 3): DP vs brute force (n=5..10)
  385.         // =========================
  386.         System.out.println("====================================================================");
  387.         System.out.println("Q3 (Task 3): DP vs brute-force comparison (n = 5.." + BRUTE_FORCE_LIMIT + ")");
  388.         System.out.println("====================================================================");
  389.         System.out.println("Note: Brute force is limited to n <= " + BRUTE_FORCE_LIMIT
  390.                 + " because the permutation approach grows factorially and becomes impractical.");
  391.         System.out.println("--------------------------------------------------------------------");
  392.         System.out.printf("%-4s %-12s %-12s %-12s %-12s %-10s%n",
  393.                 "n", "DP_cost", "DP_time(ms)", "BF_cost", "BF_time(ms)", "Match?");
  394.         System.out.println("--------------------------------------------------------------------");
  395.  
  396.         for (int n = MIN_N; n <= BRUTE_FORCE_LIMIT; n++) {
  397.             double[][] dist = randomSymmetricMatrix(n, MIN_W, MAX_W, BASE_SEED + n);
  398.  
  399.             // DP (single timed run here is OK; Q2 already did averaged timing)
  400.             long dpT0 = System.nanoTime();
  401.             Result dpRes = solveDP(dist);
  402.             long dpT1 = System.nanoTime();
  403.             double dpMs = (dpT1 - dpT0) / 1_000_000.0;
  404.  
  405.             // Brute force
  406.             long bfT0 = System.nanoTime();
  407.             Result bfRes = solveBruteForce(dist);
  408.             long bfT1 = System.nanoTime();
  409.             double bfMs = (bfT1 - bfT0) / 1_000_000.0;
  410.  
  411.             boolean match = Math.abs(dpRes.minCost - bfRes.minCost) <= 1e-9;
  412.  
  413.             System.out.printf("%-4d %-12.2f %-12.3f %-12.2f %-12.3f %-10s%n",
  414.                     n, dpRes.minCost, dpMs, bfRes.minCost, bfMs, match ? "YES" : "NO");
  415.         }
  416.  
  417.         System.out.println("--------------------------------------------------------------------");
  418.     }
  419. }
Success #stdin #stdout 0.55s 133496KB
comments (?)
stdin 
Standard input is empty
stdout 
====================================================================
Q1 (Task 1): DP TSP on an explicit input (cities + distance matrix)
====================================================================
Example input (offices): [Madrid, Sevilla, Valencia, Bilbao, Zaragoza]
Distance matrix (dist[i][j]):
                  Madrid     Sevilla    Valencia      Bilbao    Zaragoza
      Madrid           0         530         360         400         320
     Sevilla         530           0         650         880         800
    Valencia         360         650           0         610         310
      Bilbao         400         880         610           0         300
    Zaragoza         320         800         310         300           0

DP minimum cost: 2190.00
DP tour (indices): [0, 3, 4, 2, 1, 0]
DP tour (names): Madrid -> Bilbao -> Zaragoza -> Valencia -> Sevilla -> Madrid

(Brute force shown for Q3 comparison)
Brute force minimum cost: 2190.00
Brute force tour (names): Madrid -> Sevilla -> Valencia -> Zaragoza -> Bilbao -> Madrid

====================================================================
Q2 (Task 2): Scalability test for DP (n = 5..15 offices)
====================================================================
Distances: random symmetric [1..100] generated with a fixed seed (reproducible).
DP timing: average of 5 runs (ms).
--------------------------------------------------------------------
n    DP_cost      DP_time(ms)  DP_tour_len   
--------------------------------------------------------------------
5    218.00       0.148        6             
6    121.00       0.075        7             
7    166.00       0.199        8             
8    200.00       3.976        9             
9    256.00       13.627       10            
10   138.00       0.519        11            
11   158.00       0.577        12            
12   253.00       1.717        13            
13   182.00       2.819        14            
14   231.00       5.364        15            
15   287.00       16.294       16            
--------------------------------------------------------------------

====================================================================
Q3 (Task 3): DP vs brute-force comparison (n = 5..10)
====================================================================
Note: Brute force is limited to n <= 10 because the permutation approach grows factorially and becomes impractical.
--------------------------------------------------------------------
n    DP_cost      DP_time(ms)  BF_cost      BF_time(ms)  Match?    
--------------------------------------------------------------------
5    218.00       0.014        218.00       0.214        YES       
6    121.00       0.021        121.00       2.487        YES       
7    166.00       0.039        166.00       0.095        YES       
8    200.00       0.075        200.00       54.657       YES       
9    256.00       0.105        256.00       0.925        YES       
10   138.00       0.230        138.00       9.626        YES       
--------------------------------------------------------------------
https://ideone.com/BxiMON
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!