87 lines
3.6 KiB
Markdown
87 lines
3.6 KiB
Markdown
---
|
||
created_at: '2015-04-14T02:49:29.000Z'
|
||
title: Russian way with the mathematical travelling salesman (1979)
|
||
url: http://www.theguardian.com/technology/2014/oct/29/mathematics-khachian-russia-travelling-salesman-archive-1979
|
||
author: bootload
|
||
points: 46
|
||
story_text:
|
||
comment_text:
|
||
num_comments: 10
|
||
story_id:
|
||
story_title:
|
||
story_url:
|
||
parent_id:
|
||
created_at_i: 1428979769
|
||
_tags:
|
||
- story
|
||
- author_bootload
|
||
- story_9371847
|
||
objectID: '9371847'
|
||
year: 1979
|
||
|
||
---
|
||
A young Soviet mathematician, apparently totally unknown to any of the
|
||
world’s senior practitioners, has found an answer to one of the most
|
||
baffling problems in computer calculation.
|
||
|
||
But his obscurity is such that his discovery went unnoticed for 10
|
||
months in the mathematical world, although work on the problem has been
|
||
going on for years.
|
||
|
||
The apparent breakthrough was achieved by L. G. Khachian, and was
|
||
published in a Soviet scientific journal, Doklady, last January. Few
|
||
people in the West read the journal and it was only after rumours of the
|
||
discovery circulated at a conference in Germany that anyone in the
|
||
mathematical world at large had even a hint that someone had come up
|
||
with an answer to what is known in the trade as the “travelling
|
||
salesman” problem.
|
||
|
||
The fact that some of the world’s best brains have been trying to solve
|
||
the problem gives some idea of its density to the layman. Reduced to its
|
||
simplest, the difficulty is to find a formula for a computer to work out
|
||
the best route for a salesman to take when he has to make calls in a
|
||
number of different cities.
|
||
|
||
This is only a sample problem. There are any number of analogous
|
||
situations in the everyday life of the industrial world: calculating the
|
||
most efficient way of staffing a factory with three shifts of workers is
|
||
another.
|
||
|
||
On the face of it, this should present no difficulty at all and, up to a
|
||
point, the computer can do the sums at its normal speed. But it only
|
||
needs a small increase in the number of cities to be visited by the
|
||
salesman for the machine to fall into the binary version of a nervous
|
||
breakdown.
|
||
|
||
The trouble is that the machine can only be programmed to work on the
|
||
problem through trial and error, laboriously going through all the
|
||
possible combinations until one emerges which is better than all the
|
||
others - known in the trade as the exponential time method.
|
||
|
||
The alternative being sought would use the polynomial time method, by
|
||
which the machine can carry out a whole range of simultaneous
|
||
calculations.
|
||
|
||
A route for a salesman visiting 60 cities would take about one-fifth of
|
||
a second to work out with a polynomial formula. Using exponential time
|
||
methods it needs literally billions of centuries. But no one so far has
|
||
managed to come up with a mathematical theory to underpin a solution.
|
||
|
||
Now Mr Khachian has burst on the scene and seems to have provided a
|
||
significant bit of the answer. Since no one knows who he is and since
|
||
there is no record of any previous publication by him, the speculation
|
||
is that he carried out his work as part of his doctoral thesis.
|
||
|
||
The best brains in the business have tried out his formula and agree
|
||
that it works, at least on a pocket calculator. It has yet to be given a
|
||
full-blown test as part of a computer programme.
|
||
|
||
Mr Khachian’s solution is not easily explained, but involves the use of
|
||
sets (that central element in the new maths) in a more imaginative way
|
||
than hitherto which closes in on the best solution.
|
||
|
||
The practical advantage of this is to cut out consideration of obvious
|
||
non-starters. The consensus of the mathematical fraternity is that the
|
||
Russian’s obscurity is not likely to last if he continues to produce
|
||
work of this calibre.
|