The easy route the easy way: New chip calculates the shortest distance in an instant

4 years ago
Anonymous $yQ5BfQaAxy

https://www.sciencedaily.com/releases/2020/01/200123152500.htm

To solve this conundrum, scientists are actively exploring the use of integrated circuits. In this method, each state in a traveling salesman problem (for example, each possible route in the delivery truck) is represented by "spin cells," each having one of two states. Using a circuit which can store the strength of one spin cell state over another, the relationship between these states (or to use our analogy, the distance between two cities for the delivery truck) can be obtained. Using a large system containing the same number of spin cells and circuits as the components (or the cities and routes for the delivery truck) in the problem, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the traveling salesman problem, or any other type of combinatorial optimization problem.

However, a major drawback of the conventional way of using integrated circuits is that it requires pre-processing, and the number of components and time required to input the data increase as the scale of the problem increases. For this reason, this technology has only been able to solve the traveling salesman problem involving a maximum of 16 states, or cities.

The easy route the easy way: New chip calculates the shortest distance in an instant

Jan 26, 2020, 10:18pm UTC
https://www.sciencedaily.com/releases/2020/01/200123152500.htm > To solve this conundrum, scientists are actively exploring the use of integrated circuits. In this method, each state in a traveling salesman problem (for example, each possible route in the delivery truck) is represented by "spin cells," each having one of two states. Using a circuit which can store the strength of one spin cell state over another, the relationship between these states (or to use our analogy, the distance between two cities for the delivery truck) can be obtained. Using a large system containing the same number of spin cells and circuits as the components (or the cities and routes for the delivery truck) in the problem, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the traveling salesman problem, or any other type of combinatorial optimization problem. > However, a major drawback of the conventional way of using integrated circuits is that it requires pre-processing, and the number of components and time required to input the data increase as the scale of the problem increases. For this reason, this technology has only been able to solve the traveling salesman problem involving a maximum of 16 states, or cities.