Ejemplo de implementación en Python de algoritmo de rama y límite

Objetivo de la solución: el objetivo de la solución del método de rama y límite es encontrar una solución que satisfaga las condiciones de restricción, o encontrar una solución óptima en un cierto sentido entre las soluciones que satisfacen las condiciones de restricción.

Método de búsqueda: busque en el árbol del espacio de soluciones primero en amplitud o primero en costo mínimo. El método de ramificación y limitación generalmente busca en el árbol del espacio de soluciones de un problema primero en amplitud o en primer lugar con costo mínimo (beneficio máximo).

En el método de rama y restricción, cada nodo activo tiene solo una oportunidad de convertirse en un nodo de expansión. Una vez que un nodo activo se convierte en un nodo extendido, genera todos sus nodos secundarios a la vez. Entre estos nodos secundarios, los nodos secundarios que conducen a soluciones no factibles o no óptimas se descartan y los nodos secundarios restantes se agregan a la tabla de nodos activos.

A partir de entonces, el nodo expandido actual se utiliza como el siguiente nodo en la tabla de nodos en tiempo real y se repite el proceso de expansión de nodos anterior. Este proceso continúa hasta que se encuentra la solución requerida o hasta que la tabla de nodos activos esté vacía.

Ejemplo de método de rama y límite:

Ruta más corta de fuente única:

Pregunta: Dado un gráfico dirigido ponderado G = (V, E), donde El peso de cada arista es un número real. También se da un vértice en V, llamado punto fuente. Ahora calcule la longitud del camino más corto desde el vértice de origen hasta todos los demás vértices. La longitud aquí es la suma de los pesos de todos los bordes del camino.

Análisis:

Los pasos del método de rama y límite son los siguientes:

1) Recorrer el árbol del espacio de solución de acuerdo con la estrategia de amplitud primero

2) Durante el proceso transversal, para cada nodo i que se procesa, de acuerdo con la función límite -bound(i)=[dow(i)=[dow(i)], la función objetivo del proceso completo La solución que se puede alcanzar buscando hacia abajo a lo largo del nodo es el rango estimado de valores posibles. bound(i)=[dow(i), up(i)]

3)? Seleccione nodos con un valor de función objetivo pequeño y realice primero una búsqueda en amplitud, para ajustar continuamente la dirección de búsqueda. lo más pronto posible.

Después de cada rama, no se tomarán más ramas para aquellos subconjuntos cuyos límites excedan los valores de solución factible conocidos. De esta manera, se pueden ignorar muchos subconjuntos de la solución (es decir, muchos nodos en el árbol de búsqueda), reduciendo así el alcance de la búsqueda.

El proceso de convertir este gráfico en un árbol es el siguiente:

Crear una cola. 1. El nodo 1 ingresa a la cola, Q = {1}.

Tomamos el nodo cabecera de la cola como nodo de difusión y actualizamos los valores de sus descendientes. En este problema, las distancias de los nodos 2, 3 y 4 se actualizan y se agregan a la cola Q = {1, 2, 3, 4}. Una vez completado, el nodo 1 abandona la cola, es decir, Q = {2, 3, 4}.

2. De manera similar, repita el paso 1, Q = {3, 4, 5, 6}

3. Cuando tomamos el nodo 3, encontramos que desde el punto de origen - > La distancia entre el nodo 3 -> nodo 6 es 11, que es mayor que el peso de la ruta 1-2-6. Esto es mayor que el peso de la ruta 1-2-6, por lo que no consideraremos la ruta posterior 1-3-6. Ésta es la idea de "restricciones" (llamada "poda").

4. Repetir la operación hasta que Q quede vacío. El método de cola prioritaria es similar al método primero en entrar, primero en salir, excepto que la cola prioritaria selecciona el elemento de la cola con la distancia más corta desde la fuente.

# -*- Codificación: utf-8 -*-

"""

Creado el domingo 7 de marzo 19:03:09 2021 p>

@autor: iron

"""

# Autor: Iron

# Inicialice los parámetros del gráfico usando un diccionario para inicializar esto gráfico

G = {1: {2:4, 3:2, 4:5},

2: {5:7, 6:5},

3: { 6: 9},

4: { 5: 2, 7: 7},

5: { 8: 4},

6: { 10: 6}, ? del Q[0]

? =0:

? dict=G[Q[0]]

'''

#Implementación del método de cola prioritaria

def rama(G, v0):

Q.append(v0)

mientras len(Q)! = 0:

? min=99999

? flag=0

?# Encuentra el punto más cercano a la fuente en la cola

* para v en Q:

* if min gt; longitud[v]:

min=longitud[v]

bandera = v

* cabeza = bandera

* dict = G[cabeza]

?# Encuentra el punto de difusión y realiza relajación

* para clave en dict ：

* if longitud[cabeza] G[cabeza][clave] lt;= longitud[clave]:

longitud[clave] = longitud[cabeza] G[cabeza][ key ]

Q.append(key)

?#Cuando se complete la relajación, el punto de difusión se eliminará de la cola

?Q.remove( head)

'''

rama(G, 1)

print(longitud)

Resultado de ejecución: [9999, 0 , 4, 2, 5, 7, 9, 12, 11, 15, 15].