Transcription of Chapter 10
{{id}} {{{paragraph}}}
Example: biology
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.
A spanning tree is constructed by deleting edges from a tour. Thus, an optimal tour has more weight than the minimum-spanning tree, which means that the weight of the minimum spanning tree forms a lower bound on the weight of an optimal tour. c(t) ≤ c(H*). 10.2
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: