Mathematical Challenge

[DMFW]

Isn't the count of unordered subsets what we want though? It's true that the actual route will be one unique ordering of each subset but in terms of counting the possible sets of waypoints themselves we don't need to worry about how they are ordered, since we know that there will be one (and only one) order for each unordered subset that will be our actual physical route?

e.g. we pull out the combination A,B,H,Y (when including the sets of 4) and I am just assuming that there is always a unique order we can place the set in such that the remaining distance is successively less for each star. But we don't want to count A,B,H,Y twice (in fact it is the very fact that we have to order it and can only do so one way which makes this calculation work) so it is the count of unique unordered sets (each one containing one and only one physical route order) that give us the upper bound answer.

Although I do think this only works if the stars you include are only those that are closer to your target than your starting star (so not all 400 billion if calculating from Sol) since that means you will never get a set that starts by going backwards.

P.S. I think this works out differently if the problem is to find a count of routes where the distance from the start always increases as well as the distance from the target always decreasing. My definition of "valid" routes only stipulates that the distance to the target always decreases. We could call "sensible" routes ones where this applied and where the distance from the start always increased as well. This would eliminate spiral routes and the like. I'm just happy to have worked out more about the "valid" route question. The "sensible" route question, does suffer from the problem you are concerned with and the count of "sensible" routes should be much smaller than "valid" ones but it can be left as an open question unless we're all having too much fun.

Whatever the answers the numbers are truly astronomical [I've been wanting to do that pun ever since the thread started]

 

[Hanekura Shizuka]

DMFW, you were closer the first time. The 2^N solution is for unordered subsets. However these are ordered by distance, and you can't go backwards per your original definition.

The reason why we want the unordered subsets in this case is because we have no control over the order - the order is dictated to us by stellar geography. If we select a subset of stars, there's only one order those can go in, from one to the next. Therefore, to the eyes of mathematics, an order of, say, 1-4-8 and 1-8-4 and 8-4-1 is the same subset if we want unordered subsets, because it contains the same elements. In the same way, if this were a route, the only one that can be used is 1-4-8 - one subset - because any others would go out of order.

 

[Ziljan]

Isn't the count of unordered subsets what we want though?

Read Jackie's post. The stars are naturally ordered by distance from the center of the galaxy according to your original definition. Besides, the total number of sets of unordered subsets is (by PC computing standards) infinitely larger than the actual ordered solution you were originally asking for.

For instance my solution for the subsets ordered by diminishing range only had 22 zeroes. Which is far smaller than PC infinity. And I am guessing that by iteration of incremental waypoint subtraction, the upper bound of sets of ordered subsets on a ship with unlimited range would only have ~44 zeroes. But I haven't done the math on that one yet.

 

[Allitnil]

Very nice, because that not only simplifies the problem, it also creates an upper bound. If there is no restriction on range, then the problem is reduced to single dimensional set with the dimension being "individual distance from Sgr A*". Every sequential jump reduces the range and thus population of stars to jump to.

Hence the solution is to find the total possible unique linear pairings of the numbers in the set in order of distance from Sgr A* is simply

N = (n-1) + (n-2) + (n-3) +... + (1-0) = n(n-1)/2

Since n ~= 140,000,000,000 stars

Which is N ~ 0.5*(140,000,000,000)^2 ~ 10^22

Now if we have limited range, then the total number of sequential pairings based on range is a number less than 10^22. Because each subsequent pairing will be a tiny fraction of (n-1).

However this still isn't the answer, since you'd have to iterate the problem again to come up with solutions that excluded all the possible rejected pairings. And now my head hurts, so I'll pass the baton.

The lower bound is quite simply found by using Hanekura's approach. It's the product of the number of options at each jump for a high range ship. Even if there were only 10 options at each jump (and obviously the true number is much higher, running potentially into the thousands in the core) that gives ~ 10⁶⁵⁰. A lot of these routes would involve using some or many of the systems used by other routes, but each one would still be a unique route. So I'm not quite sure what your above reasoning is, but it is clearly not an upper bound.

 

[Hanekura Shizuka]

The lower bound is quite simply found by using Hanekura's approach. It's the product of the number of options at each jump for a high range ship. Even if there were only 10 options at each jump (and obviously the true number is much higher, running potentially into the thousands in the core) that gives ~ 10⁶⁵⁰. A lot of these routes would involve using some or many of the systems used by other routes, but each one would still be a unique route. So I'm not quite sure what your above reasoning is, but it is clearly not an upper bound.

I actually gave two results: an upper bound (the 2^N result) and the more detailed method which you reference here, which was an attempt to get to a result that closely matched the actual.

So now we know it's somewhere between 10⁶⁵⁰ and 2^{400,000,000,000}. We're making progress!

 

[Ziljan]

The lower bound is quite simply found by using Hanekura's approach. It's the product of the number of options at each jump for a high range ship. Even if there were only 10 options at each jump (and obviously the true number is much higher, running potentially into the thousands in the core) that gives ~ 10⁶⁵⁰. A lot of these routes would involve using some or many of the systems used by other routes, but each one would still be a unique route. So I'm not quite sure what your above reasoning is, but it is clearly not an upper bound.

It's an upper bound on the number of connections between all waypoints interior to the galactic radius of Sol, given the simplification of infinite jump range. It is not the upper bound on the subsets of these jumps, and does not take into account the the set of all possible paths or any range limitations.

 

[Hanekura Shizuka]

It's an upper bound on the number of connections between all waypoints interior to the galactic radius of Sol, given the simplification of infinite jump range. It is not the upper bound on the subsets of these jumps, and does not take into account the the set of all possible paths or any range limitations.

Actually, it does take into account the set of all possible paths, and thus is an upper bound, though does not take into account range limitations (which would reduce rather than increase our solution set). The reason is the definition of a 'valid route' given at the beginning of the thread:

If a "valid route" between any two stars "A" and "B" is defined as one where for every successive waypoint the distance to "B" is always less than the distance at the previous waypoint,

The result of this limitation is that it simplifies the number of routes greatly. More to the point, it dictates an order, from the first to the last, that the stars could be considered as candidates for a particular route. In effect, it says that, no matter what stars we pick, it MUST be in a particular order, based on its distance from A*. So we have an order of stars:

1. Sol
2. Someplace really close to Sol.
3. Someplace kind of close to Sol.
4. Someplace just a bit further from Sol.
...
399,999,999,999: Stuemeae OM-G Really Close to A*
400,000,000,000: Sagittarius A*.

So the order in which these stars could occur on this route is dictated by the distance from A*. If we go from Sol to "Someplace just a bit further from Sol", then we can't go back to "Someplace kind of close to Sol," because that would violate the terms of the experiment.

The result of this is that we have no control - AT ALL - over the order in which these stars are visited. If it is visited, then it is visited according to the order set out by the conditions of the problem - furthest from A* first, then second-furthest, then third-furthest, etc. The result of this is that different routes are not determined by the possible connections between stars, but whether or not the star is a part of the route at all. In that case, it is simply a binary - either it is a part of the route, or it isn't.

So each star has two possibilities that can affect the number of routes. Is it a part of the route, or isn't it? Again, we have NO SAY over the route, other than whether or not a star is on the route. The result of this is that the number of possible routes becomes that binary - 2 - to the power of the number of stars for which we have that decision as to whether or not to include it in the route (in this case, estimated at 400 billion). Thus do we come to our 2^N result as our upper bound.

 

[Ziljan]

Actually, it does take into account the set of all possible paths, and thus is an upper bound, though does not take into account range limitations (which would reduce rather than increase our solution set). The reason is the definition of a 'valid route' given at the beginning of the thread:

I was talking about my humble contribution. I was not talking about the 2^N or the ∏ n[SUB]i [/SUB]from i=0:J solutions. ​

 

[Hanekura Shizuka]

I'm reminded of a joke. We'll go with the Wiki version.

An astronomer, a physicist and a mathematician are on a train in Scotland. The astronomer looks out of the window, sees a black sheep standing in a field, and remarks, "How odd. All the sheep in Scotland are black!" "No, no, no!" says the physicist. "Only some Scottish sheep are black." The mathematician rolls his eyes at his companions' muddled thinking and says, "In Scotland, there is at least one sheep, at least one side of which appears to be black from here some of the time."

 

[Ziljan]

I'm reminded of a joke. We'll go with the Wiki version.

An astronomer, a physicist and a mathematician are on a train in Scotland. The astronomer looks out of the window, sees a black sheep standing in a field, and remarks, "How odd. All the sheep in Scotland are black!" "No, no, no!" says the physicist. "Only some Scottish sheep are black." The mathematician rolls his eyes at his companions' muddled thinking and says, "In Scotland, there is at least one sheep, at least one side of which appears to be black from here some of the time."

I think it was originally an engineer, a physicist, and mathematician.


An astronomer would look at the sheep, analyze it's radiation curve, and try to tell you with authority what its great great grandfather ate for breakfast.



Which reminds me of another joke:


An engineer, a physicist, and a mathematician, are locked in separate cells with plenty of canned food and water but no can opener.
The engineer constructs a can opener from pocket trash. The physicist works out the angle necessary to knock the lids off the tin cans by throwing them against the wall.
The mathematician had stacked the unopened cans next to his desiccated corpse, and inscribed on the floor in blood:

Theorem: If I can open these cans, the I shall not die.
Proof. Assume the opposite…
​

 

[AJW]

Jokes aside, and for the benefit of someone who's mathematical skills tend to peter out somewhere not much beyond basic trigonometry, can we say that whatever the galmap does, it certainly doesn't test all possible routes before plotting one? I'm fairly certain that this must be true, at least for more complex routes (something I read but failed to understand about travelling salesmen being NP-complete possibly being relevant), but it would be nice to have conformation.

 

[Hanekura Shizuka]

Jokes aside, and for the benefit of someone who's mathematical skills tend to peter out somewhere not much beyond basic trigonometry, can we say that whatever the galmap does, it certainly doesn't test all possible routes before plotting one? I'm fairly certain that this must be true, at least for more complex routes (something I read but failed to understand about travelling salesmen being NP-complete possibly being relevant), but it would be nice to have conformation.

Not quite the right problem to look at when it comes to route plotting.

This, on the other hand, is. Dijkstra's Algorithm runs in polynomial time; depending on the method used (original Dijkstra's, or Dial's) it can run at O[V²] or O[E+V*logV], where V is the number of nodes, and E the number of paths. Polynomial-time is good, generally. The difficulty occurs in that the problem that the galmap has to work on is SO huge (how many billions of stars are there?) that it's going to take time in the core regardless.

Also, this problem is complicated by working with something other than simple distance. Near the end of the route, the problem becomes a combination of minimum number of jumps and economical jumps. It's likely that Dijkstra's is used for early parts of it, then a second algorithm, one that is a bit more of a challenge, kicks in for the last 6 plots or so. For an idea, refer to Esvandiary's work here.

 

[Senik]

The underlying problem is actually very simple. For every jump, you just have to calculate the volume resulting from the intersection of two spheres:

1. A sphere centered on your ship, whose radius equals your jump range
2. A sphere centered on your destination, whose radius equals the distance to your destination

Every star within the hull of the resulting volume is a valid jump destination. You then have to repeat that recursively using every possible destination as the new starting point, until all possible paths converge on the destination system.

I can visualize how to code a program that would solve for that, given an input data set (star coordinates). But I can't even begin to imagine how you'd express some of this in a mathematical formula. It would require notation that goes way beyond anything I learned in the classes leading up to undergraduate level linear algebra.

 

[DMFW]

The main thing I'm taking away from this thread is that I am now convinced that the number of "valid" routes greatly exceeds the number of possible games of chess and also the number of atomic particles in the visible universe. These mind blowing numbers are in many senses inconceivable but it's good just to get a handle on the relative sizes by calculating reasonable approximations so that at least you can place them in a ranking order which is quite interesting (to me at least!)