open All Channels
seplocked EVE General Discussion
blankseplocked Completed! Optimal Route Competition with Reward
 
This thread is older than 90 days and has been locked due to inactivity.


 
Pages: [1] 2

Author Topic

Neramore
Posted - 2009.08.20 17:44:00 - [1]
 

Edited by: Neramore on 03/09/2009 12:39:10
Edited by: Neramore on 02/09/2009 12:42:42
The competition: Find the optimal way to gather market information from every major high-sec trading region.

The reward: starts at 100 Million isk, goes up with donations

The question:
Assume you have four pilots (the alts of two different accounts).
What is the list of systems for each of those pilots to visit to gather market info on the following regions using only high-security systems - The Citadel, Derelik, Devoid, Domain, Essence, Everyshore, The Forge, Genesis, Heimatar, Kador, Khanid, Kor-Azor, Lonetrek, Metropolis, Sinq Laison, Tash-Murkon, Verge Vendor.

The Rules:
1. Reply with your route to this post.
2. Your route can only use high security systems.
3. Post the systems each pilot A, B, C and D must visit.
4. If your list covers more of the above 17 regions than the previous best, you are the new leader.
5. If your list covers the same number of regions than the previous best, but in fewer total jumps, you are the new leader.
6. The leader wins when no one improves on the current best for one week from the leader's posting.

The Reward:
I will put up 100 million isk for the reward. I will take donations to increase the reward. If you think having this information known to all is a good thing, and would like to increase the reward, please send a donation to me with the note "Optimal Route Competition". I will publicly thank you (or not, your choice) and add your donation to the reward. If the donations exceed 1 billion isk, I will find someone to act as an escrow.

Other Details:
I will update this post as frequently as I can with the current optimum, and the current end of the competition. Obviously the end of the competition will move depending on the most recent best routes.

An Example:
A: Ourapheh - Genesis, Botane - Sinq Laison, Atlangeins - Essence, Tolle - Everyshore
B: New Caldari - The Forge, Alikara - The Citadel, Vellaine - Lonetrek
C: Ryddinjorn - Metropolis, Odatrik - Heimatar, Jark - Derelik, Lisudeh - Devoid
D: Suner - Kador, Masanuh - Kor-Azor, Ervekam - Khanid, Onazel - Tash-Murkon, Bhizhea - Domain

This route covers 16 regions.

Neramore
Posted - 2009.08.20 17:45:00 - [2]
 

Edited by: Neramore on 27/08/2009 14:06:00
Current leader: Aluvysa
Competition ends: 2009.09.03 00:08:00

Babel
Utopian Research I.E.L.
Hedonistic Imperative
Posted - 2009.08.20 18:33:00 - [3]
 

A = Athinard - Chantrousse - Derrintel [Everyshore, Sinq, Genesis, Verge, Essence = 7 jumps] *also includes Verge compared to yours*

B = New Caldari - Alikara - Vellaine [Forge, Citadel, Lonetrek = 3 jumps, lots of variations on this] *same as your route*

C = Ryddinjorn - Lisudeh [Metro, Heimatar, Derelik, Devoid = 9 jumps, alternative start = Arlulf] *same as your route*

D = Molea - Bhizheba - Romi - Tash-Murkon Prime [Khanid, Kor-Azor, Domain, Kador, Tash-Murkon = 8 jumps] *shorter than your version*

Total = 27 jumps with the 4 characters, 17 regions covered ... :)
nb. links are to Dotlan routes.

Neramore
Posted - 2009.08.21 19:28:00 - [4]
 

Only six days left!

Neramore
Posted - 2009.08.23 11:10:00 - [5]
 

Four days left!

Chribba
Otherworld Enterprises
Otherworld Empire
Posted - 2009.08.23 11:13:00 - [6]
 

Will us normal peps get the result for our market alts too? Razz

Joe
Umbra Legion
Shadow Empire.
Posted - 2009.08.23 12:48:00 - [7]
 

Originally by: Neramore
The competition: Find the optimal way to gather market information from every major high-sec trading region.


http://www.eve-central.com/

Did i win? Very Happy


Neramore
Posted - 2009.08.23 16:49:00 - [8]
 

Originally by: Chribba
Will us normal peps get the result for our market alts too? Razz

Chribba? Normal? Riiiight.
The results are public, not sure what might be hidden here? We're just discussing where to place your alts and what systems to visit to see every major market most efficiently.

Neramore
Posted - 2009.08.23 16:50:00 - [9]
 

Originally by: Joe
Originally by: Neramore
The competition: Find the optimal way to gather market information from every major high-sec trading region.


http://www.eve-central.com/

Did i win? Very Happy



Since eve-central doesn't have every bit of info on every major market, no. :) Granted, it has a lot, but it's not everything, and it's only as up to date as folks are willing to share.

Professor Tarantula
Hedion University
Posted - 2009.08.23 17:06:00 - [10]
 

Edited by: Professor Tarantula on 23/08/2009 17:06:29
Rens is the spot for the Heimatar region.

It's also commonly accepted that people in Rens and Abudban are naturally cooler and sexier than the people of other systems.

Neramore
Posted - 2009.08.25 19:08:00 - [11]
 

Only two days left! Easy isk, just spend some time with the map!

Fink Angel
Caldari
The Merry Men
Posted - 2009.08.25 19:14:00 - [12]
 

Edited by: Fink Angel on 25/08/2009 19:18:17
Aha, this is known as the Travelling Salesman Problem, or also "NP Complete".

http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://en.wikipedia.org/wiki/NP-complete

Good luck, there's no simple computational solution.

Edit: see here too:

"One experience from dealing with the Travelling Salesman's Problem is that our eyes easily discovers the flaws of different solutions. Something just "feels wrong". But it can be very difficult to put the feeling into words, not to talk about defining it in terms that can be used as an algorithm.

Isadora Duncan once was asked to tell what her dance was about. She answered - "if I could tell it, I wouldn't have to dance it"."

http://web.telia.com/~u85905224/tsp/TSP.htm

B1FF
Posted - 2009.08.25 20:12:00 - [13]
 

Originally by: Fink Angel
Edited by: Fink Angel on 25/08/2009 19:18:17
Aha, this is known as the Travelling Salesman Problem, or also "NP Complete".

http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://en.wikipedia.org/wiki/NP-complete

Good luck, there's no simple computational solution.

Edit: see here too:

"One experience from dealing with the Travelling Salesman's Problem is that our eyes easily discovers the flaws of different solutions. Something just "feels wrong". But it can be very difficult to put the feeling into words, not to talk about defining it in terms that can be used as an algorithm.

Isadora Duncan once was asked to tell what her dance was about. She answered - "if I could tell it, I wouldn't have to dance it"."

http://web.telia.com/~u85905224/tsp/TSP.htm


Not quite as the OP doesn't care about distances just the number of jumps.

This makes it trivial to compute.

Fink Angel
Caldari
The Merry Men
Posted - 2009.08.25 23:29:00 - [14]
 

Originally by: B1FF
Not quite as the OP doesn't care about distances just the number of jumps.

This makes it trivial to compute.


Should take into account the AUs of the warps too. That would properly optimise it, especially if you're slow-warping your freighter.

Taedrin
Gallente
Kushan Industrial
Posted - 2009.08.26 00:02:00 - [15]
 

Edited by: Taedrin on 26/08/2009 00:02:32
Originally by: B1FF
Originally by: Fink Angel
Edited by: Fink Angel on 25/08/2009 19:18:17
Aha, this is known as the Travelling Salesman Problem, or also "NP Complete".

http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://en.wikipedia.org/wiki/NP-complete

Good luck, there's no simple computational solution.

Edit: see here too:

"One experience from dealing with the Travelling Salesman's Problem is that our eyes easily discovers the flaws of different solutions. Something just "feels wrong". But it can be very difficult to put the feeling into words, not to talk about defining it in terms that can be used as an algorithm.

Isadora Duncan once was asked to tell what her dance was about. She answered - "if I could tell it, I wouldn't have to dance it"."

http://web.telia.com/~u85905224/tsp/TSP.htm


Not quite as the OP doesn't care about distances just the number of jumps.

This makes it trivial to compute.


The number of jumps IS the distance. This is a 17 point Traveling salesman problem, as you have to visit at least 17 points (regions) and attempt to find the shortest possible route while visiting all 17 points. This is NOT easily solved. The naive brute force method for solving this requires you to compare 355,687,428,096,000 different possible routes to find the best possible solution.


However, humans are surprisingly good at finding a "good enough" solution, hence the reason why the OP is bringing this to the forums.

Jennifer Celeste
Posted - 2009.08.26 00:24:00 - [16]
 

Originally by: Neramore
Edited by: Neramore on 25/08/2009 19:07:45

The competition: Find the optimal way to gather market information from every major high-sec trading region.

The reward: starts at 100 Million isk, goes up with donations

The question:
Assume you have four pilots (the alts of two different accounts).
What is the list of systems for each of those pilots to visit to gather market info on the following regions using only high-security systems - The Citadel, Derelik, Devoid, Domain, Essence, Everyshore, The Forge, Genesis, Heimatar, Kador, Khanid, Kor-Azor, Lonetrek, Metropolis, Sinq Laison, Tash-Murkon, Verge Vendor.

The Rules:
1. Reply with your route to this post.
2. Your route can only use high security systems.
3. Post the systems each pilot A, B, C and D must visit.
4. If your list covers more of the above 17 regions than the previous best, you are the new leader.
5. If your list covers the same number of regions than the previous best, but in fewer total jumps, you are the new leader.
6. The leader wins when no one improves on the current best for one week from the leader's posting.

The Reward:
I will put up 100 million isk for the reward. I will take donations to increase the reward. If you think having this information known to all is a good thing, and would like to increase the reward, please send a donation to me with the note "Optimal Route Competition". I will publicly thank you (or not, your choice) and add your donation to the reward. If the donations exceed 1 billion isk, I will find someone to act as an escrow.

Other Details:
I will update this post as frequently as I can with the current optimum, and the current end of the competition. Obviously the end of the competition will move depending on the most recent best routes.

An Example:
A: Ourapheh - Genesis, Botane - Sinq Laison, Atlangeins - Essence, Tolle - Everyshore
B: New Caldari - The Forge, Alikara - The Citadel, Vellaine - Lonetrek
C: Ryddinjorn - Metropolis, Odatrik - Heimatar, Jark - Derelik, Lisudeh - Devoid
D: Suner - Kador, Masanuh - Kor-Azor, Ervekam - Khanid, Onazel - Tash-Murkon, Bhizhea - Domain

This route covers 16 regions.


translation: Hey guys im too lazy to plot a trade route, can you all do it for me?

R Ramjet
Immortal Council
Posted - 2009.08.26 00:40:00 - [17]
 

Originally by: Jennifer Celeste
translation: Hey guys, I earn enough isk nowadays to waste my time plotting a trade route, so I'm kindly offering to pay someone to do it for me.


There, fixed that for you.

B1FF
Posted - 2009.08.26 12:18:00 - [18]
 

Originally by: Taedrin
Edited by: Taedrin on 26/08/2009 00:02:32
Originally by: B1FF
Originally by: Fink Angel
Edited by: Fink Angel on 25/08/2009 19:18:17
Aha, this is known as the Travelling Salesman Problem, or also "NP Complete".

http://en.wikipedia.org/wiki/Travelling_salesman_problem
http://en.wikipedia.org/wiki/NP-complete

Good luck, there's no simple computational solution.

Edit: see here too:

"One experience from dealing with the Travelling Salesman's Problem is that our eyes easily discovers the flaws of different solutions. Something just "feels wrong". But it can be very difficult to put the feeling into words, not to talk about defining it in terms that can be used as an algorithm.

Isadora Duncan once was asked to tell what her dance was about. She answered - "if I could tell it, I wouldn't have to dance it"."

http://web.telia.com/~u85905224/tsp/TSP.htm


Not quite as the OP doesn't care about distances just the number of jumps.

This makes it trivial to compute.


The number of jumps IS the distance. This is a 17 point Traveling salesman problem, as you have to visit at least 17 points (regions) and attempt to find the shortest possible route while visiting all 17 points. This is NOT easily solved. The naive brute force method for solving this requires you to compare 355,687,428,096,000 different possible routes to find the best possible solution.


However, humans are surprisingly good at finding a "good enough" solution, hence the reason why the OP is bringing this to the forums.


Go read the link. Finding the shortest route between all nodes in a graph and all nodes in a graph with weighting is significantly different.

Your search space arguement is meaningless. Trivial has a distinct meaning in comp sci. It does not mean quick to solve. It means easy to solve.

The problem as layed out by the OP is identical to the maze navigation screen saver. It is not traveling salesman.

B1FF
Posted - 2009.08.26 12:18:00 - [19]
 

Originally by: Fink Angel
Originally by: B1FF
Not quite as the OP doesn't care about distances just the number of jumps.

This makes it trivial to compute.


Should take into account the AUs of the warps too. That would properly optimise it, especially if you're slow-warping your freighter.


In that case you would be right, but the OP doesn't so you're wrong.

Neramore
Posted - 2009.08.26 18:29:00 - [20]
 

It's amazing how many folks read this and think I'm asking for one route. I'm not. I'm asking for four routes that combined cover all 17 regions. Also amazing how much discussion about the type of problem it is, but not much actually addressing the problem.
And yes, this is absolutely a case of spending isk instead of time. One of the few examples in EVE where a noob can make a decent pile of isk with 0 skills whatsoever.
Ah well.
One day left!

Fink Angel
Caldari
The Merry Men
Posted - 2009.08.26 19:05:00 - [21]
 

Originally by: Neramore
Also amazing how much discussion about the type of problem it is, but not much actually addressing the problem.


It's a discussion forum, so I guess you'll have to live with it. Also, the discussion might have ended up helping your quest for an answer.

Gnulpie
Minmatar
Miner Tech
Posted - 2009.08.26 20:25:00 - [22]
 

Originally by: Neramore
Also amazing how much discussion about the type of problem it is, but not much actually addressing the problem.


That's how "scientists" are trained up these days.

They aren't trained any more to solve problems. They are trained to categorize problem, sort them into folders, tag them with labels, research the nature of the problem etc. But they aren't taught how to solve it.

Very typical for our days.

Aluvysa
Posted - 2009.08.27 00:08:00 - [23]
 

Kassigainen (Citadel) - Synchelle (Essence) - Pakhishi (Gensis) - Tar (Gen) - Merolles (Verge Vendor) - Tar (Gen) - Manarq (Gen) - Tolle (Everyshore) :: 7 Jumps, 5 Regions

Molea (Khanid) - Nakregde (Kor-Azor) - Kor-Azor Prime (K-A) - Amarr (Domain) - Bhizheba (Dom) - Tash-Murkon Prime (Tash-Murkon) - Bhizheba (Dom) - Romi (Kador) :: 7 Jumps, 5 Regions

Tunttaras (Lonetrek) - Niyabainen (The Forge) - Perimeter (For) - Ieyn-Oursta (Sinq Laison) :: 3 Jumps, 3 Regions

Lisudeh (Devoid) - Lashesih (Derelik) - Sasta (Der) - Jark (Der) - Odatrik (Heimatar) - Trytedald (Hem) - Ivar (Hem) - Ameinaka (Hem) - Arlulf (Metropolis) :: 8 Jumps, 4 Regions

17 Regions visited
25 Jumps Total

Neramore
Posted - 2009.08.27 14:11:00 - [24]
 

And in a near last minute entry, Aluvysa becomes the new leader, resetting the clock per rule 5 and 6! Double checked that route, and it all looks good.

To date there have been no isk donations, unfortunately.

If no one improves on Aluvysa's routes within one week of that post, she will be the new winner!

B1FF
Posted - 2009.08.27 16:44:00 - [25]
 

Originally by: Gnulpie
Originally by: Neramore
Also amazing how much discussion about the type of problem it is, but not much actually addressing the problem.


That's how "scientists" are trained up these days.

They aren't trained any more to solve problems. They are trained to categorize problem, sort them into folders, tag them with labels, research the nature of the problem etc. But they aren't taught how to solve it.

Very typical for our days.


How can you solve problem A if you think you're solving problem B and thus are using the tools needed for problem B?

Neramore
Posted - 2009.08.30 15:51:00 - [26]
 

Four days left. Just have to beat the best by one to win 100 Million Isk!

cyboman
Caldari
Caldari Provisions
Posted - 2009.08.31 15:00:00 - [27]
 

Originally by: Aluvysa
Kassigainen (Citadel) - Synchelle (Essence) - Pakhishi (Gensis) - Tar (Gen) - Merolles (Verge Vendor) - Tar (Gen) - Manarq (Gen) - Tolle (Everyshore) :: 7 Jumps, 5 Regions

Molea (Khanid) - Nakregde (Kor-Azor) - Kor-Azor Prime (K-A) - Amarr (Domain) - Bhizheba (Dom) - Tash-Murkon Prime (Tash-Murkon) - Bhizheba (Dom) - Romi (Kador) :: 7 Jumps, 5 Regions

Tunttaras (Lonetrek) - Niyabainen (The Forge) - Perimeter (For) - Ieyn-Oursta (Sinq Laison) :: 3 Jumps, 3 Regions

Lisudeh (Devoid) - Lashesih (Derelik) - Sasta (Der) - Jark (Der) - Odatrik (Heimatar) - Trytedald (Hem) - Ivar (Hem) - Ameinaka (Hem) - Arlulf (Metropolis) :: 8 Jumps, 4 Regions

17 Regions visited
25 Jumps Total



To imporve on the last set...

Lisudeh (Devoid) - Lashesih (Derelik) - Sasta (Der) - Jark (Der) - Odatrik (Heimatar) - Rens (Heimatar) - Ryddinjorn (Metropolis) :: 6 Jumps, 4 Regions

17 Regions visited
23 Jumps Total

Unless I missed something?

Neramore
Posted - 2009.09.01 15:45:00 - [28]
 

Originally by: cyboman

To imporve on the last set...

Lisudeh (Devoid) - Lashesih (Derelik) - Sasta (Der) - Jark (Der) - Odatrik (Heimatar) - Rens (Heimatar) - Ryddinjorn (Metropolis) :: 6 Jumps, 4 Regions

17 Regions visited
23 Jumps Total

Unless I missed something?


Sorry, can't go straight from Rens to Ryddinjorn. Please try again?

Neramore
Posted - 2009.09.02 12:44:00 - [29]
 

We're in the final hours for the competition, folks. Unless, of course, YOU find a better route and post it!

Neramore
Posted - 2009.09.03 12:40:00 - [30]
 

Congratulations to Aluvysa. She has won the competition, and the 100 million isk. This isk has been deposited in her account.
Thanks to all our participants!


Pages: [1] 2

This thread is older than 90 days and has been locked due to inactivity.


 


The new forums are live

Please adjust your bookmarks to https://forums.eveonline.com

These forums are archived and read-only