Le 08/06/2011 par pierrecogitae :

Salut,
Je vais devoir effectuer une optimisation de parcours d'arborescence orientée étiquetée aux sommets. Les sommets représentent des obstacles sur mon parcours.
Chaque obstacle est identifié et a 2 valeurs
- Nombre de cacahouètes que je trouve sur ce sommet,
- Coût pour pouvoir détruire l'obstacle et avoir ses cacahouètes.
Aucun problème pour revenir en arrière une fois l'obstacle passé, je ne peux pas accéder à un sommet sans avoir détruit tous les obstacles qui y mènent, je pars toujours de la racine de l'arbre.
Le but est le suivant: J'ai X euros disponibles, il faut trouver comment obtenir le plus grand nombre de cacahouètes en restant dans le budget.
Ma pratique de la RO est ancienne (depuis la fac!) et je vois à peu près le genre de techniques à mettre en place, mais je voudrais demander si quelqu'un a des pistes, des recommandations ou des pièges à éviter.
Dispo pour toute question supplémentaire si mon exposé n'est pas clair.
Merci!

Le 09/06/2011 par Acrima :

Pour moi, il s'agit d'un problème de sac à dos (maximiser le nombre de cacahouètes tout en respectant la limite d'argent) avec des contraintes de précédences (qui vont accélérer la résolution du problème en le structurant). Qu'en pensez vous ?

Le 09/06/2011 par Acrima :

ps: Vous pouvez chercher du cote des "Partially ordered knapsack".