从给定的多组中找到最佳组合
https://stackoverflow.com/questions/14884
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
假设您有一批货物。它需要从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 算法或最短路径或单纯形算法或其他算法）。但一切都在发生变化，这让我陷入了现在的境地。
所以我想这意味着我需要忘记到目前为止我所做的所有废话，只做我知道应该做的事情，这是一种路径查找算法。
解决方案
可以改变一些 最短路径算法, 与 Dijkstra 一样，按成本对每条路径进行加权，但也会跟踪时间，如果时间超过阈值，则停止沿着特定路径前进。应该找到最便宜的，让你低于你的门槛
其他提示
听起来你所遇到的问题被称为“线性规划问题”。这听起来也像是一个家庭作业问题，无意冒犯。
LP 问题的经典解决方案称为“单纯形法”。去谷歌上查询。
但是，要使用该方法，您必须正确表述问题来描述您的需求。
尽管如此，还是可以枚举所有可能的路径，因为你的路径很小。不过，这样的事情不会规模化。
如果我知道我只需要按照预先确定的顺序处理 5 个城市，并且相邻城市之间只有 3 条路线，我就会强制执行。优雅是没有意义的。
另一方面，如果这是一项家庭作业，并且我应该生成一个可以实际扩展的算法，我可能会采取不同的方法。
正如 Baltimark 所说，这基本上是一个线性规划问题。如果每个航段的托运人系数（1 表示包含，0 表示不包含）不是（二进制）整数，那么这将更容易解决。现在您需要找到一些（二进制）整数线性规划（ILP）启发式，因为该问题是 NP 困难的。看 维基百科关于整数线性规划 对于链接；在我的线性编程课程中，我们至少使用了 分支定界.
事实上，现在我想起来了，这种特殊情况是可以在没有实际 ILP 的情况下解决的，因为只要天数 <= 5，天数并不重要。现在首先选择最便宜的航空公司作为首选（Conway 5:1000）。接下来，您再次选择最便宜的，结果是 8 天和 4000 个货币单位，这太多了，所以我们放弃了。通过尝试其他的，我们发现它们的结果都> 5天，所以我们回到第一个选择并尝试第二便宜的（联邦快递2：3000），然后在第二个中选择UPS，最后在最后一个中选择联邦快递。这给了我们总共 4 天和 9000 个货币单位。
然后，我们可以使用此成本来修剪树中的其他搜索，这些搜索在某些子树阶段结果中的成本将大于我们已经找到的搜索结果，并从该点开始不搜索该子树。只有当我们知道在子树中搜索不会产生更好的结果时，这才有效，就像我们在成本不能为负时所做的那样。
希望这篇闲言碎语对您有所帮助:)。
这是一个 背包问题. 。权重是运输天数，利润应该是 5000 美元 - 航段成本。消除所有负面成本并从那里开始！
我认为迪杰斯特拉算法是为了寻找最短路径。
姆卡洛 正在寻找最低成本，但受到 5 天内到达的限制。
因此，仅仅找到最快的方式并不能以最便宜的价格到达目的地，而以最便宜的价格到达目的地也无法在所需的时间内到达目的地。
