Menu
I studied TSP in college in the context of NP Completeness. I have never actually had a situation where it would apply to a practical problem. A little bit of research shows that it has been used to pick the cheapest path to move a drill around, that is making holes in circuit boards. That is pretty much all I could find.
Are you using it? What other practical applications does the TSA have?
924
The Brute Force approach, also known as the Naive Approach, calculates and compares all possible permutations of routes or paths to determine the shortest unique solution. To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes.
Scientists in Japan have solved a more complex traveling salesman problem than ever before. The previous standard for instant solving was 16 “cities,” and these scientists have used a new kind of processor to solve 22 cities. They say it would have taken a traditional von Neumann CPU 1,200 years to do the same task.
A traveler needs to visit all the cities from a list, where distances between all the cities are known and each city should be visited just once. What is the shortest possible route that he visits each city exactly once and returns to the origin city?
The salesman's goal is to keep both the travel costs and the distance traveled as low as possible. Focused on optimization, TSP is often used in computer science to find the most efficient route for data to travel between various nodes. Applications include identifying network or hardware optimization methods.
I was once given the task of writing a program to fill a rectangular area fairly uniformly with a "squiggle" - a curved line which doesn't self-intersect. My first attempt was to generate random points within the rectangle and try to find a tour of them (not necessarily the absolute shortest). Unfortunately this approach just didn't work very well and I abandoned it.
I did solve the problem in the end though:
My successful method was not related to the TSP but for the curious I will summarize it:
Start with a single line segment. Now loop: if a line is "too long", divide it in two. Move each point a bit at random, but make points repel each other. End the loop when little progress can be made. There are details but hopefully you get the idea.
Of course this produces an angular path (which would have been acceptable) but it is easy to turn the corners into smooth arcs.
And yes I did keep the code.
158
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
