PLZ HELP! Mathematics(TSP)!

[ramone]

tsp maths formulation

Hi there! I'm working on some robotics and i use the Traveling Salesman Problem to make some paths. At the moment i'm trying to model this game:
the salesman starts from a city (say 1) and has n cities to travel but he has only T time units. Assuming that every travel between 2 cities is one time unit then which is the best path to take?

This means i have to reformulate the problem in some way. I have thought of a solution but how can i gurrante if it is the optimal or not? What maths to use???

 

[checkmate]

The TSP problem is a well-known NP hard problem. While the optimal path can be found in reasonable time for small N, this proves difficult for large N, where the search focuses on suboptimal paths.

Wikipedia has a list of possible algorithms.
https://en.wikipedia.org/wiki/Traveling_salesman_problem

 

[ramone]

Try reading again my post - you will understand what i want. If you want to test a heuristic (P time) for an NP problem you must first find an exact solution for the optimal problem. Since what i want starts from the TSP BUT IT ISN'T TSP i must first know if my formulation is the OPTIMAL or not (so to find another).

 

[yjkwon57]

Hi.

This topic belongs to a special kind of mathematics, called Graph Theory.