Finden Sie die beste Kombination aus einer bestimmten Menge mehrerer Sätze

Question

Angenommen, Sie haben eine Lieferung.Es muss von Punkt A nach Punkt B, von Punkt B nach Punkt C und schließlich von Punkt C nach Punkt D gehen.Sie benötigen es, um in fünf Tagen für möglichst wenig Geld dorthin zu gelangen.Für jede Etappe gibt es drei mögliche Versender mit jeweils unterschiedlichen Zeiten und Kosten für jede Etappe:

Array
(
    [leg0] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 5000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 5
                    [cost] => 1000
                )

        )

    [leg1] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 3
                    [cost] => 1000
                )

        )

    [leg2] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 4000
                )

            [FedEx] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 2
                    [cost] => 5000
                )

        )

)

Wie würden Sie programmatisch die beste Kombination finden?

Mein bisher bester Versuch (dritter oder vierter Algorithmus) ist:

1. Finden Sie den längsten Versender für jede Etappe
2. Eliminieren Sie das „teuerste“.
3. Finden Sie für jede Strecke den günstigsten Versender
4. Berechnen Sie die Gesamtkosten und Tage
5. Wenn die Tage akzeptabel sind, beenden Sie den Vorgang, andernfalls gehen Sie zu 1

Schnell in PHP nachgebildet (beachten Sie, dass das Testarray unten problemlos funktioniert, aber wenn Sie es mit dem Testarray von oben versuchen, findet es nicht die richtige Kombination):

$shippers["leg1"] = array(
    "UPS"    => array("days" => 1, "cost" => 4000),
    "Conway" => array("days" => 3, "cost" => 3200),
    "FedEx"  => array("days" => 8, "cost" => 1000)
);

$shippers["leg2"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);

$shippers["leg3"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);    

$times = 0;
$totalDays = 9999999;

print "<h1>Shippers to Choose From:</h1><pre>";
print_r($shippers);
print "</pre><br />";

while($totalDays > $maxDays && $times < 500){
            $totalDays = 0;
            $times++;
            $worstShipper = null;
            $longestShippers = null;
            $cheapestShippers = null;

            foreach($shippers as $legName => $leg){
                //find longest shipment for each leg (in terms of days)
                unset($longestShippers[$legName]);
                $longestDays = null;        

                if(count($leg) > 1){
                    foreach($leg as $shipperName => $shipper){
                        if(empty($longestDays) || $shipper["days"] > $longestDays){
                            $longestShippers[$legName]["days"] = $shipper["days"];
                            $longestShippers[$legName]["cost"] = $shipper["cost"];
                            $longestShippers[$legName]["name"] = $shipperName;
                            $longestDays = $shipper["days"];
                        }
                    }           
                }
            }

            foreach($longestShippers as $leg => $shipper){
                $shipper["totalCost"] = $shipper["days"] * $shipper["cost"];

                //print $shipper["totalCost"] . " &lt;?&gt; " . $worstShipper["totalCost"] . ";";

                if(empty($worstShipper) || $shipper["totalCost"] > $worstShipper["totalCost"]){
                    $worstShipper = $shipper;
                    $worstShipperLeg = $leg;
                }
            }

            //print "worst shipper is: shippers[$worstShipperLeg][{$worstShipper['name']}]" . $shippers[$worstShipperLeg][$worstShipper["name"]]["days"];
            unset($shippers[$worstShipperLeg][$worstShipper["name"]]);

            print "<h1>Next:</h1><pre>";
            print_r($shippers);
            print "</pre><br />";

            foreach($shippers as $legName => $leg){
                //find cheapest shipment for each leg (in terms of cost)
                unset($cheapestShippers[$legName]);
                $lowestCost = null;

                foreach($leg as $shipperName => $shipper){
                    if(empty($lowestCost) || $shipper["cost"] < $lowestCost){
                        $cheapestShippers[$legName]["days"] = $shipper["days"];
                        $cheapestShippers[$legName]["cost"] = $shipper["cost"];
                        $cheapestShippers[$legName]["name"] = $shipperName;
                        $lowestCost = $shipper["cost"];
                    }
                }

                //recalculate days and see if we are under max days...
                $totalDays += $cheapestShippers[$legName]['days'];  
            }
            //print "<h2>totalDays: $totalDays</h2>";
        }

        print "<h1>Chosen Shippers:</h1><pre>";
        print_r($cheapestShippers);
        print "</pre>";

Ich denke, ich muss vielleicht tatsächlich etwas tun, bei dem ich buchstäblich jede Kombination eine nach der anderen mache (mit einer Reihe von Schleifen) und die Gesamtpunktzahl jeder Kombination addiere und die beste finde ...

BEARBEITEN:Zur Klarstellung: Dies ist keine „Hausaufgabe“ (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 begann, an diesem Problem zu arbeiten, die aktuellen Einschränkungen hätte, würde ich eine Variante des A*-Algorithmus (oder Dijkstras oder den kürzesten Weg oder Simplex oder so etwas) verwenden.Aber alles hat sich verändert und verändert, und das bringt mich dorthin, wo ich gerade bin.

Ich schätze, das bedeutet, dass ich den ganzen Mist, den ich bisher gemacht habe, vergessen und einfach mit dem weitermachen muss, von dem ich weiß, dass ich es tun sollte, nämlich einem Pfadfindungsalgorithmus.

Answer 1

Könnte einiges davon ändern Algorithmen für kürzeste Wege, wie bei Dijkstra, um jeden Pfad nach Kosten zu gewichten, aber auch die Zeit im Auge zu behalten und die Fortsetzung eines bestimmten Pfads zu stoppen, wenn die Zeit Ihren Schwellenwert überschreitet.Auf diese Weise sollten Sie den günstigsten finden, der Sie unter Ihre Schwelle bringt

Answer 2

Klingt so, als ob das, was Sie haben, ein „lineares Programmierproblem“ ist.Es klingt auch wie ein Hausaufgabenproblem, nichts für ungut.

Die klassische Lösung eines LP-Problems wird „Simplex-Methode“ genannt.Google es.

Um diese Methode verwenden zu können, muss das Problem jedoch korrekt formuliert sein, um Ihre Anforderungen zu beschreiben.

Dennoch ist es möglicherweise möglich, alle möglichen Pfade aufzuzählen, da die Menge so klein ist.So etwas lässt sich allerdings nicht skalieren.

Answer 3

Klingt nach einem Job für Dijkstras Algorithmus:

Dijkstras Algorithmus, 1959 vom niederländischen Informatiker Edsger Dijkstra konzipiert, 1 ist ein Graphsuchalgorithmus, der das Problem des kürzesten Pfads aus einer Quelle für einen Graphen mit nicht negativen Kantenpfadkosten löst und einen Baum des kürzesten Pfads ausgibt.Dieser Algorithmus wird häufig beim Routing verwendet.

Details zur Implementierung finden Sie auch im Wikipedia-Artikel.

Answer 4

Wenn ich wüsste, dass ich mich nur mit 5 Städten in einer vorgegebenen Reihenfolge befassen muss und dass es nur 3 Routen zwischen benachbarten Städten gibt, würde ich es brutal erzwingen.Es hat keinen Sinn, elegant zu sein.

Wenn dies hingegen eine Hausaufgabe wäre und ich einen Algorithmus entwickeln müsste, der sich tatsächlich skalieren lässt, würde ich wahrscheinlich einen anderen Ansatz wählen.

Answer 5

Wie Baltimark sagte, handelt es sich im Grunde genommen um ein lineares Programmierproblem.Wenn nur die Koeffizienten für die Verlader (1 für eingeschlossen, 0 für nicht eingeschlossen) für jeden Zweig keine (binären) ganzen Zahlen wären, wäre dies einfacher zu lösen.Jetzt müssen Sie einige (binäre) ILP-Heuristiken (Integer Linear Programming) finden, da das Problem NP-schwer ist.Sehen Wikipedia zur ganzzahligen linearen Programmierung für Links;In meinem linearen Programmierkurs haben wir es zumindest verwendet Verzweigt und gebunden.

Wenn ich darüber nachdenke, ist dieser Sonderfall tatsächlich ohne tatsächlichen ILP lösbar, da die Anzahl der Tage keine Rolle spielt, solange sie <= 5 ist.Beginnen Sie nun mit der Auswahl des günstigsten Anbieters als erste Wahl (Conway 5:1000).Als nächstes wählen Sie noch einmal das günstigste, was 8 Tage und 4000 Währungseinheiten ergibt, was zu viel ist, also brechen wir das ab.Wenn wir auch andere ausprobieren, stellen wir fest, dass sie alle Tage > 5 ergeben, also kehren wir zur ersten Wahl zurück und versuchen es mit der zweitgünstigsten (FedEx 2:3000) und dann mit Ups in der zweiten und Fedex in der letzten.Das ergibt insgesamt 4 Tage und 9000 Währungseinheiten.

Wir könnten diese Kosten dann verwenden, um andere Suchvorgänge im Baum zu beschneiden, deren Ergebnis um eine Teilbaumstufe höher wäre als das, was wir bereits gefunden haben, und diesen Teilbaum von diesem Zeitpunkt an undurchsucht zu lassen.Dies funktioniert nur, solange wir wissen, dass die Suche im Teilbaum keine besseren Ergebnisse liefert, wie wir es hier tun, wenn die Kosten nicht negativ sein können.

Ich hoffe, dieses Geschwafel hat ein wenig geholfen :).

Answer 6

Das ist ein Problem mit dem Rucksack.Die Gewichte sind die Transporttage, und der Gewinn sollte 5.000 US-Dollar betragen – die Kosten für die Strecke.Eliminieren Sie alle negativen Kosten und machen Sie weiter!

Answer 7

Ich denke, dass Dijkstras Algorithmus dazu dient, einen kürzesten Weg zu finden.

cmcculloh sucht nach den minimalen Kosten unter der Bedingung, dass er es innerhalb von 5 Tagen erhält.

Wenn man also einfach nur den schnellsten Weg findet, kommt man nicht am günstigsten ans Ziel, und wenn man zum günstigsten Weg dorthin kommt, kommt man nicht in der erforderlichen Zeit ans Ziel.