Procédure Branch And Bound

Inhoudsopgave

Fonctionnalités de la procédure Branch And Bound

  • Nous pouvons utiliser la procédure Branch And Bound en tant qu'algorithme de recherche de chemin extrême.
  • Nous utiliserons la procédure Branch And Bound sur des graphes pondérés1
  • Nous pouvons utiliser la procédure Branch And Bound sur des graphes aux pondérations quelconques, et des graphes avec circuits ou sans circuits.

Caractéristiques de la procédure Branch And Bound

Le Branch And Bound, ou en français Procédure de séparation et d'évaluation progressive, est une application du principe "diviser pour régner" appliquée à la résolution de problèmes d'optimisation.

Nous pouvons appliquer la procédure Branch And Bound à de nombreux problèmes NP-complets, qu'il s'agisse de la théorie des graphes ou non. Parmi les exemples les plus connus, nous avons le problème du voyageur de commerce (TSP pour Traveling Salesman Problem).

La méthode Branch And Bound a longtemps été considérée comme le meilleur moyen pour la recherche de circuit hamiltonien de poids minimum (le problème du voyager de commerce), bien qu'à présent les méthodes telles que la programmation quadratique convexe2 ou les metaheuristiques3

Inhoudsopgave Haut

Séparation et évaluation

  • Dans la partie séparation, nous diviserons le problème afin de constituer un "arbre de décisions".
  • Dans la partie évaluation, nous déciderons vers quelle branche de l'arbre nous allons poursuivre nos investigations.

Profondeur maximale de l'arbre Branch And Bound

Dans le pire des cas nous pouvons construire un arbre qui dégénère en une liste chaînée, et que pour chaque sommet l'arc à sélectionner est le dernier. Dans ce cas, notre profondeur maximale est de n2.

Dans le cas d'une optimisation en variables binaires, une variable est définie pour chaque branche, et la profondeur maximum est réduite à n.

Si nous utilisons des variables d'un autre type (par exemple en programmation en variables entières bornées), la profondeur de l'arbre Branch And Bound dépend du domaine de ce type de variable.

Inhoudsopgave Haut

Algorithme de Little

L'lgorithme de Little est une simplification du Branch And Bound. Il se décompose de la manière suivante :

  • Initialisation
    1. Réduction de la matrice (RM)
      • Réduction en ligne : soustraire le plus petit élément de chaque ligne, ce qui nous permet d'avoir pour chaque ligne au moins un 0.
      • Réduction en colonne : soustraire le plus petit élément de chaque colonne, ce qui nous permet d'avoir pour chaque colonne au moins un 0.
    2. Calcul de la borne inférieure (BI).
  • Branch And Bound
    1. Calcul des coûts d'évitement (CE)
      CE(x,y) = min{Pxi+Pjy | i≠y ∧ j≠x}
    2. Sélection de l'arc (x,y) avec CE(x,y) maximal
    3. Branchement (création de l'arborescence)
      • Branche P1 si nous passons par (x,y)
      • Branche P2 si nous évitons de passer par (x,y)

Inhoudsopgave Haut

A* vs Branch And Bound

A* est heuristique4, alors que la procédure Branch And Bound est un algorithme qui fournit la solution optimale du problème.

Comme la procédure Branch And Bound peut effectuer des backtrackings5 et se retrouver avec un domaine des solutions assez vaste, il peut sembler beaucoup plus lent que l'heuristique A*. Toutefois, si nous sommes pressés, nous pouvons arrêter l'algorithme Branch And Bound avant son exécution complète à partir du moment où il a trouvé au moins un chemin possible.

Nous ne sommes pas dans ce cas assurés d'être en présence du chemin optimal, mais nous avons assez rapidement un chemin parmi les meilleurs.

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 03/01/2010 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-branch-and-bound.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes
  1. ↑ pondération : La pondération est une valeur associée à un arc (ou une arête), et correspond au coût du passage par cet arc. Par exemple, il peut s'agir d'une distance entre deux villes représentées chacune par un sommet du graphe.

  2. ↑ Programmation quadratique convexe : La programmation quadratique convexe permet de réduire la taille de l'arborescence lors du "Branch And Bound".

  3. ↑ Metaheuristique : Algorithmes d'optimisation. Généralement des algorithmes aléatoires qui fonctionnent par apprentissage des caractéristiques du problème pour tenter de trouver une meilleure solution.

  4. ↑ Heuristique : En optimisation combinatoire et en théorie des graphes, le terme "heuristique" est utilisé pour décrire le fait que cet algorithme soit approximatif, et pas nécessairement optimal.

  5. ↑ Backtracking : Si la nouvelle borne en cours de recherche est supérieure à une borne d'une branche que nous avions délaissée, nous devons remonter dans l'arbre jusqu'à cette branche et reprendre notre recherche. Le terme utilisé est le terme anglais "Backtracking".

Inhoudsopgave Haut

Referenties

  1. boek Taal van het document:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut