Travelling salesman problem From Wikipedia, the free encyclopedia [LINK] [LINK] 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. Read the text and answer the Qs. a) What kind of 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. Description - As a graph problem [LINK] [LINK] 2. Fill in the missing words. The TSP can be modeled as a 1)……….., such that cities are the graph’s2) ……………, paths are the graph’s3) ………….., and a path's distance is the edge's length. A TSP tour becomes a4) ……………….., and the optimal TSP tour is the shortest Hamiltonian cycle. Often, the model is a 5) ………………(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) …………... With metric distances 3. 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 of 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) The drilling machine in maximum metric moves slowly to the next hole. 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. 4. Have a look at the picture and try to solve the problem. Problem: Find the cycle of minimum cost visiting all of the vertices of G exactly once. traveling-salesman-L Shortest Paths I: Properties, Dijkstra's Algorithm http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algor ithms-sma-5503-fall-2005/video-lectures/lecture-17-shortest-paths-i-properties-dijkstras-algorithm- breadth-first-search/ Pre-listening 1) What do you know about the shortest path problem? 2) What is a graph composed of? 3) What kinds of graphs do you know? Listening. Listen to and watch the lecture and answer questions. 1) Why did the lecturer mention the Star Wars? ………………………………………………………………………………………… 2) Why did the lecturer mention the dynamic programming? ……………………………………………………………………………………….. 3) Why did he mention Alderon and Cambridge? ……………………………………………………………………………………….. 4) What is directed graph? ………………………………………………………………………………………. 5) What is edge weight? ……………………………………………………………………………………….. 6) How do we denote paths? ……………………………………………………………………………………….. 7) What is directed path? ………………………………………………………………………………………. 8) What is the weight of a path? ……………………………………………………………………………………….. 9) What is the property of a simple graph? ………………………………………………………………………………………… 10) How can you find the shortest path from u to v? Body language (adapted from Effective Presentations by Jeremy Comfort and Derek Utley, 2000, and materials designed by Hana Němcová.) a) Watch the video and make notes on the presenter’s body language. Complete the checklist. Posture version 1 version 2 Hands – position Hands – gestures Eye contact Facial expression Movement b) Language focus – emphasizing and minimizing Emphasizing Minimizing Strong adverbs intensity adjectives: Look at the way the following expressions We’ve had an extremely good year. of degree and uncertainty modify or minimize the message. Adverbs can be total, very strong, or moderate. It seems we will have to delay the delivery. He appears to have left the country. TOTAL It is just a little bit more complicated. absolutely (fantastic) Perhaps we should consider other options. completely (awful) There might be another way to solve this. entirely (depressing) I tend to think we should investigate this. To some extent, this might be plausible. VERY STRONG extremely (good) very (bad) MODERATE fairly (safe) reasonably (expensive) quite (cheap) c) Add an adverb to these sentences to emphasize the message. 1. This has been a good year. (very strong) 2. We have had a difficult time. (moderate) 3. We have seen a disastrous decline in our performance. (total) 4. It was easy to achieve our objectives. (moderate) 5. The announcement was unexpected. (total) 6. I have got some bad news. (very strong) d) Hedging Language Source: http://www.uefap.com/writing/feature/hedge.htm An important feature of academic writing is the concept of cautious language, often called "hedging" or "vague language". In other words, it is necessary to make decisions about your stance on a particular subject, or the strength of the claims you are making. Introductory verbs: e.g. seem, tend, look like, appear to be, think, believe, doubt, be sure, indicate, suggest Certain lexical verbs: e.g. believe, assume, suggest Certain modal verbs: e.g. will, must, would, may, might, could Adverbs of frequency: e.g. often, sometimes, usually Modal adverbs: e.g. certainly, definitely, clearly, probably, possibly, perhaps, conceivably Modal adjectives: e.g. certain, definite, clear, probable, possible Modal nouns: e.g. assumption, possibility, probability That clauses e.g. It could be the case that . e.g. It might be suggested that . e.g. There is every hope that …. To-clause + adjective: e.g. It may be possible to obtain . e.g. It is important to develop . e.g. It is useful to study . Rewrite these sentences using hedging language. 1. Playing violent video games causes more aggression, bullying, and fighting 2. Mars is the focus of much scientific study and the foremost planet for human colonization. 3. News reports can never be trusted because of media bias, journalist interpretation and agenda setting. 4. The main concerns for the future generations are global food supplies and population growth. Both of these have to be addressed by international leaders within the next five years. 5. Most people think that Climate Change is caused by human activities. 6. The key factor of divorce is gender hierarchy and gender inequality. 7. The impact of the UK’s ageing population will lead to increased welfare costs. Consequently, this will result in higher taxes and an increased retirement age for younger people. 8.Everybody agrees that the main cause of the financial crash was subprime mortgage lending. Closing your speech. a) Which parts should be included in the final part of a presentation? Watch the video and try to identify these parts. 1. …………………………………… 2. …………………………………… 3. …………………………………….. 4. …………………………………….. b) The sentences a-e below are the end of a presentation, but they are in the wrong order. Put them into the right order. c) 1. So, I would be glad to answer any questions. 2. I sincerely hope you will all go away with a more complete picture of the principal activities of UNEXCO. 3. Very briefly, there are three. Firstly, fund-raising, secondly, publicity, and thirdly, political lobbying. 4. So, that brings me to the end of this presentation. 5. Finally, I would like to leave you with something which I heard recently: “You can’t please all the people all the time, but we should certainly be able to feed all the people all the time.” d) Make full sentences by matching the correct halves. a) Before we come to the end, 1. there are four major features. b) I‘d be glad to answer 2. we start the discussion now. c) To summarize, 3. by quoting a well-known saying. d) We can conclude 4. we should reduce our costs. e) In my opinion, 5. any questions now. f) I‘d like to suggest 6. I‘d like to thank you for your participation.