Explicación de ramas y límites

Tengo una prueba sobre la rama y el algoritmo enlazado . Entiendo teóricamente cómo funciona este algoritmo, pero no pude encontrar ejemplos que ilustren cómo este algoritmo puede implementarse prácticamente.

Encontré algunos ejemplos como este, pero todavía estoy confundido al respecto. También busqué el problema del vendedor ambulante y no pude entenderlo.

Lo que necesito son algunos problemas y cómo pueden resolverse estos problemas mediante el uso de ramificación y enlace.

Apliquemos Branch and Bound a Knapsack , con suerte esto le aclarará el concepto.

$n$$1$$n$$v_i$$i$$w_i$$T$

$v_1$$n-1$$v_1$$n-1$

$i$$i$$n$$O(2^n)$

$T$$n/2$$n/2+1$$n$$n/2+1$$n$$2^{n/2}$

$d$$O(2^d)$

Tenga en cuenta que esto se llama ' Límite ' porque generalmente implica algún tipo de límite inferior o superior: para el criterio ' incluso si agrego todos los elementos restantes, el valor de los elementos que he agregado no excederá la mejor configuración He encontrado hasta ahora ', el valor de su mejor configuración hasta el momento es un límite inferior en la mejor configuración, por lo que cualquier cosa que nunca supere este límite inferior está condenado al fracaso.

Puede hacer que la parte 'Límite' sea tan compleja como desee. Por ejemplo, los problemas de programación de enteros a menudo se resuelven usando relajaciones: relaja su programa a un programa lineal, que puede resolver en tiempo polinómico, y luego puede descartar muchos casos para sus variables binarias que nunca funcionarán de todos modos. Luego se ramifica en las opciones restantes.

Tenga en cuenta que Branch and Bound generalmente solo le da un aumento de velocidad en la práctica, pero no en teoría: es difícil decir exactamente cuánto del árbol de búsqueda se corta utilizando sus heurísticas. Esto se demuestra por el número de heurísticas diferentes utilizadas en la práctica en tales problemas. Si no tienes suerte, el árbol de búsqueda restante sigue siendo enorme incluso con muchos límites.

Considere la programación , la tarea de asignar trabajos con ciertas duraciones y plazos a las máquinas. Asumimos un tiempo discreto. Muchos de estos problemas son NP (O) -hard.

$1 \mid r_i \mid L_\max$

• en una máquina
• problemas con las fechas de lanzamiento y nosotros
• minimizar la tardanza máxima , que es la diferencia máxima entre la fecha límite y el tiempo de finalización en todos los trabajos.$L_\max$

La versión de decisión de este problema es NP-hard; esto se puede ver por reducción de 3PARTITION .

Curiosamente, si permitimos la preferencia , que es intercambiar trabajos activos, el problema puede resolverse en tiempo cuadrático mediante la primera heurística de fecha de vencimiento más temprana (en fechas de vencimiento modificadas). Es fácil ver que la solución óptima de esta variante no puede ser peor que la solución óptima del problema original.

Ahora, para aplicar Branch & Bound a este problema, necesitamos corregir algunos parámetros:

• Calculamos los límites inferiores al permitir la preferencia y el uso de EDD.
• Nos ramificamos arreglando cada uno de los trabajos no programados como el siguiente.
• Vamos al niño con el límite inferior más pequeño primero.

Tienes que hacer esto para cada aplicación de B&B.

Para un ejemplo concreto, considere esta instancia de :$1 \mid r_i \mid L_\max$

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p_i & 4 & 2 & 6 & 5 \\ r_i & 0 & 1 & 3 & 5 \\ d_i & 8 & 12 & 11 & 10 \end{array}$

con los tiempos de procesamiento de los trabajos, las fechas de lanzamiento y las fechas de vencimiento.$p_i$$r_i$$d_i$

Ejecutando B & B como se especifica anteriormente, esto sucede:

_{Este GIF no se repite. Vuelva a cargarlo en una nueva pestaña para verlo desde el principio.}
^{[ fuente ] [ versión estática ]}

Tenga en cuenta que de 41 nodos, solo cuatro se visitan correctamente y solo para diez se calculan los límites inferiores.