travelling salesman problem

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

Pohihihi - 30 Nov 2005 08:08 GMT

Hello All,

I am looking for VC++ implementation of travelling salesman problem. My
project designer wants it not to have with branch and bound algorithm or any
genetic/nural algorithm. Any pointers?

Thanks,
Po

Reply to this Message

Brian Muth - 30 Nov 2005 17:29 GMT

> I am looking for VC++ implementation of travelling salesman problem. My
> project designer wants it not to have with branch and bound algorithm or
> any
> genetic/nural algorithm. Any pointers?

project designer?

or teacher?

Brian

Reply to this Message

Pohihihi - 30 Nov 2005 20:30 GMT

It surely would have a school project 5 years back when I was in school but
for now it is a project for me. While posting first time I was assuming that
someone will surely take it as a school assignment. Can't complain cause I
would have taken it that way myself.

Anyways, so the usual implementation we see for this algorithm is via
branch&bound or some kind of genetic algorithm. Google is full of all those
implementation. Basically we are in a project that is related to hydroplant
optimization. Don't ask me how that work cause I am having a part in the
whole project. Our algorithm expert has some argument about not using
regular/populer (and easy) method. Now for me I have not implemented TSP
without B&B so I am very much like a student right now in knowing how to do
it.

All this said, now question is, can you help me?

Thanks,
Po

>> I am looking for VC++ implementation of travelling salesman problem. My
>> project designer wants it not to have with branch and bound algorithm or
[quoted text clipped - 6 lines]
>
> Brian

Reply to this Message

Peter Oliphant - 30 Nov 2005 21:14 GMT

Create a method to generate different paths deterministically from start
position to end position. Compute which one is best, and keep it. Generate
more paths. Compare against each other and the previous best one, and keep
best one again. Keep doing this until you 'time-out'. This will find a good
solution, but not guarantee a best solution (and note that it is very close
to, but not quite, a genetic algorithm. It is more a typical example of old
style heuristics).

If you need a best solution, plan on it taking 100's of years in many
non-trivial cases, the problem can be very intractable due to the enormous
number of non-linear paths (e.g., path A + Path B != Path (A+B))....hehe
THAT's why genetic algoritms are the typical way to go, which makes me
wonder why any project supervisor for a COMMERCIAL company would ever
restrict HOW you got a problem solved for the hell of it.

Are you sure you're not a student? : )

[==P==]

> It surely would have a school project 5 years back when I was in school
> but for now it is a project for me. While posting first time I was
[quoted text clipped - 25 lines]
>>
>> Brian

Reply to this Message

Pohihihi - 30 Nov 2005 21:44 GMT

I wish I was a student, my life would be much much easy (other than finding
a job and trying to meet ends).

> Create a method to generate different paths deterministically from start
> position to end position. Compute which one is best, and keep it. Generate
[quoted text clipped - 44 lines]
>>>
>>> Brian

Reply to this Message

Rate this thread:

travelling salesman problem

Free Magazines