 |
Illustration for Death of a Salesman by Brian Stauffer for the Soulpepper Theater Company, Toronto
|
It may seem like a stretch to write about combinatorial
optimization problems (aka the traveling salesman problem) on a blog about the ‘language
of smell,’ but Limbic Signal isn’t
just about smells, or language, but the connections between olfaction and
computation. Our olfactory system is a champion at dealing with very large,
very complex datasets.
Olfaction uses our brain in ways the other senses don’t.
Some of the ways olfaction diverges from the other senses are akin to novel solutions
to very complex problems in computation, such as big-data-sifting, pattern
recognition, or the aforementioned traveling salesman problem.
Also note that, in
addition to the magnet network described below, another unconventional solution
to the traveling salesman problem is to use mold. In fact, slime mold was used
to design Spain's motorways and the Tokyo rail system.
So this article below does a good job of explaining the
traveling salesman problem; I straight copied it from the writers at phys.org.
And in the second section is an explanation of an interesting solution to the
problem.
Researchers create
a new type of computer that can solve problems that are a challenge for
traditional computers
The traveling
salesman problem
There is a special type of problem - called a
combinatorial optimization problem - that traditional computers find difficult
to solve, even approximately. An example is what's known as the "traveling
salesman" problem, wherein a salesman has to visit a specific set of
cities, each only once, and return to the first city, and the salesman wants to
take the most efficient route possible. This problem may seem simple but the
number of possible routes increases extremely rapidly as cities are added, and
this underlies why the problem is difficult to solve.
...
It may be tempting to simply give up on the traveling
salesman, but solving such hard optimization problems could have enormous
impact in a wide range of areas. Examples include finding the optimal path for
delivery trucks, minimizing interference in wireless networks, and determining
how proteins fold. Even small improvements in some of these areas could result
in massive monetary savings, which is why some scientists have spent their
careers creating algorithms that produce very good approximate solutions to
this type of problem.
An Ising machine
The Stanford team has built what's called an Ising
machine, named for a mathematical model of magnetism. The machine acts like a
reprogrammable network of artificial magnets where each magnet only points up
or down and, like a real magnetic system, it is expected to tend toward
operating at low energy.
The theory is that, if the connections among a network of
magnets can be programmed to represent the problem at hand, once they settle on
the optimal, low-energy directions they should face, the solution can be
derived from their final state. In the case of the traveling salesman, each
artificial magnet in the Ising machine represents the position of a city in a
particular path.
No comments:
Post a Comment