Jump to content

Help with EE Research question Traveling Salesman Problem


Alfredo Chavez

Recommended Posts

Hey guys!

I've been doing my Extended Essay about the Traveling Salesman Problem, but now I realize I'm not sure about my Research Question, and by the way, not even the subject (Math or Computer Science).

I wonder if you could give me some feedback on it.

My actual research question is: Proving the Traveling Salesman Problem is an NP-Complete problem.

I'm thinking about maybe changing it to see how a specific algorithm (the simplex one, by Dantzig) actually helped to solve large instances of the TSP.

Help, please, I'm lost.

Thank you in advance!

Link to post
Share on other sites

First off, it'll probably be best to have is as a CS EE. While it has some links to maths with graph theory and such, some things like complexity theory isn't. Besides, a lot of the theoretical aspects tend to be pretty complex, I wouldn't really recommend going into it unless you are really confident you can.

Just proving something isn't really enough though, you would have to go into more depth than that. Investigating and analyzing an algorithm would definitely work though, provided you can do it to a sufficient level of depth. I don't know too much about the subject myself, but it seems like there's two main types of algorithms to solve the problem - exact methods and approximations. That would give you something look analyse and judge for yourself, since an EE does require some personal contribution.

Link to post
Share on other sites

First off, it'll probably be best to have is as a CS EE. While it has some links to maths with graph theory and such, some things like complexity theory isn't. Besides, a lot of the theoretical aspects tend to be pretty complex, I wouldn't really recommend going into it unless you are really confident you can.

Just proving something isn't really enough though, you would have to go into more depth than that. Investigating and analyzing an algorithm would definitely work though, provided you can do it to a sufficient level of depth. I don't know too much about the subject myself, but it seems like there's two main types of algorithms to solve the problem - exact methods and approximations. That would give you something look analyse and judge for yourself, since an EE does require some personal contribution.

Thanks, I wasn't familiar at all with the topic, but after more than a year.of reading and studying I am proud to say I actually understand it. :D lol

Yeah, I believe I'm going to analyze the simplex algorithm, involving linear programming.

Thanks again

Link to post
Share on other sites

  • 8 years later...
On 9/14/2013 at 1:43 AM, Alfredo Chavez said:

Thanks, I wasn't familiar at all with the topic, but after more than a year.of reading and studying I am proud to say I actually understand it. :D lol

Yeah, I believe I'm going to analyze the simplex algorithm, involving linear programming.

Thanks again

hi im also trying to do my ee on a similar topic could u send it to me or if u used the DFJ formulation or anything similar could u send me that part. 

Link to post
Share on other sites

  • 4 months later...
On 9/14/2013 at 1:43 AM, Alfredo Chavez said:

Thanks, I wasn't familiar at all with the topic, but after more than a year.of reading and studying I am proud to say I actually understand it. :D lol

Yeah, I believe I'm going to analyze the simplex algorithm, involving linear programming.

Thanks again

Hi, will it be possible for you to guide me a bit on the mathematical computation and what all topics to use for it? 

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...