Angenommen, Sie haben eine Lieferung. 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 Versendern für jedes Bein, jede mit ihrer eigenen unterschiedlichen Zeit und Kosten für jedes Bein:Finden Sie die beste Kombination aus einem gegebenen Satz von mehreren Sets
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 gehen über programmatisch die beste Kombination zu finden?
Mein bester Versuch so weit (dritter oder vierte Algorithmus) ist:
- Finden Sie den längsten Versender für jedes Bein
- beseitigen die „teueren“ ein
- den günstigster Versender für jedes Bein Finden
- berechnen die Gesamtkosten & Tage
- Wenn Tage sind akzeptabel, fertig, sonst, gehe zu 1
Schnell verspottet-up in PHP (beachten Sie, dass die Testanordnung unter swimmingly funktioniert, aber wenn man es mit der Testanordnung von oben versuchen, es nicht die richtige Kombination finden):
$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"] . " <?> " . $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 tatsächlich etwas tun, wo ich buchstäblich jede Kombination einzeln mache (mit einer Reihe von Schleifen) und summiere die Gesamt "Punktzahl" von jedem, und finde das beste ....
EDIT: Um zu verdeutlichen, ist dies keine "Hausaufgabe" Aufgabe (ich bin nicht in der Schule). Es ist Teil meines aktuellen Projekts bei der Arbeit.
Die Anforderungen (wie immer) haben sich 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, das ist ein Pfadfindungsalgorithmus.
+1 für die Annäherung an Morphing-über-Zeit-Anforderungen mit einem "lass uns diesen Mist Graben und neu beginnen" Gemütszustand. – Alex