Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

PLZ HELP! Mathematics(TSP)!

Status
Not open for further replies.

ramone

Member level 3
Joined
Oct 5, 2003
Messages
58
Helped
1
Reputation
2
Reaction score
0
Trophy points
1,286
Location
Patras University
Activity points
721
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???
 

ramone

Member level 3
Joined
Oct 5, 2003
Messages
58
Helped
1
Reputation
2
Reaction score
0
Trophy points
1,286
Location
Patras University
Activity points
721
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

Full Member level 4
Joined
Jul 31, 2004
Messages
218
Helped
24
Reputation
48
Reaction score
3
Trophy points
1,298
Activity points
1,808
Hi.

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

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top