Reply to thread

Message

[QUOTE="Patricia Shanahan, post: 3598197"]
....

Here's another example, and a brute force program for finding the
minimum cost. In this case, to avoid arguments about distance, I'm
specifying only coordinates. The cost of each edge is the Java double
approximation to the Euclidean distance between the vertices.

To make everything as self-contained and simple as possible, I specify
the problem inside the program. Here's the definition for my latest example:

private static final double L = 2;
   private static final double M = 3;

private static final Node[] NODES = new Node[] {
       new Node("A", -L/2,M+L/2), new Node("B", L/2, M+L/2),
       new Node("C", M+L/2, L/2), new Node("D", M+L/2, -L/2),
       new Node("E", L/2, -M-L/2), new Node("F", -L/2, -M-L/2),
       new Node("G", -M-L/2, -L/2), new Node("H", -M-L/2, L/2),
       new Node("W", -L/2, L/2), new Node("X", L/2, L/2),
       new Node("Y", L/2, -L/2), new Node("Z", -L/2, -L/2)

};

W, X, Y, and Z are the corners of an L by L square. The remaining points
are corners of L by M rectangles attached to each edge of the square.

With L=2 and M=3 the results are:

Best Score 32.0000
Best Cycle: A W H G Z F E Y D C X B A

The rest of this message is a simple TSP solving program. Although the
12 vertex case only takes a few seconds, it is exponential time so I
don't recommend using it for much larger problems.

import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class BruteForce {
   /*
    * Problem definition.
    */
   private static final double L = 2;
   private static final double M = 3;

private static final Node[] NODES = new Node[] {
       new Node("A", -L/2,M+L/2), new Node("B", L/2, M+L/2),
       new Node("C", M+L/2, L/2), new Node("D", M+L/2, -L/2),
       new Node("E", L/2, -M-L/2), new Node("F", -L/2, -M-L/2),
       new Node("G", -M-L/2, -L/2), new Node("H", -M-L/2, L/2),
       new Node("W", -L/2, L/2), new Node("X", L/2, L/2),
       new Node("Y", L/2, -L/2), new Node("Z", -L/2, -L/2)

};

public static void main(String[] args) {
     BruteForce test = new BruteForce(NODES);
     long start = System.nanoTime();
     test.solve();
     long end = System.nanoTime();
     System.out.printf("Best Score %g%n", test.bestScore);
     System.out.print("Best Cycle:");
     for (Node n : test.bestCycle) {
       System.out.print(" "+n.getId());
     }
     System.out.println();
     System.out.printf("Elapsed time: %g seconds%n", (end-start)/1e9);
   }

private final Set<Node> nodes = new HashSet<Node>();

private double bestScore = Double.POSITIVE_INFINITY;

private Deque<Node> bestCycle;

private final Node startNode;

public BruteForce(Node[] nodes) {
     this.nodes.addAll(Arrays.asList(nodes));
     startNode = nodes[0];
   }

/**
    * Calculate bestScore and bestCycle.
    */
   private void solve() {
     /* Do special case handling for getting started with startNode as the
      * first and last node of the cycle.
      */
     nodes.remove(startNode);
     Deque<Node> prefix = new LinkedList<Node>();
     prefix.add(startNode);
     nodes.remove(startNode);
     solve(nodes, 0, prefix);
     nodes.add(startNode);
   }

/**
    * Calculate bestScore and bestCycle starting from a
    * specified prefix path.
    * @param available The set of nodes that are not in the prefix path
    * @param prefixScore The score for the prefix path
    * @param prefix The prefix path
    */
   private void solve(Set<Node> available,
       double prefixScore, Deque<Node> prefix) {
     if (available.isEmpty()) {
       /* Finished, the path is complete except for closing the cycle*/
       double score = prefixScore
           + prefix.getLast().distance(prefix.getFirst());
       if (score < bestScore) {
         /* This cycle is better than the best so far */
         bestCycle = new LinkedList<Node>();
         bestCycle.addAll(prefix);
         bestCycle.addLast(prefix.getFirst());
         bestScore = score;
       }
       return;
     }
     /* Need two copies of available set, one to provide an iterator
      * and another that can be temporarily modified without
      * disturbing the iterator.
      */
     Set<Node> workingAvailable = new HashSet<Node>(
         available);
     for (Node n : available) {
       double score = prefixScore + prefix.getLast().distance(n);
       if (score < bestScore) {
         /* There is a possibility that this path will lead to the best
          * cycle.
          */
         workingAvailable.remove(n);
         prefix.addLast(n);
         solve(workingAvailable, score, prefix);
         prefix.removeLast();
         workingAvailable.add(n);
       }
     }
   }
   static class Node {
     private String id;
     private double x;
     private double y;

/**
      * Create node.
      * @param id Identifier-like string labeling the node.
      * @param x X coordinate.
      * @param y Y coordinate.
      */
     Node(String id, double x, double y) {
       this.id = id;
       this.x = x;
       this.y = y;
     }

String getId() {
       return id;
     }

double distance(Node o) {
       double xDist = x - o.x;
       double yDist = y - o.y;
       return Math.sqrt((xDist * xDist + yDist * yDist));
     }
   }
}
[/QUOTE]

Verification