Найдите наилучшую комбинацию из заданного набора из нескольких наборов
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 * (или Дейкстры, или кратчайшего пути, или симплекса, или чего-то еще).Но все менялось, и это привело меня туда, где я нахожусь прямо сейчас.
Так что, я думаю, это означает, что мне нужно забыть обо всем том дерьме, которое я натворил до этого момента, и просто следовать тому, что, я знаю, я должен использовать, а именно алгоритму поиска пути.
Решение
Могло бы изменить некоторые из алгоритмы кратчайшего пути, как у Дейкстры, взвешивать каждый путь по стоимости, но также отслеживать время и прекращать движение по определенному пути, если время превышает ваш порог.Следует найти самое дешевое, которое таким образом позволит вам попасть под ваш порог
Другие советы
Похоже, то, что у вас есть, называется "задачей линейного программирования".Это также звучит как проблема с домашним заданием, без обид.
Классическое решение задачи LP называется "Симплексным методом".Погуглите это.
Однако, чтобы использовать этот метод, вы должны правильно сформулировать проблему, описывающую ваши требования.
Тем не менее, возможно, удастся перечислить все возможные пути, поскольку у вас такой небольшой набор.Однако такая штука не будет масштабироваться.
Звучит как работа для Алгоритм Дейкстры:
Алгоритм Дейкстры, разработанный голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1959 году, 1 это алгоритм поиска по графу, который решает задачу о кратчайшем пути из одного источника для графа с неотрицательными затратами на прохождение ребер, выводя дерево кратчайших путей.Этот алгоритм часто используется при маршрутизации.
Подробности реализации также приведены в статье Википедии.
Если бы я знал, что мне придется иметь дело только с 5 городами в заранее определенном порядке и что существует только 3 маршрута между соседними городами, я бы применил грубую силу.Нет смысла быть элегантным.
С другой стороны, если бы это было домашнее задание и я должен был создать алгоритм, который действительно мог бы масштабироваться, я бы, вероятно, выбрал другой подход.
Как сказал Балтимарк, по сути, это задача линейного программирования.Если бы только коэффициенты для отправителей (1 для включенных, 0 для не включенных) не были (двоичными) целыми числами для каждого этапа, это было бы более легко разрешимо.Теперь вам нужно найти некоторую эвристику (двоичного) целочисленного линейного программирования (ILP), поскольку задача NP-сложная.Видишь Википедия о целочисленном линейном программировании для ссылок;на моем курсе линейного программирования мы использовали по крайней мере Ветвь и граница.
На самом деле, теперь, когда я думаю об этом, этот особый случай разрешим без фактического ILP, поскольку количество дней не имеет значения, пока это так <= 5.Теперь начните с выбора самого дешевого перевозчика для first choice (Conway 5: 1000).Затем вы снова выбираете самую дешевую, в результате чего получается 8 дней и 4000 единиц валюты, что слишком много, поэтому мы отменяем это.Пробуя и другие, мы видим, что все они дают результаты дней > 5, поэтому мы возвращаемся к первому выбору и пробуем второй по дешевизне (FedEx 2: 3000), а затем ups на втором и FedEx на последнем.Это дает нам в общей сложности 4 дня и 9000 единиц валюты.
Затем мы могли бы использовать эту стоимость для сокращения других поисковых запросов в дереве, которые на каком-то этапе на этапе поддерева стоили бы больше, чем тот, который мы уже нашли, и оставить это поддерево неотысканным с этого момента.Это работает только до тех пор, пока мы можем знать, что поиск в поддереве не даст лучших результатов, как мы делаем здесь, когда затраты не могут быть отрицательными.
Надеюсь, эта бессвязная болтовня немного помогла :).
Это настоящий проблема с рюкзаком.Весы - это дни в пути, а прибыль должна составить 5000 долларов - стоимость этапа.Устраните все негативные затраты и двигайтесь дальше!
Я думаю, что алгоритм Дейкстры предназначен для нахождения кратчайшего пути.
cmcculloh ( смккуллох ) ищет минимальную стоимость с учетом того, что он получит ее через 5 дней.
Таким образом, просто найдя самый быстрый способ, он не доберется туда дешевле всего, а добравшись туда за самым дешевым, не доберется туда за необходимое количество времени.
