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

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>";

我想我可能不得不实际做某种事情,我逐字逐句地制作每个组合(用一系列循环)并将每个组合的总分"加起来",并找到最好的一个....

编辑:澄清一下,这不是"家庭作业"任务(我不在学校).这是我目前工作项目的一部分.

要求(一如既往)不断变化.如果我在开始研究这个问题的时候得到了当前的限制,我会使用A*算法的一些变体(或Dijkstra或最短路径或单纯形或其他东西).但是一切都在变形和变化,这让我走到了现在的位置.

所以我想这意味着我需要忘记我在这一点上所做的所有废话,并且只是按照我所知道的去做,这是一个路径查找算法.

Answer 1

可以改变一些最短路径算法,如Dijkstra's,按成本对每条路径进行加权,但如果时间超过阈值,还要跟踪时间并停止沿某条路径前进.应该找到最便宜的,以这种方式让你进入门槛

Answer 2

听起来像你所谓的"线性编程问题".这听起来像是一个家庭作业问题,没有冒犯.

LP问题的经典解决方案称为"单纯形法".谷歌一下.

但是,要使用该方法,您必须正确制定问题以描述您的要求.

尽管如此,有可能枚举所有可能的路径,因为你有这么小的一组.但是,这样的事情不会扩展.

Answer 3

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

Dijkstra的算法由荷兰计算机科学家Edsger Dijkstra于1959年构思,1是一种图搜索算法,它解决了具有非负边缘路径成本的图的单源最短路径问题,输出最短路径树.该算法通常用于路由.

维基百科文章中还有实现细节.