从给定的多个集合中找到最佳组合
假设我们有货。它需要从A点到B点，从B点到C点，最后从C点到D点。我们需要它在五天内以最少的钱到达那里。每条腿有三种可能的托运人，每条腿的时间和成本各不相同：
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
)
)
)
我们将如何以编程方式找到最佳组合？
到目前为止，我最好的尝试(第三或者第四种算法)是：
- 查找每条腿最长的托运人
- 消除最"昂贵"的
- 查找每条腿最便宜的托运人
- 计算总费用和天数
- 如果可以接受，则结束，否则转到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>";
我想我可能实际上需要做某种事情，即从字面上逐个使每个组合(带有一系列循环)，然后将每个组合的总"得分"相加，然后找到最佳组合。
编辑：
要澄清的是，这不是一项"家庭作业"作业(我不在学校)。这是我当前工作项目的一部分。
要求(一如既往)一直在不断变化。如果在开始研究此问题时得到当前的限制，那我将使用A *算法的某些变体(或者Dijkstra的或者最短路径或者单纯形的东西)。但是一切都在变化和变化中，这使我进入了现在的状态。
所以我想这意味着我需要忘掉到目前为止所做的所有废话，只继续我所知道的应该去的东西，这是一种寻路算法。
解决方案
回答
听起来像我们所拥有的被称为"线性编程问题"。这听起来也像是一项家庭作业问题，没有冒犯性。
LP问题的经典解决方案称为" Simplex方法"。去谷歌上查询。
但是，要使用该方法，我们必须正确制定问题以描述要求。
不过，由于集合很小，因此可能会列举所有可能的路径。但是，这种事情无法扩展。
回答
听起来像Dijkstra算法的工作：
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, 1 is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing.
Wikipedia文章中也有实现细节。
回答
可以更改某些最短路径算法，例如Dijkstra的算法，以按成本对每个路径进行加权，而且还可以跟踪时间，并在时间超出阈值时停止沿某个路径前进。应该以这种方式找到让我们进入门槛的最便宜的
回答
如果我知道我只需要按照预定的顺序处理5个城市，并且相邻城市之间只有3条路线，那我就蛮力了。优雅无济于事。
另一方面，如果这是一项家庭作业，而我应该产生一种实际上可以扩展的算法，那么我可能会采用另一种方法。
回答
我认为Dijkstra的算法是用于寻找最短路径。
cmcculloh正在寻求最低成本，但要受限于他在5天内到达那里的限制。
因此，仅仅找到最快的方法不会使他到那里最便宜，而以最便宜的价格到那里就不会在所需的时间内到达那里。
回答
这是一个背包问题。重量是运输中的天数，利润应该是5000美元的支腿成本。消除所有负成本，然后再去那里！
回答
正如Baltimark所说，这基本上是一个线性编程问题。如果仅托运人的系数(包括1，不包括0，0)不是每条腿的(二进制)整数，这将更容易解决。现在，我们需要找到一些(二进制)整数线性规划(ILP)启发式方法，因为问题很难解决。
有关整数线性编程的信息，请参见Wikipedia。在我的线性编程课程中，我们至少使用了Branch and bound。
实际上，现在我想到了，这种特殊情况无需实际的ILP就可以解决，因为只要天数不超过<= 5，就不重要了。接下来，我们再次选择最便宜的价格，即8天和4000个货币单位，这太多了，因此我们中止了。通过也尝试其他方法，我们看到它们的结果均大于5天，因此我们回到了第一选择，尝试了第二便宜的方法(FedEx 2：3000)，然后在第二个方法中进行加价，在最后一个方法中使用了联邦快递。这样一来，我们总共有4天的时间和9000个货币单位。
然后，我们可以使用此开销来修剪树中的其他搜索，这会使某些子树阶段的结果的开销大于我们已经找到的结果，并且从那时起就不再搜索该子树。
只要我们知道在子树中搜索将不会产生更好的结果，就可以这样做，就像我们在成本不能为负时所做的那样。
希望这个杂乱无章的帮助:)。
