Branch and Bound Codificando el Algoritmo desde Cero

Codificando el Algoritmo Branch and Bound desde Cero

Una comprensión más profunda del algoritmo en lenguaje de programación Python

Introducción

Si vienes del artículo introductorio: Branch and Bound – Introducción Antes de Codificar el Algoritmo Desde Cero, entonces esta es la parte donde avanzamos en nuestra comprensión del algoritmo al codificarlo desde cero. Esto siempre me ayuda a entender el funcionamiento del algoritmo, avanzando en el pensamiento algorítmico o computacional que necesito en mi profesión.

Si has encontrado este artículo sin haber leído el artículo introductorio, te sugiero que leas los conceptos detrás del algoritmo y entiendas el flujo de trabajo antes de probar el código a continuación. Como queremos evitar contenido redundante, omitiremos la explicación del algoritmo de ‘branch and bound’ y nos enfocaremos directamente en la codificación.

Revisión rápida del algoritmo:

El algoritmo de ‘Branch and Bound’, cuando se utiliza para resolver programas lineales y en el contexto de la programación entera, sigue los siguientes pasos generales.

1. Inicialización – Inicializa la variable con el valor menos óptimo. Si estás maximizando, el valor debe establecerse en menos infinito, y viceversa para un problema de minimización. La razón de esto es que el proceso recursivo del código debe esforzarse por encontrar una solución mejor y una ejecución del algoritmo ya debe proporcionar una solución mejor.
2. Relajación de la Programación Lineal – El problema principal se resolvería si no se aplicara la restricción entera. Por lo tanto, “relajamos” esa restricción y la tratamos como un programa lineal normal, de ahí el término “relajación de la programación lineal”. Este paso se realiza para cada subproblema.
3. Verificación de Integralidad – Si la solución inicial ya es integral, el programa termina. Esta condición también se verifica para cada subproblema.
4. Ramificación – Si la solución óptima no es integral, entonces el problema se descompone (o se “ramifica”) en subproblemas más pequeños. Esto se hace agregando restricciones a…

• Ryan Johnson, Director de Producto Principal en CallRail – Serie de Entrevistas
• Conoce GlotLID Un modelo de Identificación de Lenguaje (LID) de código abierto que admite 1665 idiomas.
• Detección de objetos en tiempo real con SSD Detectores de cuadro único multibosque

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