从给定的多组中找到最佳组合

Question

假设您有一批货物。 它需要从 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. 找到每条航线最长的托运人
2. 消除最“昂贵”的托运人
3. 找到每条航线最便宜的托运人
4. 计算总成本和费用 天
5. 如果天数可以接受，则完成，否则，转到 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"] . " &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>";

I我想我可能必须真正做一些事情，我逐个进行每个组合（通过一系列循环）并将每个组合的总“分数”相加，然后找到最好的一个......

编辑： 澄清一下，这不是“家庭作业”（我不在学校）。 这是我当前工作项目的一部分。

需求（一如既往）一直在不断变化。 如果我在开始解决这个问题时受到当前的约束，我将使用 A* 算法的某些变体（或 Dijkstra 算法或最短路径或单纯形算法或其他算法）。 但一切都在发生变化，这让我陷入了现在的境地。

所以我想这意味着我需要忘记到目前为止我所做的所有废话，只做我知道应该做的事情，这是一种路径查找算法。

Answer 1

可以改变一些最短路径算法，例如Dijkstra算法，按成本对每条路径进行加权，但也保持跟踪时间，如果时间超过你的阈值，就停止沿着特定的路径前进。 应该找到最便宜的，让你低于你的门槛

Answer 2

听起来你所遇到的问题被称为“线性规划问题”。 这听起来也像是一个家庭作业问题，无意冒犯。

LP 问题的经典解决方案称为“单纯形法”。 去谷歌上查询。

但是，要使用该方法，您必须正确表述问题来描述您的需求。

尽管如此，还是可以枚举所有可能的路径，因为你的路径很小。 不过，这样的事情不会规模化。

Answer 3

听起来像是 Dijkstra 算法 的工作：

Dijkstra 算法，由荷兰计算机科学家 Edsger Dijkstra 于 1959 年提出，1 是图搜索算法，解决具有非负边路径成本的图的单源最短路径问题，输出最短路径树。 该算法在路由中经常使用。

维基百科文章中也有实现细节。

Answer 4

如果我知道我只需要按照预先确定的顺序处理 5 个城市，并且相邻城市之间只有 3 条路线，我就会强制执行。 优雅是没有意义的。

另一方面，如果这是一项家庭作业，并且我应该生成一个可以实际扩展的算法，我可能会采取不同的方法。

Answer 5

正如 Baltimark 所说，这基本上是一个线性规划问题。 如果每个航段的托运人系数（1 表示包含，0 表示不包含）不是（二进制）整数，那么这将更容易解决。 现在您需要找到一些（二进制）整数线性规划（ILP）启发式，因为该问题是 NP 困难的。
请参阅整数线性规划维基百科获取链接； 在我的线性编程课程中，我们至少使用了分支与界限。

其实现在我想起来了，这种特殊情况是可以在没有实际ILP的情况下解决的，因为只要<= 5天数并不重要。现在首先选择最便宜的航空公司作为首选（Conway 5:1000） 。 接下来，您再次选择最便宜的，结果是 8 天和 4000 个货币单位，这太多了，所以我们中止。 通过尝试其他人，我们发现他们的结果都是天> 5 所以我们回到第一个选择，尝试第二便宜的（联邦快递 2:3000），然后在第二个选择 ups，最后一个选择联邦快递。 这给了我们总共 4 天和 9000 个货币单位。

然后，我们可以使用此成本来修剪树中的其他搜索，这些搜索在某些子树阶段结果中的成本将大于我们已经找到的搜索结果，并从该点开始不搜索该子树。
只有当我们知道在子树中搜索不会产生更好的结果时，这才有效，就像我们在成本不能为负时所做的那样。

希望这篇闲言碎语对您有所帮助:)。

Answer 6

这是一个背包问题。 权重是运输天数，利润应该是 5000 美元 - 航段成本。 消除所有负面成本并从那里开始！

Answer 7

我认为迪杰斯特拉算法是为了寻找最短路径。

cmcculloh 正在寻找最低成本，但限制是他在 5 天内得到它。

因此，仅仅找到最快的方式并不能以最便宜的价格到达目的地，而以最便宜的价格到达目的地也无法在所需的时间内到达目的地。