Tim Greening-Jackson

Roland Perry wrote:
> In message <487e7030$0$2520$da0feed9@news.zen.co.uk>, at 23:03:28 on
> Wed, 16 Jul 2008, Tim Greening-Jackson
> <zen167520_AT_zen_co_uk@?.?.invalid> remarked:
>> I presume, though, that the push to calculate the distances at that
>> time was either due to the modernisation programme or -- perhaps more
>> prosaically -- due to the fact that the means to calculate them (LEO)
>> had just come to hand.
>>
>> From my calculation, to calculate the distances between 7,000 separate
>> places would require 24,500,000 calculations. So a computer -- even
>> one with only 2,048 words of store like LEO would be attractive.
>
> If trying to solve the problem by brute force, then you'll get a very
> large number of calculations required. But there are many very simple
> ways to optimise the search - although some of the techniques were still
> in the research labs when I was at college in 1970.
>
> The most obvious optimisation is to abandon the route you are exploring
> as soon as the mileage exceeds your currently discovered minimum. eg If
> you've already discovered that Waterloo-Portsmouth is no more than 73
> miles via Haselemere, you abandon any alternative route (perhaps via
> Basingstoke) as soon as it exceeds 73 miles. viz At Eastleigh which is
> also 73 miles from London.
>
> In practice you can truncate the process even quicker by working
> backwards from the destination as well (you won't find any shorter route
> from London to Portsmouth Harbour than starting from the already known
> shortest route from London to Hilsea).

The algorithm used was fairly a "brute force" one, based on working out
the minimum distance to successive adjacent nodes. But its use of brute
force is quite smart, as it splits the network in to regions and
considers the "difficult" (ie multiply connected nodes) I've re-created
it in Python, and the key bit is below:

def process_network(self):
while 1:
complete=1
for r in junctions:
for c in junctions:
if r != c or self.distances[r][c] != maxint:
first = self.distances[r][c]
for n in junctions:
if n != r and n != c and r!= c and
self.distances[c][n] != maxint:
next = self.distances[c][n]
distance = first + next
print "%s->%s->%s = %d + %d = %d" % (r,
c, n, first, next, distance)
if distance < self.distances[r][n]:
self.insert_distance(r, n, distance)
print self
complete=0
if complete: break

The problem was actually solved by Roger Coleman 15 years before you
were at college, and to put it in it's appropriate historical context
was done as Kuhn was developing the "Hungarian Method" solution to the
Travelling Salesman problem.

To say it was done on a machine which couldonly hold 2,048 16-bit words
--- and that had to contain the "operating system", program and data ---
and for which there wasn't even an assembler (they had to write the
object code down by hand in BCD) it's quite remarkable.