What is the purpose of finding a lower bound in the Traveling Salesman Problem?

  • Thread starter Zurtex
  • Start date
In summary, during a maths lesson on the traveling salesman problem, the teacher explained the importance of finding both an upper and lower bound in order to estimate the optimal path through a maze. While finding a lower bound can be challenging, it is beneficial to have a larger lower bound for a more accurate estimate. Additionally, finding an exact solution can be very time-consuming, so it is important to find a clever and efficient way to estimate the optimal path. Knowing both the upper and lower bounds allows for a better understanding of how close one is to the optimal solution.
  • #1
Zurtex
Science Advisor
Homework Helper
1,120
1
At my maths class today we just started the final module of my further maths A level class. In the lesson we met the traveling salesman problem, I understand why it is such a difficult problem and I understand why we can easily work out an upper band and why it is useful.

However our teacher did not know why we had to work out a lower bound as surely a value smaller than this would be better.

If anyone could explain this too me I would be grateful.
 
Mathematics news on Phys.org
  • #2
The traveling salesman thing asks you to find the optimal path through the 'maze' if you will. It is important to find bounds on this, both upper and lower, so that you know roughly how long it wil take. Finding *an* upper bound is easy, as is finding a lower bound, but you would prefer to find the *largest* lower bound (and the smallest upper bound). Knowing a small bound less than some other lower bound doesn't help you anymore than knowing a bound bigger than the larger bound does.


I mean, would you rather know your test score was more than 70% or more than 10%? One clearly narrows the options down (for the better).


Just knowing the salesman travels more than 7 miles does imply he travels more than 5 miles, but knowing he travels more than 5 miles doesn't imply he travels more than 7 does it?



As it is finding the exact answer takes n! steps for n towns. If you can get a path that is at most in error by 20% say in n^2 steps you'd take it.


If you know replace you lower bound by something even smaller you decrease the effectiveness of this shortcut cos you increase the percentage error.

Is that sort of clear?
 
  • #3
So rather than a way of working out a shorter route it is more a way of decreasing the amount of workings required?
 
  • #4
It isn't that you're working out a shorter route (what can be shorter than the shortest), but that you are finding out that the shortest route is at least as big as something. Just knowing that the shortest route is at least x miles tells you what''s going on. The aim ought to be to find the shortest route. This is very hard and takes about n! calculations for n towns. This is the complexity of it. If you figure out a way to do it very quickly yo'ure on the way to a million dollars.

We can in theory work through every possible combination of routes, but that's very time consuming, what you try and do is pick some clever way of doing it that you know it gives you an error you can live with.

If I tell you that the optimum route takes between 10 and 20 miles is that better or worse than me saying it's between 16 and 17? The larger the lower bound the better (and the smaller the top bound), but it is only an estimate that gives you more knowledge, and allows you to know if you're getting closer to the optimum. What really counts is bounding it above, absolutely.
 
  • #5
Hmmm, I think I about get that thanks.
 

1. What is the Travelling Salesman Problem?

The Travelling Salesman Problem (TSP) is a classic optimization problem in computer science. It involves finding the shortest possible route that visits each of a given set of locations exactly once and returns to the starting location.

2. What makes the Travelling Salesman Problem difficult to solve?

The TSP is considered a difficult problem because it belongs to a class of problems known as NP-hard. This means that there is no known efficient algorithm for solving TSP for large inputs. As the number of locations increases, the number of possible routes grows exponentially, making it practically impossible to test all of them in a reasonable amount of time.

3. How is the Travelling Salesman Problem used in real life?

The TSP has practical applications in various fields, including logistics, transportation planning, and circuit board manufacturing. It can also be used to optimize delivery routes for packages, plan efficient road trips, and even optimize DNA sequencing.

4. Are there any approximate solutions for the Travelling Salesman Problem?

Yes, there are several approximate solutions for TSP that can provide a good enough solution in a reasonable amount of time. These include heuristic algorithms, such as the nearest neighbor algorithm and the genetic algorithm, as well as mathematical programming methods like the branch and bound algorithm.

5. Is there a single best solution to the Travelling Salesman Problem?

No, there is no single best solution to the TSP as it depends on the specific input and the chosen algorithm. However, for smaller instances of the problem, it is possible to calculate the optimal solution using exact methods, such as the mathematical programming approach. For larger instances, approximate solutions can provide a good enough solution.

Similar threads

  • General Math
Replies
4
Views
4K
  • STEM Educators and Teaching
Replies
3
Views
1K
  • STEM Academic Advising
Replies
5
Views
2K
Replies
4
Views
979
Replies
2
Views
1K
Replies
8
Views
2K
  • Other Physics Topics
Replies
2
Views
3K
Replies
11
Views
298
Replies
6
Views
945
  • STEM Academic Advising
Replies
1
Views
879
Back
Top