Lösung des Problems eines Handlungsreisenden mithilfe eines magnischen kombinatorischen Geräts

Wissenschaftliche Berichte Band 13, Artikelnummer: 11708 (2023) Diesen Artikel zitieren

207 Zugriffe

Details zu den Metriken

Das Travelling-Salesman-Problem (TSP) ist ein Entscheidungsproblem, das für eine Reihe praktischer Anwendungen von wesentlicher Bedeutung ist. Heutzutage wird dieses Problem auf digitalen Computern gelöst, die eine boolesche Architektur nutzen, indem eine Reihe möglicher Routen nacheinander überprüft werden. In dieser Arbeit beschreiben wir eine spezielle Art von Hardware für die TSP-Lösung. Es handelt sich um ein magnetisches kombinatorisches Gerät, das aus magnetischen und elektrischen Teilen besteht, die im aktiven Ringkreis verbunden sind. Im magnetischen Netz aus Phasenschiebern, Frequenzfiltern und Dämpfungsgliedern gibt es eine Reihe möglicher Ausbreitungswege. Die Phasenschieber ahmen Städte im TSP nach, während die Entfernung zwischen den Städten in der Signaldämpfung kodiert ist. Der Satz von Frequenzfiltern sorgt dafür, dass sich die Wellen auf unterschiedlichen Frequenzen über die verschiedenen Routen ausbreiten. Das Funktionsprinzip basiert auf der klassischen Wellenüberlagerung. Es gibt eine Reihe von Wellen, die auf allen möglichen Wegen parallel eintreffen und unterschiedliche Phasenverschiebungen und Amplitudendämpfungen anhäufen. Allerdings werden nur die Wellen, die die bestimmte Phasenverschiebung akkumulieren, durch den elektrischen Teil verstärkt. Die Verstärkung erfolgt zunächst bei den Wellen, die die geringsten Ausbreitungsverluste aufweisen. Dadurch eignet sich dieser Gerätetyp für TSP-Lösungen, bei denen Wellen den Verkäufern ähneln, die auf allen möglichen Routen gleichzeitig unterwegs sind. Wir präsentieren die Ergebnisse der numerischen Modellierung, die die TSP-Lösungen für vier und sechs Städte veranschaulichen. Außerdem präsentieren wir experimentelle Daten für die TSP-Lösung mit vier Städten. Der Prototyp des Geräts besteht aus handelsüblichen Komponenten, darunter magnetische Phasenschieber/Filter, Koaxialkabel, Splitter, Dämpfungsglieder und ein Breitbandverstärker. Es gibt drei Beispiele für die Suche nach der kürzesten Route zwischen den Städten für drei verschiedene Sätze von Stadt-zu-Stadt-Entfernungen. Der vorgeschlagene Ansatz ist auf TSP mit einer größeren Anzahl von Städten skalierbar. Auch körperliche Grenzen und Herausforderungen werden besprochen.

TSP ist eines der bekanntesten kombinatorischen Optimierungsprobleme1. Es kann wie folgt ausgedrückt werden: „Finden Sie anhand einer Liste von Städten und der Entfernungen zwischen jedem Städtepaar die kürzestmögliche Route, die jede Stadt genau einmal besucht und zur Ursprungsstadt zurückkehrt.“ Es handelt sich um ein nichtdeterministisches Polynomzeithärteproblem (NP-schwer), was bedeutet, dass es keine Garantie dafür gibt, die optimale Route zu erhalten, und keinen genauen Algorithmus, um es in Polynomzeit zu lösen. TSP ist in einer Vielzahl praktischer Anwendungen wichtig, darunter Transport2, Planung3 und Genomik4. Mathematisch kann es als gegebene Menge von \(n\) Städten mit den Namen \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n) definiert werden }\right\}\) und Permutationen \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\} \). Das Ziel besteht darin, \({\sigma }_{i}\) so zu wählen, dass die Summe aller euklidischen Entfernungen zwischen Städten in einer Tour minimiert wird. TSP kann als ungerichteter gewichteter Graph modelliert werden, wie in Abb. 1 dargestellt, wobei die Städte die Eckpunkte des Graphen sind, Pfade die Kanten des Graphen sind und die Entfernung eines Pfades das Gewicht der Kante ist. TSP kann gelöst werden, indem nacheinander alle möglichen \(\left(n-1\right)!/2\) möglichen Routen überprüft werden. Es ist relativ einfach, alle möglichen Routen für eine kleine Anzahl von Städten zu überprüfen. Beispielsweise gibt es \(\left(4-1\right)!/2=3\) Routen für den TSP mit vier Städten. Die Anzahl der möglichen Routen steigt proportional zur \(n\)-Fakultät, was es schwierig macht, eine Lösung für eine große Anzahl von Städten mit klassischen Computergeräten zu finden.

Ungerichteter gewichteter Graph für TSP mit vier Städten. Die Städte sind die Eckpunkte des Diagramms, Pfade sind die Kanten des Diagramms und die Entfernung eines Pfads ist das Gewicht der Kante.

Es gab mehrere Versuche, spezielle Hardware für die TSP-Lösung zu bauen5,6. Beispielsweise wurde ein 6-Städte-TSP mithilfe eines optischen Netzwerks vom Kohonen-Typ6 gelöst. Allerdings führte keiner dieser Ansätze zu einem praktisch brauchbaren Gerät. In jüngster Zeit wurden verschiedene Optimierungstechniken der künstlichen Intelligenz (KI) auf TSP7 angewendet. Es kann die TSP-Lösung erheblich beschleunigen, bietet jedoch bei der Implementierung auf herkömmlicher Hardware keinen grundsätzlichen Vorteil.

Hier betrachten wir einen speziellen Typ eines kombinatorischen Geräts, bei dem ein Rechenvorgang mit der Suche nach einem Ausbreitungsweg der Welle durch die ausgewählten Knoten im Netz verbunden ist. Dieser Ansatz wurde erstmals in Ref.8 beschrieben. Die Grundidee besteht darin, den Vorteil der klassischen Wellenüberlagerung zu nutzen, bei der sich mehrere Wellen gleichzeitig auf unterschiedlichen Wegen ausbreiten können. Möglicherweise können nur die Signale verstärkt werden, die sich durch die ausgewählten Stellen im Netz ausbreiten und eine bestimmte Phasenverschiebung akkumulieren. Aufgrund der deutlichen Phasenverschiebungen, die in Wellenleitern mit Mikrometerlänge erreicht werden können, eignen sich Spinwellen-Geräte (magnonische Geräte) für diesen Zweck am besten. Der Rest der Arbeit ist wie folgt organisiert. Im Abschnitt „Materialstruktur und Funktionsprinzip“ beschreiben wir das Funktionsprinzip des magnonischen kombinatorischen Logikgeräts für TSP. Die Ergebnisse der numerischen Modellierung, die die TSP-Lösung für vier und sechs Städte veranschaulichen, werden im Abschnitt „Numerische Modellierung“ vorgestellt. Die experimentellen Daten für die TSP-Lösung für vier Städte werden im Abschnitt „Experimentelle Daten“ dargestellt. Die Diskussion und die Schlussfolgerungen finden Sie in den Abschnitten „Diskussion“ und „Schlussfolgerungen“.

Die Schaltpläne des kombinatorischen Geräts für TSP mit vier Städten sind in Abb. 2 dargestellt. Der Kern der Struktur ist das Netz bestehend aus Phasenschiebern, Dämpfungsgliedern, Frequenzfiltern und Leistungssensoren. Die mit den Buchstaben A, B, C und D gekennzeichneten Kreise sind Phasenschieber, die die vier Städte darstellen. Jeder Phasenschieber sorgt für eine einzigartige Phasenverschiebung, die proportional zum Logarithmus einer Primzahl ist. Stadt A wird beispielsweise durch den Phasenschieber dargestellt, der dem sich ausbreitenden Signal eine Phasenverschiebung \(\pi \times \mathit{Log}\left(2\right)\) verleiht. Stadt B wird durch den Phasenschieber dargestellt, der \(\pi \times \mathit{Log}\left(3\right)\) Phasenverschiebung bereitstellt, und so weiter. Es gibt zwei Städte A, eine auf der linken und eine auf der rechten Seite des Netzes. Dies ist die Stadt, von der aus der Verkäufer startet und in die er nach der Reise zurückkehren sollte. Die Phasenschieber sind über Wellenleiter miteinander verbunden. In jeden Wellenleiter ist ein Dämpfungsglied eingefügt. Die Entfernung zwischen den Städten wird in die Signaldämpfung kodiert. Beispielsweise kann eine Entfernung von 10 Meilen einer Dämpfung von 1 dB entsprechen. Es gibt eine Reihe von Frequenzbandpassfiltern. Diese Filter zielen darauf ab, unterschiedliche Frequenzen für unterschiedliche Ausbreitungsrouten von Stadt A links zu Stadt A rechts sicherzustellen. Beispielsweise kann sich nur ein Signal mit der Frequenz \({f}_{1}\) über die Route ABA ausbreiten; Nur ein Signal mit der Frequenz \({f}_{2}\) kann sich über die Route ABCA usw. ausbreiten. In jeden Wellenleiter ist außerdem eine Reihe von Leistungsdetektoren eingefügt. Diese Detektoren sollen die Ausgabe liefern: den Signalausbreitungsweg. In Abb. 2 sind die Detektoren als Farbkreise markiert. Die grüne Farbe soll den Energiefluss über einem bestimmten Referenzwert (z. B. 1 dBm) darstellen. Die rote Farbe soll keinen Energiefluss darstellen.

Schematische Darstellung des kombinatorischen Geräts für TSP mit vier Städten. Der Kern der Struktur ist das Netz bestehend aus Phasenschiebern, Dämpfungsgliedern, Frequenzfiltern und Leistungssensoren. Die mit den Buchstaben A, B, C und D gekennzeichneten Kreise sind Phasenschieber, die die vier Städte darstellen. Jeder Phasenschieber sorgt für eine einzigartige Phasenverschiebung, die proportional zum Logarithmus einer Primzahl ist. Stadt A wird beispielsweise durch den Phasenschieber dargestellt, der dem sich ausbreitenden Signal eine Phasenverschiebung \(\pi \times \mathit{Log}\left(2\right)\) verleiht. Stadt B wird durch den Phasenschieber dargestellt, der \(\pi \times \mathit{Log}\left(3\right)\) Phasenverschiebung bereitstellt, und so weiter. Es gibt zwei Städte A, eine auf der linken und eine auf der rechten Seite des Netzes. Dies ist die Stadt, von der aus der Verkäufer startet und in die er nach der Reise zurückkehren sollte. Die Phasenschieber sind über Wellenleiter miteinander verbunden. Zwischen jedem Städtepaar ist ein Dämpfungsglied eingefügt. Die Entfernung zwischen den Städten wird in die Signaldämpfung kodiert. Beispielsweise kann eine Entfernung von 10 Meilen einer Dämpfung von 1 dB entsprechen. Es gibt eine Reihe von Frequenzbandpassfiltern. Diese Filter zielen darauf ab, unterschiedliche Frequenzen für unterschiedliche Ausbreitungsrouten von der Stadt A links zur Stadt A rechts sicherzustellen.

Es gibt einen Breitbandverstärker \(G\), einen spannungsabstimmbaren Phasenschieber \(\Psi\) und einen spannungsabstimmbaren Dämpfer \(R\) außerhalb des Netzes. Im Folgenden bezeichnen wir diese Elemente als „äußeren“ Teil. Der Breitbandverstärker soll eine Signalverstärkung für alle Signalfrequenzen gewährleisten. Der spannungsabstimmbare Phasenschieber und der spannungsabstimmbare Dämpfer dienen zur Steuerung der Phasenverschiebung und der Dämpfung des externen Teils. Die Kombination des Netzes mit dem externen Teil bildet einen aktiven Mehrpfad-Ringkreis8. Es gibt eine Reihe möglicher Routen für die Signalausbreitung im Netz. Die unterschiedlichen Ausbreitungswege sind mit unterschiedlicher Phasenverschiebung \(\Delta ({f}_{i})\) sowie der unterschiedlichen Signaldämpfung \(L({f}_{i})\) verbunden, wobei \( {f}_{i}\) ist die Frequenz des Signals, das sich über die \(i\)-te Route ausbreitet. Es gibt eine Überlagerung von Wellen, die sich auf den verschiedenen Wegen im Stromkreis ausbreiten. Allerdings werden nur einige der Frequenzen verstärkt, um stabile Autooszillationen zu ermöglichen. Es gibt zwei Bedingungen für das Auftreten von Autooszillationen in einer aktiven Ringschaltung9:

Dabei ist \(G\) die vom Verstärker bereitgestellte Verstärkung, \(R\) die Signaldämpfung im elektrischen Teil, \(\Psi\) die Phasenverschiebung des externen elektrischen Teils. Die erste Gl. (1) gibt die Amplitudenbedingung für Autooszillationen an: Die vom Breitbandverstärker bereitgestellte Verstärkung sollte ausreichen, um Verluste im Netz und durch den externen Dämpfer verursachte Verluste zu kompensieren. Die zweite Gleichung gibt die Phasenbedingung für Autooszillationen an: Die gesamte Phasenverschiebung für ein Signal, das durch den Ring zirkuliert, sollte ein Vielfaches von \(2\pi .\) sein. In diesem Fall kommen die Signale bei jeder Ausbreitungsrunde in Phase. Eine genauere Beschreibung der Signalausbreitung in aktiven Ringschaltungen finden Sie in Ref.9.

Das Berechnungsverfahren für TSP ist das folgende. Der externe Phasenschieber \(\Psi\) wird auf den Wert eingestellt

wobei der letzte Term rechts die Summe der Phasenverzögerungen für die ausgewählten Städte ist. In unserem Fall von vier Städten,

Nur Signale, die sich durch die ausgewählten Städte ausbreiten (z. B. A, B, C, D und A), werden verstärkt, da die gesamte Phasenverschiebung durch den Ring \(2\pi\) beträgt. Signale, die sich durch die ausgewählten Städte, aber mehr als eine ausbreiten (z. B. ACBDCA), werden nicht verstärkt, da die gesamte Phasenverschiebung kein Vielfaches von \(2\pi\) ist. Eine detailliertere Erläuterung der selektiven Signalverstärkung in einer aktiven Mehrpfad-Ringschaltung finden Sie in Ref.8. Alle anderen Signale, die sich auf anderen Pfaden ausbreiten (z. B. ABA, ACDA usw.), werden nicht verstärkt, da die Phasenbedingung (2) nicht erfüllt ist.

Dann ist es möglich, mithilfe des externen Dämpfungsglieds \(R\) den kürzesten Pfad (dh den Pfad mit minimalen Verlusten) zu finden. Es kann eine Reihe von Routen geben, für die die gesamte Phasenverschiebung die Gleichung erfüllt. (2). Die Anzahl der Routen, die die Amplitudenbedingung Gl. erfüllen. (1) nimmt mit zunehmender externer Dämpfung \(R\) ab. Der kürzeste Weg verschwindet als letzter, da er die maximale äußere Dämpfung aushalten kann. Im Hinblick auf das Funktionsprinzip möchten wir zwei wichtige Punkte hervorheben. Das System beginnt mit einer Überlagerung aller möglichen Frequenzen, die sich über alle möglichen Pfade ausbreiten. Mit dem externen Phasenschieber können wir nur die Signale verstärken, die durch die ausgewählten Knoten/Städte kommen, um die Phasenbedingung (2) zu erfüllen. Der kürzeste Weg wird dann durch Einführung zusätzlicher Dämpfung gefunden, sodass nur das Signal mit minimalen Verlusten die Amplitudenbedingung (1) erfüllen kann. Im nächsten Abschnitt präsentieren wir die Ergebnisse der numerischen Modellierung zur Veranschaulichung der TSP-Lösung.

Zur Veranschaulichung des oben beschriebenen Lösungsverfahrens präsentieren wir die Ergebnisse der numerischen Modellierung für den Vier-Städte-TSP. In Abb. 3A ist eine Karte der 20 unterhaltsamsten Städte in den USA dargestellt (Quelle WalletHub). Der Handlungsreisende startet in Los Angeles und muss Miami, Washington und Chicago besuchen und dann nach Los Angeles zurückkehren. Die Entfernungen zwischen den Städten werden der Google Map-Anwendung entnommen. Das Problem wird mit dem in Abb. 2 dargestellten kombinatorischen Gerät gelöst. Die Entfernungen zwischen den Städten werden in Signaldämpfung umgerechnet (z. B. 1000 Meilen = 10 dB Dämpfung).

(A) US-Karte mit den 20 unterhaltsamsten Städten. Der Handlungsreisende startet in Los Angeles und muss Miami, Washington und Chicago besuchen und nach Los Angeles zurückkehren. (B) Ergebnisse der numerischen Modellierung, die die Entfernungen für alle möglichen Routen zeigen. Die Routen sind mit #1, #2, … #27 gekennzeichnet. Jeder der Routen ist ein kontinuierliches Sinussignal mit einer bestimmten Frequenz \({f}_{1}\), \({f}_{2},\dots {f}_{27}\) zugeordnet. (C) Ergebnisse der numerischen Modellierung, die Phasenverschiebungen für alle möglichen Routen zeigen. Nur 6 von 27 Routen erfüllen die Phasenbedingung (2) und werden verstärkt. (D) Ergebnisse der numerischen Modellierung zur Darstellung der kürzesten Route(n): Los Angeles–Miami–Washington–Chicago–Los Angeles und Los Angeles–Chicago–Washington–Miami–Los Angeles.

Es gibt 27 mögliche Routen zwischen den vier Städten (z. B. Los Angeles–Washington–Los Angeles–Miami–Washington–Los Angeles). In Abb. 3B sind die Reisedistanzen für alle Routen dargestellt. Die Routen sind mit #1, #2, … #27 gekennzeichnet. Jeder der Routen ist ein kontinuierliches Sinussignal mit einer bestimmten Frequenz \({f}_{1}\), \({f}_{2},\dots {f}_{27}\) zugeordnet. Die Werte dieser Frequenzen sind ohne Bedeutung. Wir gehen davon aus, dass die von den Städten bereitgestellten Phasenverschiebungen nicht von der Signalfrequenz abhängen. Die Lösung des Problems erfolgt in zwei Schritten. In Schritt 1 richten wir den externen Phasenschieber gemäß den Gleichungen ein. (3) und (4). Nur die Strecken, die durch alle vier Städte führen und nach Los Angeles zurückkommen, werden im aktiven Ringkreis verstärkt. In Abb. 3C sind Phasenverschiebungen für alle möglichen Routen dargestellt. Nur 6 von 27 Routen erfüllen die Phasenbedingung (2) und werden verstärkt. In Schritt 2 führen wir eine zusätzliche Dämpfung für den externen Stromkreis ein, sodass nur die Strecke mit minimalen Verlusten Bedingung (2) erfüllen kann. In Abb. 3D sind die Ergebnisse der numerischen Modellierung dargestellt, die die kürzeste(n) von sechs möglichen Routen aus Schritt 1 darstellen. Tatsächlich gibt es immer zwei Routen mit der kürzesten Entfernung. In unserem Fall sind dies Los Angeles–Miami–Washington–Chicago–Los Angeles und Los Angeles–Chicago–Washington–Miami–Los Angeles.

Der oben beschriebene Algorithmus kann auf eine größere Anzahl von Städten erweitert werden. In Abb. 4 sind beispielsweise die Schaltpläne eines Geräts für TSP mit sechs Städten dargestellt. Dem Netz wurden zwei weitere Phasenschieber mit der Bezeichnung E und F hinzugefügt. Diese Schieber liefern \(\pi \times \mathit{Log}\left(11\right)\) bzw. \(\pi \times \mathit{Log}\left(13\right)\) Phasenverschiebungen. Es gibt mehr Verbindungen zwischen den Standorten des Netzes. Jede Verbindung ist ein Wellenleiter, der ein Dämpfungsglied, einen Frequenzfilter und einen Leistungsdetektor umfasst. Der Einfachheit halber sind Dämpfungsglieder, Filter und Detektoren in Abb. 4 nicht dargestellt. In diesem Beispiel sollte der reisende Verkäufer, der von Los Angeles aus startet, Las Vegas, Chicago, Washington, Miami, San Francisco besuchen und nach Los Angeles zurückkehren. Die Karte mit den Städten ist in Abb. 5A dargestellt. Die Tabelle mit den Entfernungen von Stadt zu Stadt finden Sie in den Zusatzmaterialien. Es gibt mehr als 3000 mögliche Routen, wie in Abb. 5B dargestellt. Nicht alle dieser Routen führen durch alle ausgewählten Städte. In Schritt 1 wird der externe Phasenschieber abgestimmt

Schematische Darstellung des kombinatorischen Geräts für TSP mit sechs Städten. Im Vergleich zu Abb. 2 wurden dem Netz zwei weitere Phasenschieber hinzugefügt, die mit E und F gekennzeichnet sind. Diese Schieber liefern \(\pi \times \mathit{Log}\left(11\right)\) bzw. \(\pi \times \mathit{Log}\left(13\right)\) Phasenverschiebungen.

(A) US-Karte mit den 20 unterhaltsamsten Städten. Der reisende Verkäufer sollte von Los Angeles aus Las Vegas, Chicago, Washington, Miami und San Francisco besuchen und nach Los Angeles zurückkehren. (B) Ergebnisse der numerischen Modellierung, die die Entfernungen für alle möglichen Routen zeigen. (C) Ergebnisse der numerischen Modellierung, die Phasenverschiebungen für alle möglichen Routen zeigen. (D) Ergebnisse der numerischen Modellierung zur Darstellung der kürzesten Route(n): Los Angeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Angeles und der Rückwärtsroute: Los Angeles–San Francisco–Las Vegas–Chicago–Washington –Miami–Los Angeles.

Nur Routen, die durch alle Städte führen (dh die Routen, die die erforderliche Phasenverschiebung akkumulieren), werden verstärkt. Die Ergebnisse der numerischen Modellierung in Abb. 5C zeigen die Routen, die Gleichung erfüllen. (1). In Schritt 2 wird eine zusätzliche Dämpfung durch das externe Dämpfungsglied eingeführt. In Abb. 5D sind die kürzesten Routen (d. h. Nr. 320 und Nr. 3062) dargestellt, die Los Angeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Angeles entsprechen, sowie die Route mit der umgekehrten Städtereihenfolge: Los Angeles–San Francisco–Las Vegas–Chicago–Washington–Miami–Los Angeles.

Es ist zu beachten, dass TSP in den oben dargestellten Beispielen unter Verwendung eines allgemeinen Computers gelöst wurde. Alle möglichen Routen wurden einzeln berechnet. Routen mit einer Phasenverschiebung, die Gleichung erfüllt. (1) wurden damals ausgewählt. Aus den Routen mit der richtigen Phase wurde die kürzeste Route ermittelt, indem alle Routen mit der richtigen Phase überprüft wurden. Der Einsatz herkömmlicher Hardware bietet keinen Vorteil gegenüber den bestehenden Algorithmen. Um die TSP-Lösung zu beschleunigen, benötigt man ein Gerät, das Wellenüberlagerung nutzt und alle möglichen Routen parallel prüft.

In diesem Teil präsentieren wir experimentelle Daten, die eine TSP-Lösung für vier Städte zeigen. Für die praktische Umsetzung des in Abb. 2 gezeigten Geräts gibt es eine Vielzahl möglicher Ansätze. Dabei kann es sich um eine Überlagerung mechanischer, akustischer oder elektromagnetischer Wellen handeln, die sich über alle möglichen Wege im Netz ausbreiten. Unser Ansatz zielt darauf ab, die einzigartige Kombination von Eigenschaften zu erforschen, die Spinwellen innewohnen, wobei magnetische Wellenleiter gleichzeitig als Phasenschieber und Frequenzfilter dienen können. Eine Spinwelle ist eine kollektive Schwingung von Spins in einem Spingitter um die Magnetisierungsrichtung. Spinwellen treten in magnetisch geordneten Strukturen auf, und ein Quantum einer Spinwelle wird „Magnon“10 genannt. Aktive Ringschaltungen mit Spinwellen-Verzögerungsleitungen werden häufig als abstimmbare Mikrowellenquellen verwendet11. Hochfrequente Spinwellen breiten sich in magnetischen Wellenleitern viel langsamer aus als elektromagnetische Wellen in Koaxialkabeln. Beispielsweise beträgt die Gruppengeschwindigkeit magnetostatischer Spinwellen in einem einkristallinen Yttrium-Eisen-Granat-Y3Fe2(FeO4)3 (YIG)-Film mit einer Dicke von 7 µm etwa 104 m/s12. Dadurch ist es möglich, große Phasenverschiebungen (z. B. bis zu 2pi) für das sich ausbreitende Signal in Wellenleitern mit Millimeterlänge zu erzielen. Gleichzeitig hängt die Spinwellendispersion stark von der Wellenleitermagnetisierung ab. Spinwellen, die sich entlang der Magnetisierungsrichtung ausbreiten (sogenannte rückwärts gerichtete magnetostatische Volumenspinwellen (BVMSW), und Spinwellen, die sich senkrecht zur Magnetisierungsrichtung ausbreiten (sogenannte magnetostatische Oberflächenspinwellen MSSW), besitzen unterschiedliche Dispersion13. Somit ist sowohl die Phasenverschiebung und das Frequenzfenster für die Spinwellenausbreitung kann durch das lokal angelegte Magnetfeld gesteuert werden. Möglicherweise handelt es sich lediglich um einen Mikromagneten, der oben auf dem YIG-Wellenleiter platziert ist. Das erste Proof-of-the-Concept-Experiment zur Signalreduktion Die Richtung im kombinatorischen Zweipfad-Logikgerät wurde mithilfe einer YIG-basierten aktiven Ringschaltung mit BVMSW und MSSW8 erreicht.

In dieser Arbeit wird das Netz unter Verwendung kommerziell erhältlicher YIG-basierter Frequenzfilter von Micro Lambda Wireless, Inc, Modell MLFD-40540, aufgebaut. Die experimentellen Daten zur Filtertransmission und Phasenverzögerung finden Sie in den ergänzenden Materialien. Die Schaltpläne des Geräts sind in Abb. 6 dargestellt. In Abb. 6A ist die Gesamtansicht des Geräts ähnlich der in Abb. 2 gezeigt. Der Hauptunterschied besteht in der Anzahl der Routen, die die Stadt A mit der verbinden links und die A-Stadt rechts. Es sind neun Bandpassfilter dargestellt. Die Zentralfrequenzen der Filter sind so eingestellt, dass sie drei ausgewählte Frequenzen übertragen: \({f}_{1}=2,441\) GHz, \({f}_{2}=2,514\) GHz und \({f} _{3}=2,595\) GHz. Die Filter sind so zusammengesetzt, dass sie drei Ausbreitungswege bereitstellen: \({f}_{1}\) für ABCDA, \({f}_{2}\) für ACDBA und \({f}_{3}\) für ADBCA. Ziel des Geräts ist es, je nach Dämpfungssatz den kürzesten Weg zu finden. In Abb. 6B sind die Anschlusspläne des Prototypgeräts dargestellt. Es gibt sechs zweikanalige Bandpass-Frequenzfilter, die über Koaxialkabel verbunden sind. Die beiden Buchstaben (z. B. AB, CD usw.) geben den Pfad an, auf dem der Filter eingeführt wird. AB bedeutet beispielsweise, dass der Filter in den Pfad eingeführt wird, der die Städte A und B verbindet. Jeder der Filter führt zu einer Phasenverschiebung des sich ausbreitenden Signals. Diese Tatsache wird ausgenutzt, um die Anzahl der Komponenten in der Schaltung zu minimieren. Die Phasenverzögerung für jede Stadt wird durch die Frequenzfilter eingeführt. Das System wurde so kalibriert, dass die Signale, die sich über die drei Routen ausbreiten, die gleichen Phasenverschiebungen aufweisen. Die Verstärkung im elektrischen Teil erfolgt durch drei in Reihe geschaltete Verstärker (Mini-Circuits, Modell ZX60-83LN-S+). Die Gesamtverstärkung beträgt in allen Versuchen etwa 15 dB. Es gibt einen externen Phasenschieber (ARRA, Modell 9418A), der angepasst wird, um eine Phasenverschiebung von \(\pi /6\) bereitzustellen. Die Phasenbedingung (2) ist für alle drei Routen erfüllt. Experimentelle Daten zur Signalausbreitung finden Sie in den ergänzenden Materialien. Es gibt 12 Dämpfungsglieder im Stromkreis, wobei die Dämpfung in dB proportional zur Entfernung zwischen den Städten ist. Der Leistungsfluss wird mithilfe eines unidirektionalen Kopplers (KRYTAR, Modell 1850) erfasst, der an den 12 ausgewählten Stellen angebracht wird, wie in Abb. 6B dargestellt. Diese Orte sind mit den Nummern 1,2,3 und 4 gekennzeichnet. Die Markierungen haben unterschiedliche Farben (z. B. Rot, Grün und Blau), um Signale zu trennen, die sich auf den Frequenzen \({f}_{1}\), \({ f}_{2},\) bzw. \({f}_{3}\). Die an Port 1 erfasste Leistung entspricht der Eingangsleistung. Die an den Häfen 2, 3 und 4 gemessene Leistung entspricht dem Signal nach Durchquerung der ersten, zweiten und dritten Stadt. Außerdem können die Frequenzspektren der Autooszillation im aktiven Ringkreis mit dem Spektrumanalysator und PNA gemessen werden, wie in Abb. 6B dargestellt. Die Spektren finden Sie in den Zusatzmaterialien.

(A) Gesamtansicht des Prototypgeräts für TSP mit vier Städten. Das Schema umfasst 12 Einzelfrequenz-Bandpassfilter. Die Zentralfrequenzen der Filter sind so eingestellt, dass sie drei ausgewählte Frequenzen übertragen: \({f}_{1}=2,441\) GHz, \({f}_{2}=2,514\) GHz und \({f} _{3}=2,595\) GHz. Die Filter sind so zusammengesetzt, dass sie drei Ausbreitungswege bereitstellen: \({f}_{1}\) für ABCDA, \({f}_{2}\) für ACDBA und \({f}_{3}\) für ADBCA. (B) Anschlussschemata des Prototypgeräts. Die Phasenverzögerung für jede Stadt wird durch die Frequenzfilter eingeführt. Das System wurde so kalibriert, dass die Signale, die sich über die drei Routen ausbreiten, die gleichen Phasenverschiebungen aufweisen. Es gibt 12 Dämpfungsglieder im Stromkreis, wobei die Dämpfung in dB proportional zur Entfernung zwischen den Städten ist. Der Leistungsfluss wird mithilfe eines unidirektionalen Kopplers (Modell) erfasst, der an den 12 ausgewählten Stellen angebracht wird, die mit den Nummern 1,2,3 und 4 gekennzeichnet sind. Die Markierungen haben unterschiedliche Farben (z. B. Rot, Grün und Blau), um die Signale zu trennen Ausbreitung auf den Frequenzen \({f}_{1}\), \({f}_{2},\) bzw. \({f}_{3}\).

In den nächsten drei Beispielen präsentieren wir experimentelle Daten, die die kürzeste Routenfindung in Abhängigkeit vom Satz von Dämpfungsgliedern für verschiedene Pfade demonstrieren. Es ist zu beachten, dass während der Experimente weder die Bandpassfrequenzen noch die Konnektivität noch die Position des externen Phasenschiebers verändert werden.

Experiment 1: In Abb. 7A sind die Werte von Dämpfungsgliedern für verschiedene Pfade dargestellt. Diese Werte werden basierend auf den verfügbaren Komponenten zufällig ausgewählt. Sobald die magnetischen und elektrischen Teile verbunden sind, beginnt das Gerät mit der Suche nach dem Resonanzpfad. Es dauert weniger als 100 \(\mu s\), um in den stabilen Bereich der Autooszillationen zu gelangen. In Abb. 7B sind experimentelle Daten zum Leistungsfluss im Stromkreis dargestellt. Für alle drei möglichen Routen ergibt sich etwa die gleiche Eingangsleistung. Der Großteil des Stroms fließt über die Strecke ACDBA. Es gibt einen Unterschied von mehr als 30 dBm zu den anderen beiden Routen (dh ABCDA und ADBCA), die nicht in Resonanz mit dem elektrischen Teil stehen. Der Ausbreitungsweg ist in Abb. 7C dargestellt. Alle Messungen werden bei Raumtemperatur durchgeführt.

(A) Knoten-zu-Knoten-Dämpfung. (B) Experimentelle Daten zum Kraftfluss im Netz. (C) Der kürzeste Weg ACDBA wird durch die Leistungssensoren dargestellt.

Experiment 2: Als nächstes wurde der Satz der Dämpfungsglieder geändert. In Abb. 8A sind die Werte der Dämpfungsglieder für verschiedene Pfade dargestellt. In Abb. 8B sind experimentelle Daten zum Leistungsfluss im Stromkreis dargestellt. Für alle drei möglichen Routen ergibt sich etwa die gleiche Eingangsleistung. Der Großteil des Stroms fließt über die Route ADBCA. Wie im vorherigen Beispiel gibt es einen Unterschied von mehr als 30 dBm zu den anderen beiden Routen (dh ABCDA und ACDBA). Der Ausbreitungsweg ist in Abb. 8C dargestellt.

(A) Knoten-zu-Knoten-Dämpfung für Beispiel 2. (B) Experimentelle Daten zum Leistungsfluss im Netz. (C) Der kürzeste Weg ADBCA wird durch die Leistungssensoren dargestellt.

Experiment 3: In Abb. 9A ist ein unterschiedlicher Satz von Dämpfungswerten für verschiedene Pfade dargestellt. In Abb. 9B sind experimentelle Daten zum Leistungsfluss im Stromkreis dargestellt. Der Großteil des Stroms fließt über die Route ABCDA. Wie im vorherigen Beispiel gibt es einen Unterschied von mehr als 30 dBm zu den anderen beiden Routen (dh ABCDA und ACDBA). Der Ausbreitungsweg ist in Abb. 9C dargestellt. Es gibt unendlich viele Sets für Dämpfungsglieder, die die Reiseentfernung zwischen den vier Städten nachahmen. In jedem Fall findet das Gerät die kürzeste Route durch alle Städte.

(A) Knoten-zu-Knoten-Dämpfung für Beispiel 2. (B) Experimentelle Daten zum Leistungsfluss im Netz. (C) Der kürzeste Weg ABCDA wird durch die Leistungssensoren dargestellt.

Basierend auf den erhaltenen experimentellen Daten möchten wir mehrere Beobachtungen machen. Der Prototyp des magnischen kombinatorischen Geräts zeigt den kürzesten Ausbreitungsweg durch die ausgewählten Stellen im Netz aus Frequenzfiltern, Phasenschiebern und Dämpfungsgliedern. Es ist von entscheidender Bedeutung, dass die in den Beispielen gezeigte Änderung des Signalausbreitungswegs nur auf die Änderung der Pfaddämpfung zurückzuführen ist. Somit kann das Gerät für alle möglichen Kombinationen von Pfaddämpfungen (Entfernungen) zwischen den Knoten (Städten) eingesetzt werden.

Es gibt einen deutlichen Unterschied im Leistungsfluss über die verschiedenen Routen, der bei Raumtemperatur über 30 dBm liegt. Das aktive Ringschaltungsgerät verstärkt selektiv nur die Routen, die die Resonanzbedingungen (1) und (2) erfüllen. Die Phasenbedingung (2) ermöglicht es uns, die Routen mit der gewünschten akkumulierten Phasenänderung zu extrahieren. Die Amplitudenbedingung (1) ermöglicht es, aus vielen Routen mit derselben akkumulierten Phase nur die kürzeste Route auszuwählen. Bei der numerischen Modellierung ist ein besonderer Schritt erforderlich, um den kürzesten Weg durch Erhöhen der externen Dämpfung \(R\) zu ermitteln. Die Extraktion der kürzesten Route erfolgt im Prototypgerät aufgrund der nichtlinearen Phänomene auf natürliche Weise. Dieser Effekt ist als Modenunterdrückung14,15 bekannt und wird in mechanischen, akustischen und optischen Resonatoren beobachtet. Es erklärt die Energieumverteilung der Leistung zwischen den Modi, wobei der Modus mit der minimalen Dämpfung die meiste Verstärkung erhält. Es kommt nur selten vor, dass der experimentelle Prototyp effizienter arbeitet als das theoretische Gerät zur numerischen Modellierung.

Es ist der Unterschied zwischen dem in Abb. 2 gezeigten allgemeinen Gerät und dem in Abb. 4 gezeigten Prototyp zu beachten. Es wird davon ausgegangen, dass alle Routen, die die A-Stadt links und die A-Stadt rechts verbinden, im verfügbar sind allgemeines Gerät. Wie bereits erwähnt, gibt es „parasitäre“ Routen wie ABA, ACBA, die nicht durch alle Städte führen. Die Auswahl der „richtigen“ Routen erfolgt über den externen Phasenschieber. Mit dem in Abb. 2 dargestellten Gerät kann durch Einstellung des externen Phasenschiebers eine beliebige Route (z. B. ABA, ACDA) gefunden werden. Im Gegensatz dazu gibt es in dem in Abb. 4 gezeigten Gerät nur drei Routen (dh ABCDA, ABDCA und ACBDA). Es ist auch möglich, „parasitäre“ Routen in die Kosten für zusätzliche Frequenzfilter einzubeziehen. Beispielsweise müsste man zwei zusätzliche Frequenzfilter einschließen, die auf die Zentralfrequenz \({f}_{4}\) abgestimmt sind, um eine Routen-ABA zu erhalten.

Für die praktische Umsetzung kombinatorischer Geräte gibt es unterschiedliche Ansätze. Der magnonische Ansatz hat bestimmte Vorteile (z. B. deutliche Phasenverschiebung für HF-Signale in Wellenleitern im Mikrometermaßstab) und Nachteile (z. B. deutliche Spinwellendämpfung). Es könnte möglich sein, optische kombinatorische Geräte mit geringer Dämpfung und schneller Signalausbreitung zu bauen, wenn die ausgeprägte Phasenverzögerung erreicht werden kann. Die Fähigkeit, die klassische Wellenüberlagerung auszunutzen, bietet einen grundlegenden Vorteil gegenüber herkömmlichen digitalen Computern hinsichtlich des funktionalen Durchsatzes. Der funktionale Durchsatz ist eine allgemein akzeptierte Metrik für die Bewertung von Logikgeräten16, die wie folgt definiert werden kann:

Herkömmliche Logikgeräte, die auf der CMOS-Technologie (Complementary Metal-Oxide Semiconductor) basieren, besitzen eine charakteristische Größe im Submikrometerbereich (z. B. 7 nm Kanallänge) und führen einen Vorgang in sehr kurzer Zeit (z. B. einem Bruchteil einer Nanosekunde) aus17. Allerdings können diese booleschen Geräte jeweils nur einen Vorgang ausführen. Im Gegensatz dazu sind kombinatorische Logikgeräte bei der parallelen Suche effizient. Diese Suche über mehrere Routen entspricht der Anzahl nachfolgender Operationen für den Digitalcomputer. Die Anzahl der möglichen Routen in TSP skaliert proportional zu \(\left(n-1\right)!/2.\) Die Berechnungszeit skaliert proportional zu \(n\cdot l/{v}_{g},\ ), wobei \(l\) die Länge des Wellenleiters ist, der die Knoten im Netz verbindet, \({v}_{g}\) die Gruppengeschwindigkeit des Signals. Die Fläche des Netzes skaliert proportional zu \(\sqrt{n}\cdot {l}^{2}\). Der funktionale Durchsatz der kombinatorischen Geräte für TSP kann wie folgt geschätzt werden:

Wenn man die Länge des Wellenleiters mit 10 mm und die Gruppengeschwindigkeit mit \({10}^{4}\) m/s annimmt, steigt der funktionale Durchsatz sprunghaft auf \({10}^{35}\) Ops/ s∙m2, was über den Grenzen der vorhandenen Supercomputer zusammen liegt.

Überraschenderweise gibt es große Ähnlichkeiten bei der Lösung verschiedener Probleme wie der Brücken von Königsberg, TSP und der Primfaktorzerlegung. Die Verwendung von Primzahlen zur Markierung einzigartiger Mesh-Knoten (dh Städte in TSP) sieht sehr effizient aus und garantiert die Eindeutigkeit der über die verschiedenen Routen akkumulierten Phase. Dasselbe Gerät kann wiederum zur Primfaktorzerlegung verwendet werden. Der externe Phasenschieber kann auf \(\Psi =2\pi -\pi Log(X)\) eingestellt werden, wobei \(X\) die zu faktorisierende Zahl ist. Das Gerät findet einen Weg, bei dem die akkumulierte Phase mit der externen Phase übereinstimmt. Die Beispiele der Primfaktorzerlegung mit dem kombinatorischen Logikgerät werden in der vorangegangenen Arbeit8 vorgestellt. In Zukunft könnte es möglich sein, ein universelles kombinatorisches Gerät zu bauen, das eine Vielzahl von NP-schweren und NP-Problemen lösen kann.

Die entscheidende praktische Frage bezieht sich auf die Anzahl der Teile (dh Wellenleiter, Frequenzfilter, Dämpfungsglieder, Leistungsdetektoren) für den Bau eines Geräts für TSP mit einer großen Anzahl von Städten. In Tabelle 1 sind die Schätzungen für die Anzahl der Teile für TSP mit \(n\) Städten aufgeführt. Die Anzahl der Phasenschieber für Städte beträgt \(n+1\). Für die zweite A-Stadt ist ein zusätzlicher Phasenschieber erforderlich. Die Anzahl der Wellenleiter, die die Phasenschieber verbinden, ist gegeben durch

wobei der erste Term auf der rechten Seite die Anzahl der Pfade im klassischen TSP angibt, wie in Abb. 2 gezeigt. Der zweite Term auf der rechten Seite berücksichtigt die zusätzlichen \(\left(n-1\right)\) Wellenleiter für zweite Stadt A. Für TSP mit \(n\) Städten ist die gleiche Anzahl an Dämpfungsgliedern und Leistungsdetektoren erforderlich. Komplizierter ist die Situation bei Frequenzfiltern. In Abb. 6A sind 12 Einzelfrequenz-Bandpassfilter (4 Filter für 3 Routen) dargestellt. Im Prototyp verwendeten wir separate Kabel und Frequenzfilter, um zwei Ausbreitungspfade zwischen einigen Städten (z. B. BC und DC) zu schaffen. Es würde eine enorme Menge \(\left(n-1\right)!\) von Einzelfrequenz-Bandpassfiltern für TSP erfordern, wenn \(n\) Städte diesem Ansatz folgen würden. Im Allgemeinen sollte eine \(i-te\) Route im kombinatorischen Gerät mit einer Häufigkeit \({f}_{i}\) verknüpft sein. Dies führt zur großen Herausforderung des vorgestellten Ansatzes, da die Anzahl der möglichen Routen faktoriell mit der Anzahl der Städte zunimmt. Die Anzahl der unterschiedlichen Frequenzen kann recht groß sein (z. B. 1 M Frequenzen im Frequenzbereich von 0,5 bis 10 GHz mit einem Frequenzabstand von 0,5 MHz). Für die Lösung von TSP mit nur 6–7 Städten reicht es jedoch aus. Dieses Problem kann teilweise dadurch gelöst werden, dass die gleiche Frequenz für sich nicht kreuzende Routen verwendet wird. Das Problem kann vollständig gelöst werden, indem kombinatorische Filter verwendet werden, die Signale übertragen, die Wellen mit einer bestimmten Kombination von Frequenzen umfassen (z. B. \({\{f}_{1}\), \({f}_{2},\) \ ({f}_{5}\), \({f}_{11}\}\) oder \({\{f}_{2}\), \({f}_{4},\ ) \({f}_{7}\), \({f}_{19}\},\) usw.). In diesem Szenario ist die Anzahl der Filter dieselbe wie die Anzahl der Wellenleiter, die durch Gl. (8), wobei jeder Filter eine einzigartige Kombination der Bandpassfrequenzen aufweist. In allen Fällen gibt es nur einen externen Breitbandverstärker, einen externen abstimmbaren Phasenschieber und einen externen abstimmbaren Dämpfer.

Es ist zu beachten, dass jedes neue Problem eine Schaltungsanpassung oder Neukonfiguration erfordert. Beispielsweise kann die in dieser Arbeit vorgestellte Schaltung für vier Städte für jeden anderen TSP mit vier Städten verwendet werden. Man muss die Dämpfung entsprechend den Entfernungen zwischen den Städten anpassen. Dies kann mit spannungsabstimmbaren Dämpfungsgliedern erfolgen. Die Zunahme der Anzahl der Städte erfordert eine Erhöhung der Anzahl der Phasenschieber in der Schaltung. Allerdings können TSP-Schaltungen für eine kleinere Anzahl von Städten verwendet werden, ohne dass Komponenten entfernt/hinzugefügt werden müssen. Beispielsweise kann TSP mit acht Städten zur Lösung von Problemen für acht, sieben, sechs, fünf und vier Städte verwendet werden.

Eine weitere praktische Herausforderung besteht in der Genauigkeit der Teile im Hinblick auf die Anzahl der Städte. Der Unterschied in den Entfernungen zwischen den Städten kann sich bei TSPs mit einer großen Anzahl von Städten deutlich verringern. Der Genauigkeit der Dämpfungsreglersteuerung sind physikalische Grenzen gesetzt. Außerdem verringert die Zunahme möglicher Ausbreitungsrouten zwangsläufig den Unterschied in der akkumulierten Phase für verschiedene Routen. Dies führt wiederum zu dem Problem, für viele Städte den kürzesten Weg zu finden. Die Erhöhung der Präzision von Messungen/Berechnungen ist ein häufiges Problem für TSP mit einer großen Anzahl von Städten, die mit heuristischen Algorithmen angegangen werden können18. Für die Leistungsdetektoren ist eine geringere Genauigkeit erforderlich. Unabhängig von der Anzahl der Städte kann ein deutlicher Unterschied im Leistungsfluss (z. B. 20 dB Unterschied zwischen aktiver und passiver Route) erreicht werden. Es gibt gewisse Vor- und Nachteile der Verwendung magnischer Schaltkreise für TSP. Einerseits sorgen Spinwellen für markante Phasenverschiebungen auf millimeterlangen Wellenleitern. Andererseits erschwert die Spinwellendispersion die Schaltungstechnik erheblich. Außerdem besitzen Spinwellen im Vergleich zu optischen Wellen eine viel stärkere Wechselwirkung. Beispielsweise können sich Spinwellen, die sich in orthogonalen Richtungen durch den Übergang ausbreiten, gegenseitig vollständig reflektieren19. Dies stellt ein zusätzliches Problem für Spinwellenverbindungen dar. Diese und viele andere Fragen verdienen besondere Aufmerksamkeit.

Wir haben einen Ansatz zur TSP-Lösung unter Verwendung kombinatorischer Geräte beschrieben. Das Funktionsprinzip basiert auf der klassischen Wellenüberlagerung, wobei jede Welle einem Handlungsreisenden entspricht. Die Wellen breiten sich durch ein Netz aus Wellenleitern aus, wobei Phasenschieber die Städte im TSP darstellen und der Abstand zwischen den Städten in der Signaldämpfung kodiert wird. Nur Wellen, die durch die ausgewählten Städte kommen und die spezifische Phasenverschiebung akkumulieren, werden verstärkt. Am stärksten verstärkt wird die Welle, die sich mit minimaler Dämpfung durch die Strecke ausbreitet. Die TSP-Lösung wird durch numerische Modellierung veranschaulicht und experimentell demonstriert. Der erste Prototyp ist ein mehrpfadiger magnischer aktiver Ringkreis, der magnetische Phasenschieber, Frequenzfilter und Dämpfungsglieder umfasst. Der Signalausbreitungsweg wird über den Leistungsdetektor erfasst. Wir haben drei Beispiele für drei verschiedene Sätze von Dämpfungsgliedern/Stadt-zu-Stadt-Entfernungen vorgestellt. Das Gerät findet buchstäblich die kürzeste Ausbreitungsroute durch die Städte. Der Betrieb ist robust, da der Leistungsunterschied zwischen den aktiven und passiven Routen 30 dBm übersteigt. Alle Experimente werden bei Raumtemperatur durchgeführt. Diese Arbeit ist ein Schritt in Richtung kombinatorischer Logikgeräte für die Datenverarbeitung spezieller Aufgaben. Potenziell können kombinatorische Geräte im Vergleich zu herkömmlichen digitalen Geräten einen grundlegenden Vorteil beim Funktionsdurchsatz bieten. Die Fähigkeit, die klassische Überlagerung von Wellen zu nutzen, ist der Hauptvorteil und die attraktivste Eigenschaft des vorgestellten Ansatzes.

Alle während dieser Studie generierten oder analysierten Daten sind in diesem veröffentlichten Artikel enthalten.

Biggs, N., Lloyd, EK & Wilson, RJ Graphentheorie, 1736–1936. Isis 70, 164–165. https://doi.org/10.1086/352170 (1979).

Artikel MATH Google Scholar

Ungureanu, V. Problem des reisenden Verkäufers mit dem Transport. Berechnen. Wissenschaft. J. Mold. 14, 202–206 (2006).

MATH Google Scholar

Fuentes, GEA, Gress, ESH, Mora, J. & Marin, JM Lösung des Job-Shop-Planungsproblems durch das Problem des Handlungsreisenden. Rev. Iberoam. Autom. Informieren. Ind. 13, 430–437. https://doi.org/10.1016/j.riai.2016.07.003 (2016).

Artikel Google Scholar

Gusfield, D. & Gusfield, D. Travelling Salesman Problems in Genomics (Cambridge Univ Press, 2019).

Buchen Sie MATH Google Scholar

Aarts, EHL & Korst, JHM Boltzmann-Maschinen für Probleme von Handlungsreisenden. EUR. J. Oper. Res. 39, 79–95. https://doi.org/10.1016/0377-2217(89)90355-x (1989).

Artikel MATH Google Scholar

Collings, N., Sumi, R., Weible, KJ, Acklin, B. & Xue, W. InInternational Topical Meeting on Optical Computing (Oc 92). 637–641 (Spie-Int Soc Optical Engineering, 1993).

Saud, S., Kodaz, H. & Babaoglu, I. Auf der 9. Internationalen Konferenz über Fortschritte in der Informationstechnologie (IAIT). 17–32 (Knowledge E, 2018).

Khitun, A. & Balinskiy, M. Kombinatorische Logikgeräte basierend auf einer aktiven Mehrpfad-Ringschaltung. Wissenschaft. Rep. https://doi.org/10.1038/s41598-022-13614-2 (2022).

Artikel PubMed PubMed Central Google Scholar

Tiberkevich, VS, Khymyn, RS, Tang, HX & Slavin, AN Empfindlichkeit gegenüber externen Signalen und Synchronisationseigenschaften eines nicht-isochronen Autooszillators mit verzögerter Rückkopplung. Wissenschaft. Rep. https://doi.org/10.1038/srep03873 (2014).

Artikel PubMed PubMed Central Google Scholar

Kittel, C. Einführung in die Festkörperphysik 8. Aufl. (Wiley, 2005).

MATH Google Scholar

Chumak, AV, Serga, AA & Hillebrands, B. Magnonische Kristalle für die Datenverarbeitung. J. Phys. D-Appl. Physik. 50, 1–20. https://doi.org/10.1088/1361-6463/aa6a65 (2017).

Artikel CAS Google Scholar

Balinskiy, M. et al. Spinwelleninterferenz im YIG-Kreuzübergang. Aip Adv. https://doi.org/10.1063/1.4974526 (2017).

Artikel Google Scholar

Gurevich, AG & Melkov, GA Magnetization Oscillations and Waves 147–176 (CRC Press, 1996).

Google Scholar

Okusaga, O. et al. Im Jahr 2010 IEEE International Frequency Control Symposium. 539–543 (IEEE, 2010).

Carroll, JM & Chang, K. Ringresonator zur Unterdrückung des Mikrostreifenmodus. Elektron. Lette. 30, 1861–1862. https://doi.org/10.1049/el:19941291 (1994).

Artikel ADS Google Scholar

Nikonov, DE & Young, IA Einheitliche Methodik für das Benchmarking von über CMOS hinausgehenden Logikgeräten. Im Jahr 2012 IEEE International Electron Devices Meeting (IEDM 2012), vol. 25, https://doi.org/10.1109/iedm.2012.6479102 (2012).

Hoefflinger, B. In Chips 2020, Bd. 2: New Vistas in Nanoelectronics Frontiers Collection (Hrsg., Hoefflinger, B.) 143–148 (Springer, 2016).

Syambas, NR, Salsabila, S., Suranegara, GM & IEEE. Auf der 11. Internationalen Konferenz über Dienste und Anwendungen von Telekommunikationssystemen (TSSA). (IEEE, 2017).

Balynskiy, M. et al. Reversible magnetische Logikgatter basierend auf Spinwelleninterferenz. J. Appl. Physik. https://doi.org/10.1063/1.5011772 (2018).

Artikel Google Scholar

Referenzen herunterladen

Diese Arbeit von M. Balinskiy und A. Khitun wurde teilweise von der INTEL CORPORATION unter der Preisnummer 008635, Projektleiter Dr. DE Nikonov, und von der National Science Foundation (NSF) unter der Preisnummer 2006290, Programmleiter Dr. S., unterstützt . Basu. Die Autoren danken Dr. DE Nikonov für die wertvollen Diskussionen.

Fakultät für Elektrotechnik und Informationstechnik, University of California-Riverside, Riverside, CA, 92521, USA

Mykhaylo Balinskyy & Aleksandr Khitun

Sie können diesen Autor auch in PubMed Google Scholar suchen

Sie können diesen Autor auch in PubMed Google Scholar suchen

AK konzipierte die Idee kombinatorischer magnonischer Geräte für TSP und schrieb das Manuskript, MB baute den Prototyp und führte die Experimente durch. Alle Autoren diskutierten die Daten und trugen zur Manuskripterstellung bei.

Korrespondenz mit Aleksandr Khitun.

Die Autoren geben an, dass keine Interessenkonflikte bestehen.

Springer Nature bleibt neutral hinsichtlich der Zuständigkeitsansprüche in veröffentlichten Karten und institutionellen Zugehörigkeiten.

Open Access Dieser Artikel ist unter einer Creative Commons Attribution 4.0 International License lizenziert, die die Nutzung, Weitergabe, Anpassung, Verbreitung und Reproduktion in jedem Medium oder Format erlaubt, sofern Sie den/die ursprünglichen Autor(en) und die Quelle angemessen angeben. Geben Sie einen Link zur Creative Commons-Lizenz an und geben Sie an, ob Änderungen vorgenommen wurden. Die Bilder oder anderes Material Dritter in diesem Artikel sind in der Creative Commons-Lizenz des Artikels enthalten, sofern in der Quellenangabe für das Material nichts anderes angegeben ist. Wenn Material nicht in der Creative-Commons-Lizenz des Artikels enthalten ist und Ihre beabsichtigte Nutzung nicht gesetzlich zulässig ist oder über die zulässige Nutzung hinausgeht, müssen Sie die Genehmigung direkt vom Urheberrechtsinhaber einholen. Um eine Kopie dieser Lizenz anzuzeigen, besuchen Sie http://creativecommons.org/licenses/by/4.0/.

Nachdrucke und Genehmigungen

Balinskyy, M., Khitun, A. Lösung des Problems des Handlungsreisenden mithilfe eines magnischen kombinatorischen Geräts. Sci Rep 13, 11708 (2023). https://doi.org/10.1038/s41598-023-38839-7

Zitat herunterladen

Eingegangen: 17. März 2023

Angenommen: 16. Juli 2023

Veröffentlicht: 20. Juli 2023

DOI: https://doi.org/10.1038/s41598-023-38839-7

Jeder, mit dem Sie den folgenden Link teilen, kann diesen Inhalt lesen:

Leider ist für diesen Artikel derzeit kein gemeinsam nutzbarer Link verfügbar.

Bereitgestellt von der Content-Sharing-Initiative Springer Nature SharedIt

Durch das Absenden eines Kommentars erklären Sie sich damit einverstanden, unsere Nutzungsbedingungen und Community-Richtlinien einzuhalten. Wenn Sie etwas als missbräuchlich empfinden oder etwas nicht unseren Bedingungen oder Richtlinien entspricht, kennzeichnen Sie es bitte als unangemessen.