Optimisation de parcours d'arborescence orient
Forum 'Discussions' - Sujet créé le 2011-06-08
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!
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!