AA-A H! I hate the travelling salesman problem.

[Eahlstan]

I spent the last 17 days scanning every body in every AA-H system in sector EORD BLAO.

There was nothing interesting to be found, but that didn't stop me. What did stop me twice was a invisible nearly 3 million km wide ring around a neutron star orbiting a black hole facing the black hole, only one light source per system is definitely a bad idea.

If anyone knows why there no systems named H1 and H2 please tell me.


In total there were 386 AA-A H systems and the primary bodies were:

Black holes: 251
Wolf-Rayet O: 35
Class O: 35
Class B: 24
Blue-white super giants: 19
Wolf-Rayet WNC: 9
Wolf-Rayet C: 7
Wolf-Rayet N: 6

Only 31 systems were discovered so far, most of them by Bourbon014.

All bodies have been scanned and they are available at EDSM and EGO.

Here are some pictures showing the distribution of said systems (more space for bookmarks would be nice):

3-119:

120-239:

240-359:

360-388:

Pictures of all system maps can be found here: https://photos.app.goo.gl/m2TbCYjzzV2nWGxH6

 

[Numenor1379]

Ha! Bourbon is a friend of mine. We tend to make jokes about the number of Water Worlds he tags.

 

[Alkibiades]

Ha I am currently in the same situation. So many AA-A systems, so little bookmarks available

So far I have found one tagged wolf rayet in 5 systems. There is a lot yet to discover. 17 days is ... a bit massive. I hope I dont need that long.

The only one light source per system is realy annoying. I found an earth like less than 300ls from a main sequence star but its pitch black because the main star is a black hole.

 

[Eahlstan]

I hope I dont need that long.

Well 92000 light years and 2019 jumps take their time. Not to mention the time it takes to reach that single black hole 300.000 light seconds away.

The systems I spent the most time in was H383. 103 bodies and most of them 230.000 light seconds away.

 

[Redfox]

In total there were 386 AA-A H systems and the primary bodies were:

Black holes: 251
Wolf-Rayet O: 35
Class O: 35
Class B: 24
Blue-white super giants: 19
Wolf-Rayet WNC: 9
Wolf-Rayet C: 7
Wolf-Rayet N: 6

Only 31 systems were discovered so far, most of them by Bourbon014.

All bodies have been scanned and they are available at EDSM and EGO.

Nice, well done!

 

[Hanekura Shizuka]

+1 rep for mentioning Traveling Salesman problem! (Gee, you'd think the complexity of the problem was non-polynomial or something, the way you were talking.)

 

[BaldEagle]

I spent the last 17 days scanning every body in every AA-H system in sector EORD BLAO.

There was nothing interesting to be found, but that didn't stop me. What did stop me twice was a invisible nearly 3 million km wide ring around a neutron star orbiting a black hole facing the black hole, only one light source per system is definitely a bad idea.

If anyone knows why there no systems named H1 and H2 please tell me.


In total there were 386 AA-A H systems and the primary bodies were:

Black holes: 251
Wolf-Rayet O: 35
Class O: 35
Class B: 24
Blue-white super giants: 19
Wolf-Rayet WNC: 9
Wolf-Rayet C: 7
Wolf-Rayet N: 6

This is impressive, Commander. I feel so inadequate as my patience only lasts a few days and maybe 500 jumps.
Yes, we do need many more bookmarks; they always run out at just the wrong time (no patience again!).

 

[Shinji Ikari]

+1 rep for mentioning Traveling Salesman problem! (Gee, you'd think the complexity of the problem was non-polynomial or something, the way you were talking.)

NP?

 

[Dan Bender]

I’m trying to figure out what the traveling salesman has to do with the content of your post? Were you having trouble figuring out which systems you’d already visited?

 

[varonica]

I’m trying to figure out what the traveling salesman has to do with the content of your post? Were you having trouble figuring out which systems you’d already visited?

The travelling salesman doesn't, but the travelling salesman problem does have relevance;

https://en.wikipedia.org/wiki/Travelling_salesman_problem

It's basically how to calculate the shortest route that will intersect a given number of randomly placed locations. It's hard in two dimensions so in space no-one can here you scream "travelling salesman!!!"

 

[Eahlstan]

I’m trying to figure out what the traveling salesman has to do with the content of your post? Were you having trouble figuring out which systems you’d already visited?

It's about finding the shortest route to visit all the systems.
That's something completely different to 'I am not allowed to visit a system twice'.
Sure one could simply jump from system 1 to system 2 to system three. But in this case the systems closest to each other are not the systems next in ascending order and therefore this would take much more time than needed.
And this problem gets worse the more points there are.
I bookmarked 119 systems, that would be more than 2,34*10^194 possible routes.
Additionally the exact coordinates of the systems are only known after you visit them (they get written in your log file), so there is literally no way to find the optimal solution.

Furthermore, humans solving two dimensional TSPs have an error margin of 0-1% at ten points, 1-4% at 20 points and 2-5% at 50 points.
Solving three dimensional TSPs are worse, see www.researchgate.net/publication/48202356_2D_and_3D_Traveling_Salesman_Problem for more info.

I hate the TSP because I'm wasting time on non optimal routes.

 

[Sapyx]

...If anyone knows why there no systems named H1 and H2 please tell me...

I would assume that they are generated, but are not stars. At least, not stars you can tag and visit. Some possible options that occur to me are:

- Nebulae
- Rogue_Planet, a type of star speculated to have been generated by the stellar forge but not made visible on the galmap.
- Supermassive_blackhole, and since there's only one supermassive black hole, the stellar forge auto-deletes any that are created randomly.
- Some other non-stellar-object type not yet suspected to exist.

 

[MattG]

It's about finding the shortest route to visit all the systems.
That's something completely different to 'I am not allowed to visit a system twice'.
Sure one could simply jump from system 1 to system 2 to system three. But in this case the systems closest to each other are not the systems next in ascending order and therefore this would take much more time than needed.
And this problem gets worse the more points there are.
I bookmarked 119 systems, that would be more than 2,34*10^194 possible routes.
Additionally the exact coordinates of the systems are only known after you visit them (they get written in your log file), so there is literally no way to find the optimal solution.

Furthermore, humans solving two dimensional TSPs have an error margin of 0-1% at ten points, 1-4% at 20 points and 2-5% at 50 points.
Solving three dimensional TSPs are worse, see www.researchgate.net/publication/48202356_2D_and_3D_Traveling_Salesman_Problem for more info.

I hate the TSP because I'm wasting time on non optimal routes.

EDJP will produce a near-optimal path for a certain amount of systems (I think max currently is 50, but it's a somewhat arbitrary limit). You do need to either enter coordinates, or it can look them up in EDSM if the system has already been visited - but you don't need to be exact, I go with nearest 5 for X and Z coordinates. Initial entering is somewhat tiresome - but no worse than adding all the bookmarks IMO. The interface does need some work, and I keep meaning to improve it so it uses jump range as part of the calc (if you can do 45LY in 1 jump, then a distance of 46LY and 80LY should have equal weighting as they're both 2 jumps...) but it does it's job. Oh, and I need to make it work as a Hamiltonian Path rather than TSP as you'd rarely want to go back to the start...

 

[kpmop]

You can filter the galaxy map on un-visited systems and use this filter for the route plot -- i.e. it your route will only be unvisited systems between where you are where you want to go (more or less anyway). It might not work too well if you've already visited most of the systems in a volume though.

Yeah I know it's really not what you asked, but might be worth a look...?

 

[Eahlstan]

EDJP will produce a near-optimal path for a certain amount of systems (I think max currently is 50, but it's a somewhat arbitrary limit). You do need to either enter coordinates, or it can look them up in EDSM if the system has already been visited - but you don't need to be exact, I go with nearest 5 for X and Z coordinates. Initial entering is somewhat tiresome - but no worse than adding all the bookmarks IMO.

The AA-A H systems in the sector I'm currently searching were not listed on EDSM and finding the 5 nearest visited systems takes too much time.

The interface does need some work, and I keep meaning to improve it so it uses jump range as part of the calc (if you can do 45LY in 1 jump, then a distance of 46LY and 80LY should have equal weighting as they're both 2 jumps...)

That's almost true if you'r near the core. In less dense areas the problem is worse. With a jump range of 51 lys a system 100 lys away means two jumps in dense areas, or much more jumps if there are no stars between them. On the other hand a system 60 lys away with a second system 30 lys away from both really only takes two jumps.
To really solve this problem one would have to take into account every single system between the 'must visit' systems, ending up in a TSP with ten thousands of points.

50 points are nice, but if there are over 350 systems reducing it to 7 sets with 50 points would be worse than trying to manually solve 3 sets of 120 points (I have no proof for this).

Oh, and I need to make it work as a Hamiltonian Path rather than TSP as you'd rarely want to go back to the start...

Is there a differnce between a Hamiltonian Path and the open loop TSP? (like in www.researchgate.net/publication/30..._CITIES_OPEN_LOOP_TRAVELLING_SALESMAN_PROBLEM)

 

[Eahlstan]

I would assume that they are generated, but are not stars. At least, not stars you can tag and visit. Some possible options that occur to me are:

- Nebulae
- Rogue_Planet, a type of star speculated to have been generated by the stellar forge but not made visible on the galmap.
- Supermassive_blackhole, and since there's only one supermassive black hole, the stellar forge auto-deletes any that are created randomly.
- Some other non-stellar-object type not yet suspected to exist.

Wouldn't that lead to randomly missing numbers and not just zero to two?

 

[Shinji Ikari]

I spent the last 17 days scanning every body in every AA-H system in sector EORD BLAO.

There was nothing interesting to be found, but that didn't stop me. What did stop me twice was a invisible nearly 3 million km wide ring around a neutron star orbiting a black hole facing the black hole, only one light source per system is definitely a bad idea.

If anyone knows why there no systems named H1 and H2 please tell me.


In total there were 386 AA-A H systems and the primary bodies were:

Black holes: 251
Wolf-Rayet O: 35
Class O: 35
Class B: 24
Blue-white super giants: 19
Wolf-Rayet WNC: 9
Wolf-Rayet C: 7
Wolf-Rayet N: 6

Only 31 systems were discovered so far, most of them by Bourbon014.

All bodies have been scanned and they are available at EDSM and EGO.

Here are some pictures showing the distribution of said systems (more space for bookmarks would be nice):

3-119:



120-239:



240-359:



360-388:



Pictures of all system maps can be found here: https://photos.app.goo.gl/m2TbCYjzzV2nWGxH6

Well, the good thing is that we are quite good at the problem,

It has been observed that humans are able to produce near-optimal solutions quickly, in a close-to-linear fashion, with performance that ranges from 1% less efficient for graphs with 10-20 nodes, and 11% more efficient for graphs with 120 nodes.

 

[iain666]

The AA-A H systems in the sector I'm currently searching were not listed on EDSM and finding the 5 nearest visited systems takes too much time.

I think Matt was suggesting that his tool takes manually entered coordinates and being within 5ly (so easily readable from the galmap) is close enough, not that you enter 5 known-to-EDSM systems near your target.

 

[Sierra_Hotel]

I see I just needed to look further down the page to see this TSP discussion before I made my own new thread Off to give EDJP a try for this.

 

[Sierra_Hotel]

EDJP will produce a near-optimal path for a certain amount of systems (I think max currently is 50, but it's a somewhat arbitrary limit). You do need to either enter coordinates, or it can look them up in EDSM if the system has already been visited - but you don't need to be exact, I go with nearest 5 for X and Z coordinates. Initial entering is somewhat tiresome - but no worse than adding all the bookmarks IMO. The interface does need some work, and I keep meaning to improve it so it uses jump range as part of the calc (if you can do 45LY in 1 jump, then a distance of 46LY and 80LY should have equal weighting as they're both 2 jumps...) but it does it's job. Oh, and I need to make it work as a Hamiltonian Path rather than TSP as you'd rarely want to go back to the start...

Nice work, sir! Quick little test run and this is exactly what I've been pondering the last few days. I agree, at least for my use, the Hamiltonian Path would be easier. Now, since we already have system coordinates available in EDD, is there a way that mass ingestion of systems could be done, up to the limit? Would be so easy if you could just copy/paste an entire sheet of systems you're looking to explore. I know, beggars can't be choosers Knowing the coding required for something like that is well beyond my current skillset.