Dies ist der fünfte Artikel in einer siebenteiligen Reihe über Algorithmen und Berechnungen, in der untersucht wird, wie wir einfache Binärzahlen verwenden, um unsere Welt mit Strom zu versorgen. Der erste Artikel Wie Algorithmen die Welt steuern, in der wir leben , kann gefunden werden hier .
Die wesentliche Aufgabe eines theoretischen Informatikers besteht darin, effiziente Algorithmen für Probleme zu finden. Die schwierigsten dieser Probleme sind nicht nur akademische, sondern bilden den Kern einiger der herausforderndsten Szenarien der realen Welt, die sich jeden Tag abspielenDas kritischste davon ist das Problem der Optimierung: Wie finden wir das am besten Lösung eines Problems, wenn wir scheinbar unendlich viele mögliche Lösungen haben?
VERBINDUNG: NEUER ALGORITHMUS ERMÖGLICHT AUTONOMEN AUTOS, SPUREN WIE MENSCHEN ZU ÄNDERN
Im Moment können wir nur einen heuristischen Ansatz wählen und a gut genug Lösung, aber wir schaffen ein unkalkulierbares Maß an Ineffizienzen, die sich im Laufe der Zeit summieren und unsere endlichen Ressourcen erschöpfen, die anderswo besser genutzt werden könnten. Wir nennen dies das Problem des Handlungsreisenden, und es ist keine Untertreibung zu sagen, dass die Lösung dafür istDieses Problem könnte unserer Wirtschaft Billionen von Dollar ersparen.
Das Problem des Handlungsreisenden, die exponentielle Zeitkomplexität und darüber hinaus
Das Problem des Handlungsreisenden wird folgendermaßen beschrieben: ein Unternehmen erfordert, dass einer der reisenden Verkäufer jede Stadt auf einer Liste von besucht n Städte, in denen die Entfernungen zwischen einer Stadt und jeder anderen Stadt auf der Liste bekannt sind. Jede Stadt kann nur einmal besucht werden und der Verkäufer endet in der Stadt, von der aus er gestartet ist. Was ist der kürzeste Weg, den er gehen kann, um dies zu erreichen?
Der effizienteste Algorithmus, den wir für dieses Problem kennen, läuft in Exponentialzeit was ziemlich brutal ist, wie wir gesehen haben. Im Gegensatz zur RSA-Verschlüsselung gibt es im Fall des Travelling Salesman-Problems keine modulare Arithmetik oder Umwandlung der Faktorisierung in Periodenfindung, wie dies Shors Algorithmus tut. Das Travelling Salesman-Problem ist eine EntscheidungProblem, und es gibt keine Abkürzungen, von denen wir wissen, dass sie uns unter exponentielle Zeitkomplexität .
Um zu verdeutlichen, warum dies eine schreckliche Situation ist, verwenden wir ein sehr verbreitetes Beispiel dafür, wie verrückt es ist. exponentielle Zeitkomplexität kann bekommen. Nehmen wir an, Sie könnten ein Stück Papier immer wieder so oft falten, wie Sie möchten, und das hat immer so viel Länge wie nötig, um die Falte zu machen. Messen Sie die Breite des Stapels von "Blättern""In dem Endprodukt, in dem das gefaltete Papier von uns weg in der Länge wächst, ist dies das, was Sie erwarten können :
* 0 Falten : 1 / 250stel Zoll dick.
* 10 Falten : ~ 2,05 Zoll dick.
* 25 Falten : ~ 1 Meile dick.
* 43 Falten : Die Oberfläche des Mondes.
* 52 Falten : In der Sonne.
* 57 Falten : Passing Ultima Thule
* 67 Falten : Es dauert 1,5 Jahre, um von einem Ende zum anderen zu gelangen.
* 82 Falten : So breit wie die Milchstraße.
* 93 Falten : In astronomischer Wurfweite des supermassiven Schwarzen Lochs im Zentrum von Messier 87.
* 101 Falten : Nicht sicher, was da ist, weil es jenseits des beobachtbaren Universums liegt.
Und das ist mit dem am besten Algorithmus, den wir gerade haben. Jedes dieser "Blätter" in diesem Stapel ist ein Weg, den der Verkäufer nehmen könnte dessen Länge am Ende wir alle anderen Routenlängen überprüfen und messen müssten, und jede Falte entspricht dem Hinzufügen einer zusätzlichen Stadt zur Liste der Städte, die er besuchen muss. Wenn wir nur versucht haben, das Problem zu lösenTravelling Salesman Problem durch Überprüfen jeder möglichen Lösung, um die beste zu finden, die wir uns ansehen faktorielle Zeitkomplexität. Mit unserem 128-Bit Nummer aus unserem RSA-Verschlüsselungsbeispiel, die 2 war 128 während 101 Falten nur 2 sind 101 , 35! bläst vorbei 2 128 um mindestens den Faktor 100. Mit jedem zusätzlichen Schritt in Ihrer Eingabe wird es nur noch schlimmer, und das macht das Problem des Handlungsreisenden so wichtig und auch so verrückt.
Das Problem der Optimierungsalgorithmen
Wir wissen nicht, wie wir die richtige Antwort auf das Problem des Handlungsreisenden finden sollen, denn um die beste Antwort zu finden, müssen Sie alle anderen Antworten ausschließen, und wir haben keine Ahnung, wie dies zu tun ist, ohne alle Möglichkeiten oder zu prüfenUm die kürzeste bisher gefundene Route aufzuzeichnen und von vorne zu beginnen, sobald unsere aktuelle Route diese Zahl überschreitet. Das ist das Beste, was wir haben, und das bringt die Dinge nur auf den Punkt. exponentielle Zeitkomplexität Als Lösung ist es also überhaupt keine gute Lösung.
Das Problem des Handlungsreisenden ist aus vielen Gründen etwas Besonderes, aber das wichtigste ist, dass es sich um ein Optimierungsproblem handelt und Optimierungsprobleme im täglichen Leben überall auftreten. In Bezug auf die Eingabegrößen ist 101 überhaupt nicht sehr groß.In der realen Welt gibt es so viele kleine Städte in einem einzigen US-Bundesstaat, die theoretisch Teil des Liefergebiets eines großen kommerziellen Händlers sein könnten. Das Herausfinden des kürzesten Weges zwischen allen Haltestellen, die ihre Lastwagen täglich zu verschiedenen Kunden fahren müssen, würde eine unkalkulierbare Menge an Arbeits- und Kraftstoffkosten sparen.
Wenn Sie Teile aus Übersee für Ihre Fabrik beziehen, welche Route und Kombination von Liefermethoden kostet Sie am wenigsten Geld? Welche Konfiguration von Proteinfalten kann Krebs besiegen? Finden eines Algorithmus, der das Problem des Handlungsreisenden in einer ähnlichen Umgebung lösen kann Polynomzeit würde alles ändern und dies über Nacht tun.
Ein Teil des Problems ist jedoch, dass wir aufgrund der Art des Problems selbst nicht einmal wissen, ob eine Lösung vorliegt. Polynomzeit ist mathematisch möglich. Dies liegt an der Art und Weise, wie wir Probleme klassifizieren, und das Problem des Handlungsreisenden gehört zu einer ganz besonderen Klassifizierung in diesem System, die eine der größten Herausforderungen in Mathematik und Informatik darstellt und weitreichende Auswirkungen auf dieechte Welt.
Der sechste Artikel in unserer Reihe über Algorithmen und Berechnungen P Vs. NP, NP-Complete und der Algorithmus für alles , kann gefunden werden hier .