Den nemme rute på den nemme måde:Ny chip beregner den korteste afstand på et øjeblik

Hvordan ville du gå om at returnere bøger til de rigtige hylder i et stort bibliotek med mindst mulig gang? Hvordan vil du bestemme den korteste rute for en lastbil, der skal levere mange pakker til flere byer? Dette er nogle eksempler på "rejsende sælgerproblem, "en type "kombinatorisk optimeringsproblem", som ofte opstår i dagligdagssituationer. At løse problemet med den rejsende sælger involverer at søge efter den mest effektive af alle mulige ruter. For at gøre dette let, vi har brug for hjælp fra lav effekt, højtydende kunstig intelligens.

For at løse dette problem, forskere udforsker aktivt brugen af ​​integrerede kredsløb. I denne metode, hver stat i et rejsende sælgerproblem (f.eks. hver mulig rute i varebilen) er repræsenteret af "spinceller, "hver har en af ​​to tilstande. Ved hjælp af et kredsløb, der kan lagre styrken af ​​en spincelletilstand over en anden, forholdet mellem disse tilstande (eller for at bruge vores analogi, afstanden mellem to byer for varebilen) kan fås. Ved at bruge et stort system, der indeholder det samme antal spinceller og kredsløb som komponenterne (eller byerne og ruterne for varebilen) i problemet, vi kan identificere den tilstand, der kræver mindst energi, eller den rute, der dækker den mindste afstand, dermed løse problemet med den rejsende sælger, eller enhver anden form for kombinatorisk optimeringsproblem.

Imidlertid, en stor ulempe ved den konventionelle måde at bruge integrerede kredsløb på er, at den kræver forbehandling, og antallet af komponenter og tid, der kræves til at indtaste dataene, stiger, efterhånden som problemets omfang øges. Af denne grund, denne teknologi har kun været i stand til at løse det rejsende sælgers problem, der involverer maksimalt 16 stater, eller byer.

En gruppe forskere ledet af professor Takayuki Kawahara fra Institut for Elektroteknik ved Tokyo University of Science havde til formål at overvinde dette problem. De observerede, at interaktionen mellem hver spincelle er lineær, som sikrede, at spin -cellerne kun kunne interagere med cellerne i nærheden af ​​dem, forlængelse af behandlingstiden. "Vi besluttede at arrangere cellerne lidt anderledes for at sikre, at alle spinceller kunne forbindes, "Prof Kawahara forklarer.

At gøre dette, de arrangerede først kredsløbene i et todimensionelt array, og spincellerne separat i et endimensionelt arrangement. Kredsløbene ville derefter læse dataene, og et aggregat af disse data blev brugt til at skifte spincellernes tilstande. Dette ville betyde, at antallet af krævede spinceller og den nødvendige tid til behandling blev drastisk reduceret.

Forfatterne har præsenteret deres resultater på IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI 2020). "Vores nye teknik repræsenterer således en fuldt koblet metode, " bemærker prof Kawahara, "og har potentialet til at løse et rejsende sælgerproblem, der involverer op til 22 byer." Forfatterne håber på, at denne teknologi vil have fremtidige applikationer som et højtydende system med lave strømkrav til kontorudstyr og tablet-terminaler for nemt at finde optimale løsninger fra et stort antal kombinationer.