# Algorithms Problem

Suppose that the vertices for an instance of the travelling salesman problem are points in a plan and that the cost c(u; v) is the Euclidean distance between points u and v. Show (i.e., prove) that an optimal tour never crosses itself.

© BrainMass Inc. brainmass.com October 10, 2019, 5:47 am ad1c9bdddfhttps://brainmass.com/computer-science/algorithms/algorithms-problem-517873

#### Solution Preview

Proof:

Suppose an optional solution of an TSP crosses itself as shown below, we can assume the solution starts from a point , then passes through points , then finally comes back to . The solution can ...

#### Solution Summary

Algorithm problems are examined.

$2.19