Many Shortest Routes - A proposed new problem
Back to General discussions forum
This problem is a different way of looking at a popular algorithm.
Because there is a lot of data in the problem, I have made use of the Linear Congruential Generator. Unfortunately, I have had to change one of the parameters used by the generator. I have changed the parameter M from 2097152 to 2097169 (which is the nearest prime to its original value). While developing the problem I was puzzled by some of the results that I was obtaining. Further investigation showed that the generated data was very far from being random. The change of the parameter M corrected the problem. As an example of what was going wrong, consider the following. We start with a random seed of 0 and then begin to use the generator to create a sequence of numbers, each in the range 1 to 4 (as required by the problem). The sequence created is 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, ... When changing the parameter M, as described above, the sequence looks much more random.
Clive, thanks a lot for the problem!
I also noticed sometimes that the values in LCG problem which were consequently reused in some other problems are not
the most lucky choice. So many thanks for this improvement either!
This was a fun one! And the problem statement was very well-worded as well, one can quite clearly visualize the unusual toroidal road network with no visual aid necessary.
Also an interesting thought unrelated to the problem... if you were placed into such a toroidal road network without knowing which axis was "Y" (in-plane with toroid) and which was "X" (perpendicular to toroid plane), there's actually no way to determine which is which without zooming out and seeing the physical shape of the network. And so it seems like one network could be 'mapped' onto two different toroids, each with axes 'inverted' from the other. Although trying to visualize one toroid transforming into the other is making my head hurt a bit...
