Transcription of Chapter 10
{{id}} {{{paragraph}}}
Example: confidence
Chapter 10
Chapter 10 The Traveling Salesman Problem Introduction The traveling salesman problem consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one ( the hometown) and returning to the same city. The challenge of the problem is that the traveling salesman wants to minimize the total length of the trip. The traveling salesman problem can be described as follows: TSP = {(G, f, t): G = (V, E) a complete graph, f is a function V V Z, t Z, G is a graph that contains a traveling salesman tour with cost that does not exceed t}. Example: Consider the following set of cities: 5 12 2 3 10 8 4 3 AEB DC Figure A graph with weights on its edges.
First, we create a minimum spanning tree the weight of which is a lower bound on the cost of an optimal traveling salesman tour. Using this minimum spanning tree we will create a tour the cost of which is at most 2 times the weight of the spanning tree. We present the algorithm that performs these computations using the MST-Prim algorithm.
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: