Angličtina pro matematiky IV
COURSE MATERIALS AND HOMEWORK XI.
Travelling salesman problem
From Wikipedia, the free encyclopedia
An optimal TSP tour through Germany’s 15 largest cities. It is the shortest among 43 589 145 600 possible tours visiting each city exactly once.
1. Prior to reading, try to discuss with your neighbour what TSP is.
(i.e. how can you use it, what are the applications, is it difficult to solve, who solved it
first, etc.)
2. Read the text and answer the Qs.
a) What kind of a problem TSP is?
b) What does it mean: it is used as a benchmark…
c) What are heuristic methods?
d) What are the applications of the TSP?
e) Which two basic concepts are there?
f) What makes the problem hard?
g) What are NP-complete problems?
h) What are CPU years?
The Travelling Salesman Problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.
The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.
The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.
In the theory of computational complexity, the decision version of TSP belongs to the class of NP-complete problems. Thus, it is assumed that there is no efficient algorithm for solving TSPs. In other words, it is likely that the worst case running time for any algorithm for TSP increases exponentially with the number of cities, so even some instances with only hundreds of cities will take many CPU years to solve exactly.
History
3. Read the part about the history of the TSP and indicate what these names, dates or expressions refer to.
a) 1832
b) Icosian Game
c) Vienna, Harvard
d) cutting plane method
e) 49
f) Richard M. Karp
g) Concorde
h) TSPLIB
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen from 1832 mentions the problem and includes example tours through Germany and Switzerland, but contains no mathematical treatment.
Mathematical problems related to the travelling salesman problem were treated in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman. Hamilton’s Icosian Game was a recreational puzzle based on finding a Hamiltonian cycle. The general form of the TSP appears to have been first studied by mathematicians during the 1930s in Vienna and at Harvard, notably by Karl Menger, who defines the problem, considers the obvious brute-force algorithm, and observes the non-optimality of the nearest neighbour heuristic:
We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.
Hassler Whitney at Princeton University introduced the name travelling salesman problem soon after.
In the 1950s and 1960s, the problem became increasingly popular in scientific circles in Europe and the USA. Notable contributions were made by George Dantzig, Delbert Ray Fulkerson and Selmer M. Johnson at the RAND Corporation in Santa Monica, who expressed the problem as an integer linear program and developed the cutting plane method for its solution. With these new methods they solved an instance with 49 cities to optimality by constructing a tour and proving that no other tour could be shorter. In the following decades, the problem was studied by many researchers from mathematics, computer science,chemistry, physics, and other sciences.
Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NP-complete, which implies the NP-hardness of TSP. This supplied a scientific explanation for the apparent computational difficulty of finding optimal tours.
Great progress was made in the late 1970s and 1980, when Grötschel, Padberg, Rinaldi and other managed to exactly solve instances with up to 2392 cities, using cutting planes and branch-and-bound.
In the 1990s, Applegate, Bixby, Chvátal, and Cook developed the program Concorde that has been used in many recent record solutions. Gerhard Reinelt published the TSPLIB in 1991, a collection of benchmark instances of varying difficulty, which has been used by many research groups for comparing results. In 2005, Cook and others computed an optimal tour through a 33,810-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are provably within 1% of optimal tour.
4. Reported speech. There is a quotation by Karl Menger. Indicate what he said.
a) Menger said that this problem ____________________ by each postman. b) The purpose of the messenger problem _________________________. c) He believed that the problem _____________________by many trials. d)He thought that the rule _____________________________the shortest route.
Description
As a graph problem
Symmetric TSP with four cities
5. Fill in the missing words.
The TSP can be modelled as a 1)……….., such that cities are the graph’s 2) ……………, paths are the graph’s 3) ………….., and a path's distance is the edge's length. A TSP tour becomes a Hamiltonian 4) …………., and the optimal TSP tour is the shortest Hamiltonian cycle. Often, the model is a 5) ………graph (i.e. an edge connects each pair of vertices). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal 6) …………...
6. Study the following paragraph and fill in the missing information.
a) The distances are the same in the symmetric TSP but the number of possible solutions
_______________________________________________________________________
b) The paths in the asymmetric TSP ___________________________________________
c) The symmetry can break down if ___________________________________________
Asymmetric and symmetric
In the symmetric TSP, the distance between two cities is the same in each direction, forming an undirected graph. This symmetry halves the number of possible solutions. In the asymmetric TSP, paths may not exist in both directions or the distances might be different, forming a directed graph. Traffic collisions, one-way streets, and airfares for cities with different departure and arrival fees are examples of how this symmetry could break down.
With metric distances
7. Read the next part and decide whether the statements are true or false.
a) The connection from A to B cannot be longer than the detour through C.
b) The Manhattan distance is the difference between x and y coordinates.
c) The edge length is defined by a metric on the set of vertices.
d) The city block metrics is a rectilinear TSP.
e) In the example with the drilling machine in maximum metric adjusting is slower than moving.
In the metric TSP the intercity distances satisfy the triangle inequality. This can be understood as “no shortcuts”, in the sense that the direct connection from A to B is never longer than the detour via C.
These edge lengths define a metric on the set of vertices. When the cities are viewed as points in the plane, many natural distance functions are metrics.
- In the Euclidian TSP the distance between two cities is the Euclidean distance between the corresponding points.
- In the Rectilinear TSP the distance between two cities is the sum of the differences of their x- and y-coordinates. This metric is often called the Manhattan distance or city-block metric.
- In the maximum metric, the distance between two points is the maximum of the differences of their x- and y-coordinates.
The last two metrics appear for example in routing a machine that drills a given set of holes in a printed circuit board. The Manhattan metric corresponds to a machine that adjusts first one co-ordinate, and then the other, so the time to move to a new point is the sum of both movements. The maximum metric corresponds to a machine that adjusts both co-ordinates simultaneously, so the time to move to a new point is the slower of the two movements.
Transcript - Lecture 4
OK. Today we are going to talk about a very interesting algorithm called Quicksort -- -- which was invented by Tony Hoare in 1962. And it has ended up being a really interesting algorithm from many points of view. And because of that, it turns out today's lecture is going to be both hard and fast. If you see the person next to you sleeping, you will want to say let's get going. It's a divide-and-conquer algorithm.
And it sorts, as they say, in place, meaning that it just rearranged the elements where they are. That is like insertion sort rearranges elements where they are. Mergesort does not. Mergesort requires extra storage in order to do the merge operation. To merge in linear time and place, it doesn't merge in place in linear time. It doesn't do it just by rearranging. It is nice because it is in place, so that means that it is fairly efficient in its use of storage. And it also happens to be very practical if you tune it a bit. The basic algorithm turns out, if you just implement that, it's not necessarily that efficient.
But if what you do was then do the standard kinds of things you do to goose up the runtime of something, and we'll talk a little about what those things are, then it can be very, very practical. So, it uses divide-and-conquer paradigm. First step is divide. And to do this basically it does it by partitioning. So, it partitions the input array into two subarrays around an element we call the pivot --
-- such that elements in the lower subarray are less than or equal to x, are less than or equal to elements in the upper subarray. If we draw a picture of the input array, this partition step basically takes some element x and everything over here is less than or equal to x after the partition step and everything over here is greater than or equal to x. And so now the conquer step is pretty easy.
You just recursively sort the two subarrays. So, I recursively sort the elements less than or equal to x, I recursively sort the elements greater than or equal to x. And then combine is then just trivial. Because once I have sorted the things less than or equal to x, then sorted the things greater than or equal to x, the whole thing is sorted. So, there is nothing to do really for the combine. The key step in quicksort is this partition step. That is the thing that does all of the work. And so you can view quicksort of just as recursive partitioning. That's all it is.
Transcript - Lecture 4
Decide whether the statements are true or false.
- This lecture is going to be very demanding.
- Quicksort and insertion sort keep elements in place.
- Merge sort does not rearrange elements.
- Quicksort is practical if you alter it slightly.
- Pivot is the central point around which subarrays are arranged.
- There are more elements in the lower subarray than in the upper subarray.
- Combine is a difficult step to do.
- Quicksort is based on partitioning.
Listen again and fill in the missing words.
OK. Today we are going to talk about a very interesting algorithm called Quicksort -- -- which was invented by Tony Hoare in 1962. And it has ………………. being a really interesting algorithm from many points of view. And because of that, it turns out today's lecture is going to be both ……. and fast. If you see the person next to you sleeping, you will want to say let's get going. It's a divide-and-conquer algorithm.
And it sorts, as they say, in place, meaning that it just rearranged the elements where they are. That is like insertion sort rearranges elements where they are. Mergesort does not. Mergesort requires extra ………… in order to do the merge operation. To merge in linear time and place, it doesn't merge in place in linear time. It doesn't do it just by rearranging. It is nice because it is in place, so that means that it is fairly ……………. in its use of storage. And it also happens to be very practical if you tune it a bit. The basic algorithm turns out, if you just implement that, it's not necessarily that efficient.
But if what you do was then do the standard kinds of things you do to goose up the ……………….. of something, and we'll talk a little about what those things are, then it can be very, very practical. So, it uses divide-and-conquer paradigm. First step is divide. And to do this basically it does it by partitioning. So, it partitions the ………………… array into two subarrays around an element we call the pivot --
-- such that elements in the lower subarray are less than or equal to x, are less than or equal to elements in the upper subarray. If we draw a picture of the input array, this partition step …………….. takes some element x and everything over here is less than or equal to x after the partition step and everything over here is greater than or equal to x. And so now the …………… step is pretty easy.
You just recursively sort the two subarrays. So, I recursively sort the elements less than or equal to x, I recursively sort the elements greater than or equal to x. And then combine is then just trivial. Because once I have …………….. the things less than or equal to x, then sorted the things greater than or equal to x, the whole thing is sorted. So, there is nothing to do really for the combine. The key step in …………………. is this partition step. That is the thing that does all of the work. And so you can view quicksort of just as recursive partitioning. That's all it is.