Trouver le chemin minimal dans une arborescence avec des nœuds à plusieurs valeurs

Question

Mes cours de mathématiques sont loin derrière et je lutte pour trouver une solution décente à un problème que je rencontre: j'ai un arbre dans lequel les nœuds sont des actions et sont "pondérés". selon de multiples critères: le coût de cette action, le temps qu’elle prendra, les ressources nécessaires, la perturbation, etc ...

Et je veux trouver dans cet arbre le chemin qui minimise le coût ET le temps par exemple, ou la perturbation ET le coût ET le temps, etc. Mon problème est que je n'ai aucune idée de la façon de le faire, sauf en proposant une fonction de coût global F (coût, temps, ressources, ...) et appliquez un algorithme de traversée d'arbre classique en utilisant le résultat de F (...) comme seul poids. Mais alors, comment puis-je venir avec F? Quelque chose comme " F (coût, temps, ressources) = a * cout + b * temps + c * ressources " se sent très "non professionnel" ...

Modifier:

Je voulais éviter le mot "sommation". comme je n’étais pas sûr que c’était vraiment la voie à suivre, mais c’est essentiellement ce que je suis en train de faire: calculer un coût total pour chaque "chemin". ou " branche " qui va de ce nœud supérieur, à l’un des feuilles, et en choisissant le "chemin" ou " branche " cela minimise le coût. Le problème est que chaque noeud a un poids basé sur le temps nécessaire, les coûts financiers, l’utilisation des ressources, etc.

Donc, il semble inévitable de devoir trouver une formule, comme le dit Stephan, qui réduira tous ces paramètres à un coût global, par nœud, que je peux ensuite résumer sur des nœuds tout en parcourant l'arbre, et choisir le chemin qui minimise le coût total.

Donc, je suppose que ma question est vraiment la suivante: existe-t-il une méthodologie pour choisir cette fonction?

Merci pour vos réponses et vos commentaires, cela commence à être un peu plus clair dans ma tête maintenant.

Answer 1

Disons que nous avons quatre paires (x, y) comme (1, 4), (1, 5), (2, 3), (3, 3). Maintenant, vous voulez minimiser "x et y". Que voulez-vous dire? Si vous minimisez d'abord x puis y, vous vous retrouvez avec (1, 4). Si vous minimisez d'abord y puis x, vous trouvez (2, 3).

À moins que vous choisissiez une fonction de coût global F (x, y), comme dans votre observation, je ne vois aucune signification de "les deux". (De toute façon, une fois que F est choisi, il peut rester plusieurs points minimum.) En passant, à mon avis, une combinaison linéaire (les multiplicateurs positifs a, b, c étant compris comme des "poids") n'est pas "peu professionnelle" du moins, du moins si vous n’avez aucune idée de ce que pourrait être une fonction de coût plus appropriée.

Modifier:

  

Donc, il semble inévitable de devoir trouver une formule, comme le dit Stephan, qui réduira tous ces paramètres à un coût global, par nœud, que je peux ensuite résumer sur des nœuds tout en parcourant l'arbre, et choisir le chemin qui minimise le coût total.

Attention. En effet, cette stratégie n’a de sens que si F est linéaire. Les coûts, le temps, les ressources, etc. sont sûrement des fonctions additives, en ce sens que le temps (noeud1 - > noeud2 - > noeud3) = temps (noeud1) + temps (noeud2) + temps (noeud3), mais en général ce n'est pas le cas de F, à moins que ce ne soit linéaire. (c.-à-d. F (coût (noeud1 - > noeud2)) = F (coût (noeud1) + coût (noeud2))! = F (coût (noeud1)) + F (coût (noeud2)).)

Si vous choisissez une fonction de coût global non linéaire, la bonne stratégie consiste à calculer, pour chaque nœud, le coût total, le temps total, les ressources totales de la racine à ce nœud, et à calculer (puis réduire) F uniquement pour le terminal. nœuds.

Answer 2

Venir avec F est la chose la plus importante. Si je peux vous donner 6 coûts et 5 temps ou 5 temps et 6 coûts, que préférez-vous? Votre fonction de coût doit en tenir compte. Malheureusement, aucun algorithme ne résoudra ce problème. Je l'ai nié pendant une semaine avant de m'asseoir et d'écrire F pour une application d'optimisation sur laquelle je travaillais. Dans le pire des cas, laissez les paramètres sur lesquels l'utilisateur peut bricoler.

Answer 3

Pourquoi un algorithme de recherche de graphes normal tel que A * ne fonctionne-t-il pas?

Pour la fonction de coût du trajet, vous pouvez utiliser la somme cumulée des critères pertinents. La distance au but est plus difficile ...

Cela pourrait être la distance de la feuille la plus proche, pré-calculée pour tout ou partie des nœuds, bien que cela puisse sembler extrêmement coûteux. Selon la structure de votre arbre, vous pouvez obtenir une sous-estimation moins chère. Si elle est parfaitement équilibrée, par exemple, elle est triviale.