Скажем, у вас есть груз. Он должен пройти из пункта А в пункт В, из пункта В в пункт С и, наконец, из пункта С в пункт 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 (обратите внимание, что приведенный ниже тестовый массив работает плавно, но если вы попробуете его с тестовым массивом сверху, он не найдет правильной комбинации):
<code>$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 " ";
while ($ totalDays> $ maxDays && $ times <500) {
$ totalDays = 0;
$ раз ++;
$ худшийShipper = нуль;
$ longestShippers = null;
$ cheapShippers = null;
foreach ($ shippers as $ legName => $ leg) {
// найти самую длинную поставку для каждого этапа (в днях)
переменная не установлена ($ 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"];
// печать $ shipper ["totalCost"]. "& lt;? & gt;". $ худшийShipper ["totalCost"]. ";";
if (empty ($ худшийShipper) || $ shipper ["totalCost"]> $ худшийShipper ["totalCost"]) {
$ худшийShipper = $ shipper;
$ худшийShipperLeg = $ leg;
}
}
// выводим «худший грузоотправитель: shippers [$ Художественная ширма» [{$ Художник ['имя']}] ». $ грузоотправители [$ worstShipperLeg] [$ worstShipper [ "имя"]] [ "дней"];
переменные не установлены ($ грузоотправители [$ worstShipperLeg] [$ worstShipper [ "имя"]]);
print "
Next:
";
print_r($shippers);
print " ";
foreach ($ shippers as $ legName => $ leg) {
// найти самую дешевую отправку для каждой очереди
переменная не установлена ($ cheapestShippers [$ legName]);
$ lowerCost = null;
foreach ($ leg as $ shipperName => $ shipper) {
if (empty ($ lowerCost) || $ shipper ["cost"] <$ lowerCost) {
$ cheapShippers [$ legName] ["days"] = $ shipper ["days"];
$ cheapShippers [$ legName] ["cost"] = $ shipper ["cost"];
$ cheapShippers [$ legName] ["name"] = $ shipperName;
$ lowerCost = $ shipper ["cost"];
}
}
// пересчитаем дни и посмотрим, не достигли ли мы максимальных дней ...
$ totalDays + = $ cheapShippers [$ legName] ['days'];
}
// print "<h2> totalDays: $ totalDays ";
}
печать "
Избранные грузоотправители:
";
print_r($cheapestShippers);
print "";
Я думаю, что мне, возможно, придется сделать что-то вроде того, где я буквально составляю каждую комбинацию одну за другой (с серией циклов), складываю общую «оценку» каждой и нахожу лучшую ... .
EDIT:Чтобы уточнить, это не домашнее задание (я не в школе). Это часть моего текущего проекта на работе.
Требования (как всегда) постоянно менялись. Если бы мне дали текущие ограничения в то время, когда я начал работать над этой проблемой, я бы использовал какой-то вариант алгоритма A * (или Дейкстры, или кратчайшего пути, или симплекса, или чего-то еще). Но все меняется и меняется, и это приводит меня туда, где я сейчас нахожусь.
Так что я предполагаю, что это означает, что мне нужно забыть обо всем дерьме, которое я сделал к этому моменту, и просто пойти с тем, что я знаю, с которым я должен идти, - это алгоритм поиска пути.