algo Branch & Bound

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

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

je savais que c'etait une methode plus particulire du backtracking mais apres...

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 ^