Maximizing Distance in the Travelling Salesman Problem: Is it Possible?

  • Thread starter sparsh12
  • Start date
In summary, the conversation is about the difference between finding the minimum and maximum distances in the Traveling Salesman Problem. The person asking the question is wondering if there is a way to find the maximum distance, but does not want to get into the complications of computers. The other person points out that it is essentially the same problem, just with inverted weights.
  • #1
sparsh12
12
0
I change the question completely. If i get an answer for this, my question would be resolved.

Everyone is obsessive of finding minimum distance in Travelling Salesman Problem, but my question is,

"Is there a way to find the maximum distance possible?"

I know it is related to theory of computation, but i don't want to get into complication of computers.
 
Physics news on Phys.org
  • #2
Hi, I don't know much about the TSP, but wonder in what way the problem of finding the maximum distance differs from that of finding the minimum.
 
  • #3
I don't think it changes it at all. It's the same exact thing. Just invert the weights.
 

1. What is the Travelling Salesman Problem?

The Travelling Salesman Problem (TSP) is a well-known mathematical problem that involves finding the shortest possible route that visits a given set of cities and returns to the starting city. It is a classic example of a NP-hard problem, meaning that as the number of cities increases, the time and computational power required to solve the problem also increases exponentially.

2. What are the real-world applications of the Travelling Salesman Problem?

The TSP has many real-world applications, including route planning for delivery services, circuit board manufacturing, and DNA sequencing. It can also be applied to scheduling problems, such as scheduling airline routes or organizing a salesperson's itinerary.

3. How is the Travelling Salesman Problem solved?

There are several approaches to solving the TSP, including exact algorithms, heuristic algorithms, and metaheuristic algorithms. Exact algorithms guarantee the optimal solution but can be computationally intensive. Heuristic algorithms, such as the nearest neighbor algorithm, provide good solutions but do not guarantee optimality. Metaheuristic algorithms, such as simulated annealing and genetic algorithms, combine elements of both exact and heuristic approaches to find near-optimal solutions in a reasonable amount of time.

4. What are some limitations of the Travelling Salesman Problem?

The TSP is a complex problem that is difficult to solve for large numbers of cities. As the number of cities increases, the number of possible routes also increases exponentially, making it increasingly difficult to find the optimal solution. Additionally, the TSP does not take into account real-world factors such as traffic, road closures, or weather, which can impact the actual shortest route between cities.

5. Are there any practical solutions to the Travelling Salesman Problem?

While finding the optimal solution to the TSP is not always feasible in practical applications, there are many approximate solutions that can provide good results. Additionally, advancements in computer technology and algorithms have made it possible to solve larger TSP instances than ever before. Some real-world applications may also use a combination of algorithms and human decision-making to find efficient routes for travelling salespeople or delivery services.

Similar threads

Formulation of a linear programming model
    • Linear and Abstract Algebra
Replies
1
Views
3K
I Need help understanding Commuting Operators
    • Linear and Abstract Algebra
Replies
6
Views
1K
Distance traveled by a Ball affected by friction after t seconds
    • Introductory Physics Homework Help
Replies
4
Views
841
I The answer is 15! What is the problem?
    • General Math
Replies
1
Views
1K
Distance traveled by a particle in a transverse wave
    • Introductory Physics Homework Help
Replies
2
Views
2K
Physics 1 Parabolic Motion Question Confusion
    • Introductory Physics Homework Help
Replies
15
Views
492
A rolling ball, find distance traveled
    • Introductory Physics Homework Help
Replies
4
Views
1K
Calculate Distance Traveled: Instantaneous vs. Average Velocity
    • Introductory Physics Homework Help
Replies
5
Views
1K
Distance-time graph of a ball throw vertically up from a fixed point
    • Introductory Physics Homework Help
Replies
5
Views
272
I Is Teleportation & Time Travel Possible?
    • Special and General Relativity
Replies
17
Views
1K

Hot Threads

Recent Insights

Back
Top