Pigeon, curve and traveling salesman problem


Mo Williams Children’s book Don’t let the pigeons drive the bus!, The protagonist-a pigeon, obvs-uses every trick (literally) in the book to convince the reader that when an ordinary human driver suddenly has to leave, he should be allowed to drive a bus. Williams’ book had unexpected scientific consequences in 2012, when the fully respected journal “Human Cognition” published the work of fully respected researchers Brett Gibson, Matthew Wilkinson and Debbie Kelly A completely respected paper. They show through experiments that pigeons can find a solution close to the optimal solution to a simple case of famous mathematical curiosity: the traveling salesman problem. Their headline is “Let the pigeon drive the bus: the pigeon can plan the future route in a room.”

Don’t say that scientists lack a sense of humor. Or, cute headlines do not help generate publicity.

The traveling salesman problem is not just a curiosity. This is a very important example of a problem of great practical significance, called combinatorial optimization. Mathematicians are accustomed to using obvious trivial matters to ask deep and important questions.

The important trivia that inspired this article originated in a useful book—you guessed it—traveling salesman. Door-to-door seller. Like any wise businessman, the German traveling salesman in 1832 (who had always been a man at the time) attached great importance to efficient use of time and cutting costs. Fortunately, the help is at hand, in the form of a brochure: the traveling salesman-how he should and what he must do to get the order and ensure the success of his business-is promoted by an older traveler Staff provided.

The old idle hawker pointed out:

Business brings traveling salesmen here, and then there, there is no travel route that can be correctly indicated for all situations that happen; but sometimes, through proper selection and arrangement of travel, so much time can be obtained that we think we can Avoid making some rules in this area… The point always includes visiting as many places as possible without having to touch the same place twice.

The manual does not propose any mathematical method to solve this problem, but it does contain five examples of alleged best travel.

The traveling salesman problem, or TSP, later called the traveling salesman problem to avoid gender discrimination, it conveniently has the same acronym, and is a founding example in the field of mathematics now known as combinatorial optimization. This means “find the best option among a large number of possibilities, and these possibilities are too great to check one at a time.”

Strangely, until 1984, the TSP name did not seem to have been explicitly used in any publications on this subject, although it was widely used in informal discussions among mathematicians early on.

In the Internet age, companies rarely sell their products by sending people from town to town with suitcases full of samples. They put everything online. As usual (unreasonable effectiveness), this cultural change did not make the TSP obsolete. As online shopping grows exponentially, from parcels to supermarket orders to pizzas, the need for effective ways to determine routes and schedules has become increasingly important.

The portability of mathematics also comes into play. The application of TSP is not limited to driving between towns or along city streets. Once upon a time, famous astronomers owned their own telescopes or shared them with several colleagues. The telescope can be easily reoriented to point to new celestial bodies, so it is easy to improvise. This is no longer the case, because the telescopes used by astronomers are huge, extremely expensive, and can be accessed online. It takes time to aim the telescope at a new object, and it cannot be used for observation when the telescope is moved. Visiting the target in the wrong order, wasting a lot of time, moving the telescope a long distance, and then back somewhere near where it started.

In DNA sequencing, the fragment sequences of DNA bases must be connected together correctly, and the completed sequence must be optimized to avoid wasting computer time. Other applications range from efficient aircraft routing to the design and manufacture of computer microchips and printed circuit boards. TSP’s approximate solution has been used to find effective routes for Meals on Wheels and optimize the process of delivering blood to the hospital. A version of TSP even appeared in “Star Wars”, more appropriately President Ronald Reagan’s hypothetical strategic defense plan, where powerful lasers orbiting the earth will target a series of incoming nuclear missiles.

In 1956, operations research pioneer Merrill Flood thought that TSP might be difficult. In 1979, Michael Garey and David Johnson proved that he was right: there is no effective algorithm to solve the “worst case” problem. But the worst-case scenario is often very artificial, rather than a typical example in the real world. Therefore, mathematicians in the field of operations research began to study how many cities they could handle to solve real-world problems.


Source link