Trouver la meilleure combinaison à partir d'un ensemble donné de plusieurs ensembles
https://stackoverflow.com/questions/14884
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Disons que vous avez une livraison.Il doit aller du point A au point B, du point B au point C et enfin du point C au point D.Vous en avez besoin pour y arriver en cinq jours pour le moins d’argent possible.Il existe trois expéditeurs possibles pour chaque étape, chacun avec son propre délai et son propre coût pour chaque étape :
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
)
)
)
Comment feriez-vous pour trouver la meilleure combinaison par programmation ?
Ma meilleure tentative jusqu'à présent (troisième ou quatrième algorithme) est :
- Trouvez l'expéditeur le plus long pour chaque étape
- Éliminer le plus « cher »
- Trouvez l'expéditeur le moins cher pour chaque étape
- Calculez le coût total et les jours
- Si les jours sont acceptables, terminez, sinon passez à 1
Maquette rapide en PHP (notez que le tableau de test ci-dessous fonctionne à merveille, mais si vous l'essayez avec le tableau de test ci-dessus, il ne trouve pas la bonne combinaison) :
$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>";
Je pense que je devrai peut-être faire une sorte de chose où je fais littéralement chaque combinaison une par une (avec une série de boucles) et additionne le "score" total de chacune, et trouve la meilleure....
MODIFIER:Pour clarifier, ce n'est pas un « devoir » (je ne suis pas à l'école).Cela fait partie de mon projet actuel au travail.
Les exigences (comme toujours) ont constamment changé.Si on me donnait les contraintes actuelles au moment où j'ai commencé à travailler sur ce problème, j'utiliserais une variante de l'algorithme A* (ou celui de Dijkstra ou le chemin le plus court ou le simplexe ou quelque chose du genre).Mais tout s’est transformé et a changé, et cela m’amène là où j’en suis actuellement.
Donc je suppose que cela signifie que je dois oublier toutes les conneries que j'ai faites jusqu'à présent et simplement suivre ce que je sais que je devrais utiliser, à savoir un algorithme de recherche de chemin.
La solution
Pourrait modifier certains des algorithmes de chemin le plus court, comme celui de Dijkstra, pour pondérer chaque chemin en fonction du coût, mais aussi garder une trace du temps et arrêter de suivre un certain chemin si le temps dépasse votre seuil.De cette façon, je devrais trouver le moins cher qui vous permette de passer sous votre seuil.
Autres conseils
On dirait que ce que vous avez s'appelle un "problème de programmation linéaire".Cela ressemble aussi à un problème de devoirs, sans vouloir vous offenser.
La solution classique à un problème LP est appelée « Méthode Simplex ».Recherche le sur Google.
Cependant, pour utiliser cette méthode, vous devez formuler correctement le problème pour décrire vos besoins.
Néanmoins, il peut être possible d'énumérer tous les chemins possibles, puisque vous disposez d'un si petit ensemble.Cependant, une telle chose ne pourra pas évoluer.
Cela ressemble à un travail pour L'algorithme de Dijkstra:
L'algorithme de Dijkstra, conçu par l'informaticien néerlandais Edsger Dijkstra en 1959, 1 est un algorithme de recherche de graphe qui résout le problème du chemin le plus court à source unique pour un graphe avec des coûts de chemin de bord non négatifs, générant un arbre de chemin le plus court.Cet algorithme est souvent utilisé en routage.
Il existe également des détails de mise en œuvre dans l'article Wikipédia.
Si je savais que je n'avais affaire qu'à 5 villes, dans un ordre prédéterminé, et qu'il n'y avait que 3 routes entre les villes adjacentes, je le forcerais brutalement.Cela ne sert à rien d'être élégant.
Si, d’un autre côté, il s’agissait d’un devoir et que j’étais censé produire un algorithme réellement évolutif, j’adopterais probablement une approche différente.
Comme l'a dit Baltimark, il s'agit essentiellement d'un problème de programmation linéaire.Si seulement les coefficients des expéditeurs (1 pour inclus, 0 pour non inclus) n'étaient pas des nombres entiers (binaires) pour chaque étape, cela serait plus facile à résoudre.Vous devez maintenant trouver des heuristiques de programmation linéaire entière (ILP) (binaires) car le problème est NP-difficile.Voir Wikipédia sur la programmation linéaire entière pour les liens ;dans mon cours de programmation linéaire, nous avons utilisé au moins Branché et relié.
En fait, maintenant que j'y pense, ce cas particulier peut être résolu sans ILP réel, car le nombre de jours n'a pas d'importance tant qu'il est <= 5.Commencez maintenant par choisir le transporteur le moins cher en premier choix (Conway 5:1000).Ensuite, vous choisissez à nouveau le moins cher, ce qui donne 8 jours et 4 000 unités monétaires, ce qui est trop, donc nous abandonnons cela.En essayant d'autres aussi, nous voyons qu'ils donnent tous des résultats > 5 jours, donc nous revenons au premier choix et essayons le deuxième moins cher (FedEx 2 : 3000), puis ups dans le second et Fedex dans le dernier.Cela nous donne un total de 4 jours et 9 000 unités monétaires.
Nous pourrions ensuite utiliser ce coût pour élaguer d'autres recherches dans l'arborescence qui, par certains sous-arbres, coûteraient plus cher que celui que nous avons déjà trouvé et laisser ce sous-arbre sans recherche à partir de ce moment-là.Cela ne fonctionne que tant que nous savons que la recherche dans le sous-arbre ne produira pas de meilleurs résultats, comme nous le faisons ici lorsque les coûts ne peuvent pas être négatifs.
J'espère que cette divagation a aidé un peu :).
C'est un problème de sac à dos.Les poids correspondent aux jours de transit et le bénéfice devrait être de 5 000 $ - coût du trajet.Éliminez tous les coûts négatifs et partez de là !
Je pense que l'algorithme de Dijkstra sert à trouver le chemin le plus court.
cmcculloh recherche le coût minimal sous la contrainte de l'arriver sur place en 5 jours.
Ainsi, le simple fait de trouver le moyen le plus rapide ne l'y amènera pas au moins cher, et y arriver au moins cher ne l'y amènera pas dans le laps de temps requis.
