荷物があるとします。A 地点から B 地点、B 地点から C 地点、そして最後に C 地点から D 地点に移動する必要があります。5 日以内に到達する必要があり、できるだけ少ない金額で済みます。各レグには 3 つの可能な荷送人があり、各レグにはそれぞれ異なる時間とコストがあります。
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
)
)
)
プログラムで最適な組み合わせを見つけるにはどうすればよいでしょうか?
これまでの私の最善の試み（3番目または4番目のアルゴリズム）は次のとおりです。
- 各区間で最長の荷送人を見つける
- 最も「高価な」ものを排除する
- 各区間で最も安い荷送人を見つける
- 総費用と日数を計算する
- 日数が許容できる場合は終了、そうでない場合は 1 に移動
PHP ですばやくモックアップします (以下のテスト配列は問題なく動作しますが、上記のテスト配列で試してみると、正しい組み合わせが見つからないことに注意してください)。
$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>";
文字通り、各組み合わせを 1 つずつ (一連のループを使用して) 作成し、それぞれの合計「スコア」を合計して、最高のものを見つけるという、ある種のことを実際に行う必要があると思います....
編集：明確にするために、これは「宿題」の課題ではありません（私は学校にいません）。それは私の現在のプロジェクトの一部です。
要件は (いつものように) 常に変化しています。この問題に取り組み始めた時点で現在の制約が与えられていたとしたら、A* アルゴリズムの変形 (またはダイクストラまたは最短経路またはシンプレックスなど) を使用していたでしょう。しかし、すべてが変形し、変化しており、それが私を今いる場所に導きます.
つまり、これまでに行ったすべてのがらくたを忘れて、パス検索アルゴリズムである、使用すべきだとわかっているものを使用する必要があることを意味していると思います。