Ich weiß, dass exponentielle Zeitalgorithmen generell vermieden werden sollten, aber manchmal notwendig sind. Ein Fall ist der reisende Verkäufer. Wie häufig sind solche Algorithmen in Produktionssoftware? Sind diese Fälle normalerweise notwendig oder das Ergebnis von Eilaufträgen? Ich verstehe, dass viele mit einer guten Heuristik gelöst werden können. Was wird normalerweise mit denen gemacht, die es nicht können?
algorithms
Weltingenieur
quelle
quelle
Antworten:
Etwas , das nicht in Produktionssoftware aber getan auf Produktions - Software ist die formale Verifikation . Es wird wahrscheinlich nicht für die meisten Kundensoftware übernommen, gewinnt jedoch für eingebettete Systeme und Treiber an Bedeutung, dh für Hard- und Software, deren Korrektheit wichtig (und nachvollziehbar) ist.
Die tatsächlich berechenbaren Überprüfungsprobleme (Barriere Nr. 1) sind häufig EXPTIME- schwer. In den glücklicheren Fällen treten PSPACE- vollständige Probleme auf (Barriere Nr. 2). Beide Klassen sind (vermutlich) schwieriger als NP-vollständige Probleme, die im Vergleich einfach sind. Doppelt exponentielle Probleme werden ebenfalls leicht erhalten.
In diesen Fällen wird die Heuristik (im Sinne des Endergebnisses) nicht abgeschnitten, da Sie eindeutige Ergebnisse benötigen. Deshalb braucht man große Maschinen und Zeit. Es gibt Heuristiken (im Sinne einer alternativen Auswahl), die häufig zu einer kürzeren Laufzeit führen (dh eine clevere Suche im Suchraum, wenn nach Fehlerzuständen gesucht wird), aber im schlimmsten Fall können Sie nur warten. Oder Sie können einen Stift-Papier-Proof erstellen und ihn maschinell überprüfen lassen , was rechnerisch einfacher ist.
quelle
Der häufig verwendete Algorithmus mit exponentieller Worst-Case-Komplexität ist die in der linearen Programmierung verwendete Simplex-Methode . Was jedoch die generische Komplexität dieser Methode ist, ist ein offenes Problem. Mit einigen spezifischen Annahmen ist es Polynom.
quelle
Programmiersprachendolmetscher sind schlechter als die exponentielle Zeit (in der Länge ihrer Eingabe, dh in der Länge des Programms, das sie interpretieren), und sie sind ziemlich häufig. Ein anderes Beispiel ist das automatische Beweisen von Theoremen / das Lösen von Beschränkungen / das Lösen von Sätzen / die lineare Programmierung von ganzen Zahlen. Ein weiteres Beispiel ist die symbolische Differenzierung, wie sie beispielsweise in Maple / Mathematica implementiert ist (obwohl es möglich ist, eine symbolische Differenzierung in linearer Zeit durchzuführen, wenn Sie Unterausdrücke zwischen Knoten teilen dürfen).
quelle
Lassen Sie mich das Beispiel eines Problems mit reisenden Verkäufern nehmen. Ich habe ein paar Mal daran gearbeitet.
Es gibt einige Male, in denen ich in einem Team war, das eine Lösung für das Problem eines reisenden Verkäufers geschrieben hat, aber mit einigen weiteren Parametern. Zum Beispiel könnte es sich um ein Geschäft mit einer Flotte von Technikern und Ingenieuren handeln, die jeweils über einzigartige Fähigkeiten verfügen. Die Ziele werden jeden Tag in Form von Serviceanfragen angezeigt. Alle Programme sind in Produktion, obwohl sie seit dem ursprünglichen Schreiben geändert und gewartet wurden.
So haben sie gearbeitet. Jeder Ingenieur erhielt täglich eine Liste mit Wartungsarbeiten an einem Handgerät. Wenn sie jede Serviceaufgabe abgeschlossen haben, sollten sie den Fall schließen. Die Fälle, die ausgelassen werden, schließen sich den Fällen an, die für den nächsten Tag mit etwas höherer Priorität geplant werden sollen, da der Kunde bis dahin eine gewisse Unzufriedenheit geäußert hätte. Es gab eine Vielzahl von Gründen, warum ein Ingenieur nicht an einem Fall teilnehmen würde. Verkehrsprobleme waren am häufigsten.
Wie häufig sind sie? Mindestens so häufig wie die Anzahl der Kundendienstanfragen von Kunden. Ohne Kundendienst wird es beispielsweise schwierig sein, Kunden zu binden, und es wird schwieriger, neue Kunden zu gewinnen.
Bei vielen webbasierten Geschäften wie Amazon und anderen Buchhandlungen und anderen Geschäften, die gut im Geschäft sind, würde ich denken, dass reisende Verkäufer häufiger sind als früher. Es kann auch viele Variationen des Problems der reisenden Verkäufer geben, die in Lehrbüchern gelehrt werden.
quelle