Algorithmatic problem

[GiLtY]

I'm bored, so here's a problem (still trying to figure out the best way to solve this problem):

On a map dictated by x-y coordinates stations are randomly placed on the map, and you are a train operator that drives the train. At the beginning of every travel you are starting at a different station (picked at random); however, you have the knowledge of the x-y coordinates of all the stations. The problem is to go through all of the train stations once and once only, but you have to pick out a route that provides the shortest total travel distance.

Have fun with the problem 🙂

--GiLtY

 

[Barnaby W. Füi]

Puzzles suck. :|

 

[Yossarian]

could you be more vague?

 

[GiLtY]

Originally posted by: BingBongWongFooey
Puzzles suck. :|

Hope I don't keep you up all night 😛

--GiLtY

 

[AFB]

Fvck, I'm going to bed. I forgot what the first part was by the time I was finished reading.

 

[TuxDave]

Ok... I'm done.. now what.

 

[GiLtY]

Originally posted by: Yossarian
could you be more vague?

What, do you want to know if you can take a restroom break in between?

--GiLtY

 

[KingNothing]

Djikstra's algorithm would solve that. What do I win?

 

[gopunk]

Originally posted by: KingNothing
Djikstra's algorithm would solve that. What do I win?

dijkstra's is shortest path from one vertex to another, this is the TSP... np complete

 

[mobobuff]

To the Highly Technical forum with you.

Our tired brains = not compute.

But this does remind me of the time when I couldn't stop trying to figure out which type of mowing pattern would take the least amount of time to finish the yard.

 

[dfi]

I didn't give this a lot of thought so I'm probably missing something, but the obvious answer is just to always go to the station closest to your current station, barring any station you've already been to.

Or, let a computer solve it.

dfi

 

[rgwalt]

This is the traveling salesman optimization problem, and is a tough cookie.

R

 

[Goosemaster]

...pick out a route that provides the shortest total travel distance

travel to and buy a ticket on the closest bankrupt airline you can find

 

[OulOat]

This is a special case the Hamiliton graph cycles, and Hamiltion is NP-hard. Thus, by reduction, TSP is NP-hard.

Where is my cookie?

 

[OulOat]

Originally posted by: dfi
I didn't give this a lot of thought so I'm probably missing something, but the obvious answer is just to always go to the station closest to your current station, barring any station you've already been to.

Or, let a computer solve it.

dfi

Greedy algorithms won't work.

IE.
A to B = 4
B to C = 10
C to D = 5
A to D = 1
B to D = 6

Using your method, starting at A, you go to D then C and lasty B, summing to 16. An obvious shorter path is 15, A to B then D ending at C.

 

[Nato595]

Being that we are in the year 2004, I would key all the coords into my Navi/GPS system (sorting by shortest distance) and follow the on-screen routing!

 

[memo]

i would throw a Kruskal's at this sucka. 🙂

 

[Ameesh]

depending on how many nodes there are i would probably brute force it using some recursive algorithm starting from every point to return a list of routes given the starting point. at least thats the easiest way I can solve your problem.

 

[Argo]

Brute force method. Just compute all the possibilities and select the shortest. Until somebody comes with a better method I'm the winnah.

 

[eigen]

np-complete , no cookie for you. Stop getting problems out of your textbooks😀 and posting them here.

Oh this could b "solved" using DNA computing as well.


Edit: On a side note I will start doing research next semester on combinatorial optimaztion.So I will post the answer in a few months:laugh:

 

[bleeb]

There are other more efficient methods than the Brute Force Method... You can try giving each node a weight and based on that come up with an algorithm... (don't remember the names off the top of my head)

 

[jman19]

Originally posted by: Argo
Brute force method. Just compute all the possibilities and select the shortest. Until somebody comes with a better method I'm the winnah.

Yeah, as long as there aren't too many nodes, a brute force algo would be fine really. There's no "easy" way to solve this AFAIK.

 

[Ameesh]

Originally posted by: Argo
Brute force method. Just compute all the possibilities and select the shortest. Until somebody comes with a better method I'm the winnah.

i beat you by 2 minutes woman! im the winnar!

 

[MeanMeosh]

traveling salesman problem, optimize for minimum distance.

yay for operations research models!

 

[jman19]

Originally posted by: bleeb
There are other more efficient methods than the Brute Force Method... You can try giving each node a weight and based on that come up with an algorithm... (don't remember the names off the top of my head)

If you remember the names of any of these post them here. Is there a way to try weights, and then based on some results, figure out how to properly readjust them to "move" towards the solution?