Branch and Bound – Coder l’algorithme à partir de zéro

Branch and Bound - Programmation de l'algorithme de A à Z

Une compréhension plus profonde de l’algorithme en langage de programmation Python

Introduction

Si vous avez lu l’article introductif : Branch and Bound – Introduction avant de coder l’algorithme à partir de zéro, alors c’est là que nous progressons dans notre compréhension de l’algorithme en le codant à partir de zéro. Cela m’aide toujours à comprendre le fonctionnement de l’algorithme, à avancer dans ma réflexion algorithmique ou computationnelle nécessaire dans ma profession.

Si vous êtes tombé sur cet article sans avoir lu l’article introductif, je vous suggère de lire les concepts derrière l’algorithme et de comprendre le flux de travail avant d’essayer le code ci-dessous. Comme nous voulons éviter les contenus redondants, nous passerons l’explication de l’algorithme de branch and bound et nous lancerons directement dans le codage.

Révision rapide de l’algorithme :

L’algorithme de Branch and Bound, utilisé pour résoudre des programmes linéaires et dans le contexte de la programmation entière, suit les étapes générales suivantes :

1. Initialisation – Initialiser la variable pour qu’elle ait la valeur la moins optimale. Si vous maximisez, la valeur doit être réglée sur moins l’infini, et inversement pour un problème de minimisation. La raison en est que le processus récursif du code devrait chercher à trouver une meilleure solution et qu’une seule exécution de l’algorithme fournirait déjà une meilleure solution.
2. Relaxation de la programmation linéaire – Le problème principal serait résolu si la contrainte entière n’était pas appliquée. Par conséquent, nous “relâchons” cette contrainte et la traitons comme un programme linéaire normal, d’où le terme “relaxation de la programmation linéaire”. Cette étape est effectuée pour chaque sous-problème.
3. Vérification de l’intégralité – Si la solution initiale est déjà intégrale, le programme se termine. Cette condition est également testée pour chaque sous-problème.
4. Ramification – Si la solution optimale n’est pas entière, alors le problème est décomposé (ou “branché”) en sous-problèmes plus petits. Cela se fait en ajoutant des contraintes…

• Comment l’IA stimule la fintech 7 industries prometteuses alimentées par l’IA à suivre
• Se mettre en œuvre de la détection de transactions frauduleuses en utilisant les MLOPs
• Middleware.io présente une plateforme d’observabilité cloud alimentée par l’IA générative.

We will continue to update IPGirl; if you have any questions or suggestions, please contact us!