Angenommen, Sie haben eine Sendung. Es muss von Punkt A zu Punkt B, Punkt B zu Punkt C und schließlich Punkt C zu Punkt D gehen. Sie brauchen es, um in fünf Tagen dorthin zu gelangen, wo das geringste Geld möglich ist. Es gibt drei mögliche Versender für jedes Bein, jedes mit seinen eigenen unterschiedlichen Zeiten und Kosten für jedes Bein:
%Vor%Wie würden Sie die programmatisch beste Kombination finden?
Mein bisher bester Versuch (dritter oder vierter Algorithmus) ist:
Schnell in PHP gespottet (beachte, dass das Test-Array unten gut funktioniert, aber wenn du es mit dem Test-Array von oben versuchst, findet es nicht die richtige Kombination):
%Vor%Ich denke, ich muss tatsächlich irgendwas machen, wo ich buchstäblich jede Kombination einzeln mache (mit einer Reihe von Loops) und die Gesamtpunktzahl von jedem zusammenaddiere und den besten finde ... .
BEARBEITEN: Zur Klarstellung, dies ist keine Hausaufgabenaufgabe (ich bin nicht in der Schule). Es ist Teil meines aktuellen Projekts bei der Arbeit.
Die Anforderungen haben sich (wie immer) ständig geändert. Wenn ich zu dem Zeitpunkt, als ich anfing, an diesem Problem zu arbeiten, die aktuellen Einschränkungen erhalten habe, würde ich eine Variante des A * -Algorithmus (oder Dijkstra's oder kürzesten Pfad oder Simplex oder etwas) verwenden. Aber alles hat sich verändert und verändert, und das bringt mich dahin, wo ich gerade bin.
Also ich denke, das bedeutet, ich muss den ganzen Mist vergessen, den ich bis zu diesem Punkt gemacht habe, und gehe einfach mit dem, was ich weiß, mit dem ich gehen sollte, was ein Pfadfindungsalgorithmus ist.
Könnte einige der Algorithmen für den kürzesten Pfad , wie Dijkstras, ändern, um jeden Pfad nach Kosten zu gewichten, aber auch zu verfolgen Zeit und stoppen Sie einen bestimmten Weg zu gehen, wenn die Zeit Ihre Schwelle überschreitet. Sollte das billigste finden, das Sie auf diese Weise unter Ihre Schwelle bringt.
Klingt wie das, was Sie haben, wird ein "lineares Programmierproblem" genannt. Es klingt auch wie ein Hausaufgabenproblem, nichts für ungut.
Die klassische Lösung eines LP-Problems heißt "Simplex-Methode". Google es.
Um diese Methode jedoch verwenden zu können, müssen Sie das Problem korrekt formuliert haben, um Ihre Anforderungen zu beschreiben.
Trotzdem ist es möglich, alle möglichen Pfade aufzulisten, da Sie eine so kleine Menge haben. So etwas wird jedoch nicht skalieren.
Klingt wie ein Job für Dijkstra-Algorithmus :
Der Dijkstra-Algorithmus, der 1959 vom niederländischen Informatiker Edsger Dijkstra konzipiert wurde, 1 ist ein Graphsuchalgorithmus, der löst das Single-Source-Shortest-Path-Problem für einen Graphen mit nicht negativen Randpfadkosten, Ausgabe eines kürzesten Pfadbaums. Dieser Algorithmus wird oft beim Routing verwendet.
Es gibt auch Implementierungsdetails im Wikipedia-Artikel.
Wenn ich wüsste, dass ich nur in einer vorgegebenen Reihenfolge mit fünf Städten zu tun hätte und es nur drei Routen zwischen benachbarten Städten gäbe, würde ich es brutal erzwingen. Es hat keinen Sinn, elegant zu sein.
Wenn dies andererseits eine Hausaufgabe wäre und ich einen Algorithmus erstellen müsste, der tatsächlich skalieren könnte, würde ich wahrscheinlich einen anderen Ansatz wählen.
Wie Baltimark sagte, ist das im Grunde ein lineares Programmierproblem. Wenn nur die Koeffizienten für die Verlader (1 für enthalten, 0 für nicht enthalten) keine (binären) ganzen Zahlen für jedes Bein wären, wäre dies leichter lösbar. Jetzt müssen Sie einige (binäre) Ganzzahl-Linear-Programmierung (ILP) Heuristiken finden, da das Problem NP-schwer ist. Siehe Wikipedia über lineare lineare Programmierung für Links; auf meinem linearen Programmierkurs verwendeten wir mindestens Branch und bound .
Nun, da ich darüber nachdenke, ist dieser spezielle Fall ohne tatsächliche ILP lösbar, da die Anzahl der Tage keine Rolle spielt, solange es & lt; = 5 ist. Jetzt beginnen Sie mit der Auswahl des günstigsten Trägers für die erste Wahl (Conway 5) : 1000). Als nächstes wählen Sie wieder die billigsten, resultierenden 8 Tage und 4000 Währungseinheiten, was zu viel ist, so dass wir das abbrechen. Indem wir auch andere ausprobieren, sehen wir, dass sie alle Tage ergeben & gt; 5, also gehen wir zurück zur ersten Wahl und versuchen die zweitgünstigste (FedEx 2: 3000) und dann ups in der zweiten und fedex in der letzten. Dies gibt uns insgesamt 4 Tage und 9000 Währungseinheiten.
Wir könnten dann diese Kosten verwenden, um andere Suchvorgänge in der Baumstruktur zu bereinigen, die um einige sub-stufige Ergebnisse größer wären als die, die wir bereits gefunden haben, und diesen Teilbaum von diesem Punkt an nicht durchsucht. Dies funktioniert nur so lange, wie wir wissen, dass die Suche im Teilbaum keine besseren Ergebnisse liefert, wie hier, wenn die Kosten nicht negativ sein können.
Ich hoffe, dass diese Wanderung ein wenig geholfen hat :).
Dies ist ein Rucksackproblem . Die Gewichte sind die Tage auf der Durchreise, und der Gewinn sollte 5000 $ - Kosten der Bein sein. Beseitigen Sie alle negativen Kosten und gehen Sie von dort aus!
Ich denke, dass der Algorithmus von Dijkstra den kürzesten Weg sucht.
cmcculloh sucht nach den minimalen Kosten, die der Beschränkung unterliegen, dass er es dort in 5 Tagen bekommt.
Also, nur den schnellsten Weg zu finden wird ihn nicht am billigsten dorthin bringen, und dorthin für das billigste zu kommen, wird es in der erforderlichen Menge an Zeit dort nicht bekommen.
Tags und Links algorithm php combinations puzzle np-complete