Explore BrainMass
Share

Explore BrainMass

    Algorithms Problem

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 ad1c9bdddf
    https://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