Procédure Branch And Bound

Inhaltsverzeichnis

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

Inhaltsverzeichnis 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.

Inhaltsverzeichnis 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)

Inhaltsverzeichnis 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.

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 03/01/2010, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-branch-and-bound.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen
  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".

Inhaltsverzeichnis Haut

Referenzen

  1. Buch Sprache des Dokuments:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut