Re: Distance normalized TSP algorithm
Joshua Cranmer wrote:
JSH wrote:
> That's a more general assumption than what she made and sounds good
> intuitively but you haven't even begun to give any kind of proof.
>
> But it is a route to a counterexample to this idea: use two "traps"
> and prove that the algorithm as described cannot give an optimal
> path.
In working this out in my head, I realized there are two cases where the
algorithm will generate correct pathing for one of these traps (or you
could view it as one case): either the trap node has to be the start
position, or both walkers have to hit the entrance nodes at the same
time, i.e., the trap node is the halfway-point in the path.
....
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));
}
}
}