Kim woods only Please
precious_bratTutorial for getting started: This will really help you
Hello to All,
Welcome to our discussion area! :) This week we will be focusing on the Traveling Salesman problem or the TSP.
The traveling salesman problem is a FANTASTIC and very famous problem that has many applications to all sorts of different areas, such as shipping routes, planning a road trip, finding the shortest route when you look at google maps, and much more!
What is the basic idea behind this problem? We have an “n” number of destinations (cities, in this instance), which we call the vertices. “N” stands for a given number, in our case this number is 5.
Now, the goal of the TSP is to find the most efficient way to visit all cities exactly once (returning to our original starting point). Of course, the phrase “most efficient” is dependent on MANY factors, such as time, cost, deadlines, and many other considerations.
However: for simplicity, here let’s go ahead and focus on only two factors: time and money. Thus, we want to find the shortest route and the least expensive route. We will use the adage that time = money so in our case for simplicity we will assume that the shortest path is also the least expensive.
Now, let’s get a basic visual to get our minds running. For math problems, it REALLY helps to visualize!
A basic graph of the five cities could look something like this:
Source: http://homepages.ius.edu/rwisman/C455/html/notes/Chapter34/Chap34-3.htm
The circles in our graph are called vertices, and the lines are called edges.
The circles represent the cities, and the lines represent the distances between the cities.
(Note in the above graph not all possible distances have been displayed. For instance, we do not see a line from Vertex 1 to Vertex 4, but this is OK for our purposes).
In our graph, we are looking for something called a “Hamiltonian cycle.” This is a path that visits every vertex (circle) exactly one time and starts and ends at the same vertex.
Now, in the real world, where we would be analyzing many different factors, and not necessarily just time and money, this problem is actually quite complex! It requires complicated computer algorithms to solve and is often very time consuming.
However, for our assignment, we will solve this problem only by visual observation of a map.
Are you with me so far? If not, go ahead and re-read the above as many times as necessary. It’s OK if you have to re-read it four or five times for it to start to sink in – this is completely normal.
Then, come back to this point and let’s keep going!!
Next!! Please make sure that you read the textbook Chapter 4, Sections 1 through 3 on graph theory.
Then:
Let’s follow these steps to solve:
1. Name our cities and our starting/ending city:
· Orlando
· NYC
· Philadelphia
· Chicago
· Dallas
Our starting and ending city is Orlando.
2. Find the distance between all of our cities:
Pair of Cities |
Distance (rounded to the nearest whole mile) |
Orlando NYC |
938 |
Orlando Philly |
864 |
Orlando Chicago |
984 |
Orlando Dallas |
961 |
NYC Philly |
81 |
NYC Chicago |
711 |
NYC Dallas |
1370 |
Philly Chicago |
664 |
Philly Dallas |
1296 |
Chicago Dallas |
802 |
Hint: you can use this website to find the distance between your cities:
3. Let’s pin-point our cities on the map to get a good visual:
As we can see above, the cities I have chosen form a rough circle, so the shortest path would be to just trace the circle.
Now, just by visual inspection, I can see what is likely to be the shortest path:
Orlando Dallas Chicago NYC Philly Orlando
4. Let’s plug in the numbers!
Let’s go back to the chart of distances I created and plug in my numbers:
Orlando Dallas Chicago NYC Philly Orlando
961 802 711 81 864 = 3419 total miles
5. Let’s consider our answer!
Now, as we saw above, my method was a visual inspection of the graph and an educated guess. However, I speculate that in the top right corner of my map/graph, where Chicago, NYC and Philly are located, there might be variations to what order I would visit those cities so my initial guess may not be the best one. I might want to try a few different paths to see if my initial answer was correct.
Let’s try this path:
Orlando Dallas Chicago Philly NYC Orlando
961 802 664 81 938 = 3493 total miles
This number of miles is greater than my previous one, so I would be fairly certain that my initial answer is correct.
Now, it’s your turn! Go ahead and choose your five cities and follow the steps above to complete the assignment. You do NOT have to create/upload a graph (but you are welcome to if you would like), but in your answer for how you arrived at your conclusion for the best path, make sure to discuss the map you used and how you used it.