Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Résultats du Branch and bound


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Résultats du Branch and bound
    Bonjour

    J'applique l'algorithme de branch and bound dans le but de résoudre un problème de sac à dos
    J'aimerais savoir si c'est normal qu'en fonction du choix de l'ordre des contraintes les solutions sont différentes

    Exemple
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    x1 , x2 , x3
     
    Si je commence avec x1 mon arbre me donne 20 feuilles 
     
    Si je mélange l'ordre x2 x3 x1 mon arbre de donne 12 feuilles


    Merci de vos réponses

  2. #2
    Membre actif
    mais bien sur : le fait de stériliser une branche dépend de la valeur que prend la variable et donc cela dépend énormément du choix de la variable , tout ce qu'il y a de logique.

  3. #3
    Membre régulier
    Merci pour la réponse

    Mais j'aimerais savoir si le resultat optimal est garanti quelque soit l'ordre que l'on choisit ????