algo Branch & Bound

Discussion dans 'Web, design' créé par leprincemiri, 9 Août 2007.

Statut de la discussion:
Fermée.
  1. Offline
    leprincemiri ex membre
    Hello à tous
    j'ai un travail à faire en rapport avec l'algorithme Branch & Bound, hélas je ne trouve pas d'explication dessus, quelqu'un pourrait me renseigner?
    merci d'avance
    leprincemiri, 9 Août 2007
    #1
  2. Offline
    AcidBird Touriste
    Google est ton Amis :)

    "Branch and bound" et "branch and bound implementation" devrait t'aider ;o). Sinon, je connais pas cet algo mais d'après ce que j'ai lu (en diagonale), c'est un algo décisionnel te permettant d'évaluer / choisir la meilleur solution à un problème. En gros, tu crées un arbre avec toute les solution possible à un problème pour trouver la meilleur ... maintenant, faut creuser un peu le sujet j'pense :p
    AcidBird, 9 Août 2007
    #2
  3. Offline
    leprincemiri ex membre
    je savais que c'etait une methode plus particulire du backtracking mais apres... :D
    leprincemiri, 9 Août 2007
    #3
  4. Offline
    Eagor Croqueur de pomme
    Je te conseille le mivre de Jacques Teghem "La programmation lineaire" aux éditions de l'ULB.
    L'algorithme y est tres bien décrit tout comme plein d'autres.

    Sinon dans le principe faut scinder tes ensembles de solutions hiérarchiquement. SI t'as une fonction à minimiser, à chaque noeud tu calcules une borne inférieure de ta sous-solution optimale. Si elle est plus grande que ta valeur de fonction objectif déjà trouvée, tu peux couper cette branche et passer à une suivante.
    Le plus dur étant de bien couper tes ensembles de solutions pour ne pas en perdre et de trouver une fonction d'évaluation de la borne inférieure qui se veut la plus haute possible pour couper des branches au plus vite.

    Ca c'est le principe ^
    Eagor, 13 Août 2007
    #4
Statut de la discussion:
Fermée.