Найти лучшую комбинацию из заданного множества множеств

Скажем, у вас есть груз. Он должен пройти из пункта А в пункт В, из пункта В в пункт С и, наконец, из пункта С в пункт 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 * (или Дейкстры, или кратчайшего пути, или симплекса, или чего-то еще). Но все меняется и меняется, и это приводит меня туда, где я сейчас нахожусь.

Так что, я думаю, это означает, что мне нужно забыть обо всем дерьме, которое я сделал к этому моменту, и просто пойти с тем, что, как я знаю, мне следует сделать, - алгоритмом поиска пути.

18.08.2008 16:39:23
+1 за то, что мы приближаемся к требованиям, предъявляемым к морфингу с течением времени, с настроением «давайте бросим эту чушь и начнем сначала».
Alex 3.07.2012 15:12:50
7 ОТВЕТОВ
РЕШЕНИЕ

Может изменить некоторые алгоритмы кратчайшего пути , такие как алгоритм Дейкстры, чтобы взвешивать каждый путь по стоимости, но также отслеживать время и прекратить движение по определенному пути, если время превышает ваш порог. Должен найти самое дешевое, что доставит вас под ваш порог таким образом

8
18.08.2008 16:52:36

Похоже, то, что у вас есть, называется «проблемой линейного программирования». Это также звучит как домашнее задание, без обид.

Классическое решение проблемы ЛП называется «Симплекс-метод». Поищи в Гугле.

Однако для использования этого метода необходимо правильно сформулировать проблему, чтобы описать ваши требования.

Тем не менее, может быть возможным перечислить все возможные пути, так как у вас такой маленький набор. Такая вещь не будет масштабироваться, хотя.

5
18.08.2008 16:48:34

Похоже, работа для алгоритма Дейкстры :

Алгоритм Дейкстры, разработанный голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1959 году 1, представляет собой алгоритм поиска графа, который решает проблему кратчайшего пути из одного источника для графа с неотрицательными затратами на ребро пути, выводя дерево кратчайшего пути. Этот алгоритм часто используется при маршрутизации.

Также есть подробности реализации в статье Википедии.

5
18.08.2008 16:49:53

Если бы я знал, что мне нужно иметь дело только с 5 городами в заранее установленном порядке и что между соседними городами было только 3 маршрута, я бы грубо форсировал это. Нет смысла быть элегантным.

Если бы, с другой стороны, это было домашнее задание, и я должен был разработать алгоритм, который мог бы реально масштабироваться, я бы, вероятно, выбрал другой подход.

3
18.08.2008 16:56:02

Я думаю, что алгоритм Дейкстры для нахождения кратчайшего пути.

cmcculloh ищет минимальную стоимость с учетом ограничения, которое он получит там за 5 дней.

Таким образом, простое нахождение самого быстрого пути не приведет к тому, что он окажется там самым дешевым, а попадание туда за самым дешевым, не получит его там за требуемое количество времени.

-1
18.08.2008 16:56:10

Это проблема ранца . Весами являются дни в пути, а прибыль должна составлять 5000 долларов - стоимость ноги. Устраните все отрицательные расходы и идите оттуда!

2
3.07.2012 15:05:38

Как сказал Балтимарк, это в основном проблема линейного программирования. Если бы только коэффициенты для грузоотправителей (1 для включенного, 0 для не включенного) не были (двоичными) целыми числами для каждого участка, это было бы легче решить. Теперь вам нужно найти некоторую эвристику (двоичного) целочисленного линейного программирования (ILP), поскольку задача NP-трудна. Смотрите Википедию по целочисленному линейному программированию для ссылок; В моем курсе линейного программирования мы использовали хотя бы Branch и Bound .

На самом деле, теперь, когда я об этом думаю, этот особый случай можно решить без фактического ILP, поскольку количество дней не имеет значения, если оно <= 5. Теперь начните с выбора самого дешевого перевозчика для первого выбора (Конвей 5: 1000). Затем вы снова выбираете самый дешевый, в результате 8 дней и 4000 денежных единиц, что слишком много, поэтому мы прерываем это. Испытывая и других, мы видим, что все они дают дни> 5, поэтому мы возвращаемся к первому выбору и пробуем второй самый дешевый (FedEx 2: 3000), а затем повышаем второй и FedEx в последнем. Это дает нам в общей сложности 4 дня и 9000 денежных единиц.

Затем мы могли бы использовать эту стоимость, чтобы обрезать другие запросы в дереве, которые по некоторому результату на уровне поддерева будут стоить больше, чем тот, который мы уже нашли, и оставить это поддерево незамеченным с этого момента. Это работает только до тех пор, пока мы знаем, что поиск в поддереве не даст лучших результатов, как мы делаем здесь, когда затраты не могут быть отрицательными.

Надеюсь, что эта бессвязная помощь немного помогла :).

2
19.09.2008 19:52:57