¿Qué es un algoritmo de ramificación?
Algoritmo de rama y límite:
El algoritmo de rama y límite es un método para buscar una solución a un problema en el árbol del espacio de soluciones del problema. Sin embargo, a diferencia del algoritmo de retroceso, el algoritmo de rama y límite utiliza el método de primero en amplitud o de costo mínimo primero para buscar en el árbol del espacio de soluciones, y en el algoritmo de rama y límite, cada nodo activo tiene solo una oportunidad. convertirse en un nodo de expansión.
Utilice el algoritmo de rama y ligada para buscar el árbol del espacio de solución del problema. Su estrategia de búsqueda es:
1. Genere todos los nodos secundarios del nodo de expansión actual
2. Entre los nodos secundarios generados, descarte aquellos nodos que probablemente no produzcan soluciones factibles (o soluciones óptimas);
3. Agregue los nodos secundarios restantes a la tabla de nodos activos
4. Seleccione el siguiente nudo corredizo de la tabla de nudos corredizos como nuevo nodo de extensión.
Este ciclo continúa hasta que se encuentra una solución factible (solución óptima) al problema o la mesa de Slipknot está vacía.
Seleccione el siguiente nodo activo de la tabla de nodos activos como un nuevo nodo de extensión. Dependiendo del método de selección, el algoritmo de bifurcación y vinculación generalmente se puede dividir en dos formas:
1. ． Algoritmo de bifurcación y vinculación FIFO (primero en entrar, primero en salir): seleccione el siguiente nodo activo como nodo de expansión de acuerdo con el principio de primero en entrar, primero en salir, es decir, el orden de eliminación de nodos de la tabla de nodos activos es el Igual que el orden de agregar nodos.
2. Rama de costo mínimo o beneficio máximo y algoritmo ligado: En este caso, cada nodo tiene un costo o beneficio. Si desea encontrar una solución con el costo mínimo, entonces el siguiente nodo de expansión a seleccionar es el nodo activo con el costo mínimo en la tabla de nodos activos, si desea encontrar una solución con el máximo beneficio, entonces la siguiente expansión; El nodo a seleccionar es el nudo corredizo con mayor beneficio en la tabla de nudos corredizos.
También conocido como método de búsqueda en rama y encuadernado. Un tipo de método para la síntesis de sistemas de procesos. Este método descompone el problema original en un conjunto de subproblemas. La ramificación es dividir un conjunto de soluciones en varios grupos de subsoluciones, y la delimitación es establecer los límites de las funciones objetivas de estas soluciones de subgrupos. Si la solución de un determinado subgrupo está fuera de estos límites, este subgrupo se descarta (se poda). El método de ramificación y unión era originalmente un método para resolver problemas de programación entera (o programación entera mixta) en investigación de operaciones. Este método es muy eficiente para encontrar la solución óptima entera. La aplicación de los principios de este método a la síntesis del sistema de procesos puede reducir significativamente la cantidad de días necesarios para calcular los escenarios.
La idea del método de rama y límite es: primero determinar los límites superior e inferior del valor objetivo y luego restar ciertas ramas del árbol de búsqueda durante la búsqueda para mejorar la eficiencia de la búsqueda.
En las competiciones, a veces nos encontramos con algunos problemas que no se pueden resolver estableciendo modelos matemáticos, y no existen algoritmos listos para usar que se puedan aplicar, o no se pueden obtener los resultados correctos atravesando todas las situaciones. En este momento, debemos utilizar un algoritmo de búsqueda para solucionar el problema.
Los algoritmos de búsqueda se dividen en dos categorías según los métodos de búsqueda, una es la búsqueda en profundidad y la otra es la búsqueda en amplitud. Sabemos que la búsqueda profunda es simple de programar, el programa es conciso y fácil de entender, y el requisito de espacio es relativamente bajo. Sin embargo, la complejidad temporal de este método suele ser exponencial. Si no se optimiza, su eficiencia temporal es simplemente. intolerable; aunque la búsqueda en amplitud es menor que la primera, sus enormes requisitos de espacio suelen ser prohibitivos.
Por lo tanto, la optimización del programa se ha convertido en la parte más crítica de la programación del algoritmo de búsqueda.
Lo que tratará este artículo es la "poda", un método básico para optimizar programas en algoritmos de búsqueda.
¿Qué es la poda?
Creo que las personas que son nuevas en los algoritmos de búsqueda han resuelto problemas como laberintos.
Cuando estamos "caminando por el laberinto", la idea general de retroceder es la siguiente:
1 Hay un camino por recorrer en esta dirección, pero no lo he recorrido
2. Ve en esta dirección
3. Es un callejón sin salida, regresa a la intersección anterior
4. Repite el primer paso hasta encontrar la salida<. /p>
Esta idea es muy simple. Es fácil de entender y fácil de programar. Pero cuando la escala del laberinto es muy grande, las deficiencias del método de retroceso quedan expuestas: la búsqueda lleva mucho tiempo y es insoportable.
Cuando nos movemos en una determinada dirección, ¿podemos juzgar primero si esto nos llevará a un callejón sin salida? ¿De esta forma no se reduciría el tiempo de búsqueda?
La respuesta es: sí.
El concepto de poda es en realidad similar a caminar por un laberinto para evitar callejones sin salida. Si consideramos el proceso de búsqueda como atravesar un árbol, entonces la poda, como su nombre indica, es "cortar" algunos "callejones sin salida" en el árbol y las ramas que no pueden alcanzar la solución que necesitamos, para reducir el tiempo de búsqueda.
La mayoría de los algoritmos de búsqueda requieren poda. Sin embargo, no se pueden cortar todas las ramas, lo que requiere diseñar un método de juicio razonable para decidir si se elige una determinada rama. Al diseñar un método de juicio, es necesario seguir ciertos principios.
Principios de la poda
1. Corrección
Como se mencionó anteriormente, las ramas no se pueden cortar solo porque te gusten. Si podas al azar y cortas la rama con la solución óptima, la poda perderá su sentido. Por tanto, la premisa de la poda es conseguir que no se pierdan los resultados correctos.
2. Precisión
Para garantizar la corrección, debemos analizar los problemas específicos en detalle y utilizar métodos de juicio adecuados para asegurarnos de que las ramas que no contienen el óptimo. La solución es que la mayoría de ellos pueden cortarse para lograr el propósito de "optimizar" el programa. Se puede decir que la precisión de la poda es un criterio para medir la calidad de un algoritmo de optimización.
3. Eficiencia El propósito fundamental del diseño de un programa de optimización es reducir el número de búsquedas y reducir el tiempo de ejecución del programa. Pero para reducir la cantidad de búsquedas tanto como sea posible, debemos dedicar tiempo a diseñar un algoritmo de optimización con mayor precisión. Cuando aumenta la precisión del algoritmo, la cantidad de juicios inevitablemente aumentará, lo que conducirá a un aumento en el tiempo. consumo, lo que lleva a una contradicción.
Por lo tanto, también es muy importante encontrar un equilibrio entre optimización y eficiencia para reducir al máximo la complejidad temporal del programa. Si el efecto de juicio de una poda es muy bueno, pero lleva mucho tiempo juzgar y comparar, el resultado es que todo el programa se ejecuta de la misma manera que uno que no ha sido optimizado, lo que no vale la pena ganar.
En resumen, podemos resumir los principios fundamentales de la optimización de la poda en seis palabras: correcto, preciso y eficiente.
Los algoritmos de poda se pueden dividir aproximadamente en dos categorías según sus ideas de juicio: poda de viabilidad y poda óptima.
Para el algoritmo de rama y límite, el límite superior es el mínimo de los valores de la función objetivo de las soluciones factibles que se han obtenido, que se divide en un límite superior inicial y un límite superior dinámico generado. durante el proceso de detección Bifurcación y límite En el proceso iterativo de encontrar la solución óptima, si el límite inferior estimado de un nodo no es menor que el límite superior conocido, no es necesario continuar buscando desde ese nodo. se puede generar un mejor límite superior, se pueden eliminar muchos problemas Cálculos de enumeración innecesarios.
Implementación del algoritmo de bifurcación y límite
Antes de describir los pasos del algoritmo de bifurcación y límite, los relevantes Los términos involucrados en el algoritmo se definen de la siguiente manera:
p——El número de niveles de rama;
C*——El valor actual óptimo de la función objetivo;
P*——La secuencia de la pieza de trabajo correspondiente a C*;
p>
P1——La secuencia parcial correspondiente al nodo actual (el nodo que necesita ser ramificado ahora).
Los pasos de implementación del algoritmo de rama y enlace son los siguientes:
Paso 1 Inicialización: Establecer p = 0, P 1 = ? (conjunto vacío), C* = ∞. el nodo actual siempre corresponde a P 1. En este momento, el nodo actual es el nodo raíz.
Paso 2 Cálculo El límite inferior de cada nodo secundario se obtiene de la rama del nodo actual y los nodos secundarios se ordenan de pequeño a grande por el valor del límite inferior Sea p ←p 1.
Paso 3 Si el nodo actual está agotado, sea p ←p - 1, vaya al paso 6. De lo contrario, suponga que el nodo. con el valor de límite inferior más pequeño entre los subnodos activos de la capa actual (p-ésima capa) es Q, luego agregue Q al final de P 1 correspondiente a la pieza de trabajo en la p-ésima posición, en este momento Convierta el nodo actual a Q y vaya al paso 4.
Paso 4 Debido a que el nodo actual es el nodo con el mismo nodo principal en la misma capa y el valor de límite inferior más pequeño, si el valor de límite inferior del actual nodo es mayor o igual a C*, no es necesario buscar el nodo actual y sus nodos activos en el mismo nivel y en el mismo padre. De esta manera, se han detectado los nodos de nivel superior (nodos principales) del nodo actual. , p ←p - 1, elimine el último artefacto en P 1 y vaya al paso 6. De lo contrario, vaya al paso 5.
Paso 5 Si p = n, obtenga un orden mejor. = P 1, C* sea el valor límite inferior del nodo actual, p ←p - 1, elimine P. Para la última pieza de trabajo en 1, vaya al paso 6, de lo contrario, vaya al paso 2.
Paso 6 Si p ≠ 0, retire la última pieza de trabajo en P 1, vaya al paso 3; de lo contrario, el algoritmo se detiene. C* es el valor máximo de la función objetivo, P* es el orden óptimo.
Implementación del algoritmo de estructura de ramas (conceptos básicos de programación)
Ahora he aprendido la estructura de ramas. Encontré un problema nuevamente. Me pregunto si todavía estás aquí. ¿Puedes ayudarme? (Sí, no hay problema).
1. Usa el lenguaje Pascal para expresar la siguiente expresión condicional:
(1): x es menor que 10;
(2): 0lt; =ylt =5 (no se reproducirá 'menor o igual a')
(3): x es mayor que 5 o x es un número negativo;
(4): ch está entre "A" y "Z" (incluidos "A" y "Z"); /p>
(5): La edad (edad) no es menor de 18 años y la nacionalidad (natioality) no es un ciudadano varón de China "CHINA" o Corea del Norte "COREA" (sex=`maie`) ;
(6): Número positivo, entre 2 y 100 y no divisible por 2, 3 o 5.
2. Intente escribir las declaraciones de Pascal para los siguientes elementos:
(1): Si el salario es mayor que 10000, reste 10 salarios. (2): Si el valor de Elección es 1, lea el valor de x e imprima el cuadrado de x; de lo contrario, lea el valor de y e imprima el cuadrado de y;