Transcription of Chapter 10
{{id}} {{{paragraph}}}
Example: bankruptcy
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.
2.use MST-Prim (G, c, r) to compute a minimum spanning tree from r. 3.assume L to be the sequence of vertices visited in a preorder tree walk of T. 4.return the Hamiltonian cycle H that visits the vertices in the order L. The next set of figures show the working of the proposed algorithm. A B E C
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: