Algoritmo paralelo: técnicas de diseño
Seleccionar una técnica de diseño adecuada para un algoritmo paralelo es la tarea más difícil e importante. La mayoría de los problemas de programación paralela pueden tener más de una solución. En este capítulo, discutiremos las siguientes técnicas de diseño para algoritmos paralelos:
- Divide y conquistaras
- Método codicioso
- Programación dinámica
- Backtracking
- Rama y atado
- Programación lineal
Método de dividir y conquistar
En el enfoque de divide y vencerás, el problema se divide en varios subproblemas pequeños. Luego, los subproblemas se resuelven de forma recursiva y se combinan para obtener la solución del problema original.
El enfoque de divide y vencerás implica los siguientes pasos en cada nivel:
Divide - El problema original se divide en subproblemas.
Conquer - Los subproblemas se resuelven de forma recursiva.
Combine - Las soluciones de los subproblemas se combinan para obtener la solución del problema original.
El enfoque de divide y vencerás se aplica en los siguientes algoritmos:
- Búsqueda binaria
- Ordenación rápida
- Combinar ordenación
- Multiplicación de enteros
- Inversión de matriz
- Multiplicación de matrices
Método codicioso
En el codicioso algoritmo de optimización de la solución, se elige la mejor solución en cualquier momento. Un algoritmo codicioso es muy fácil de aplicar a problemas complejos. Decide qué paso proporcionará la solución más precisa en el siguiente paso.
Este algoritmo se llama greedyporque cuando se proporciona la solución óptima para la instancia más pequeña, el algoritmo no considera el programa total como un todo. Una vez que se considera una solución, el algoritmo codicioso nunca vuelve a considerar la misma solución.
Un algoritmo codicioso funciona de forma recursiva creando un grupo de objetos a partir de las partes componentes más pequeñas posibles. La recursividad es un procedimiento para resolver un problema en el que la solución a un problema específico depende de la solución de la instancia más pequeña de ese problema.
Programación dinámica
La programación dinámica es una técnica de optimización, que divide el problema en subproblemas más pequeños y después de resolver cada subproblema, la programación dinámica combina todas las soluciones para obtener la solución definitiva. A diferencia del método de divide y vencerás, la programación dinámica reutiliza la solución a los subproblemas muchas veces.
El algoritmo recursivo para la serie Fibonacci es un ejemplo de programación dinámica.
Algoritmo de retroceso
El retroceso es una técnica de optimización para resolver problemas de combinación. Se aplica a problemas tanto programáticos como de la vida real. El problema de las ocho reinas, el Sudoku y atravesar un laberinto son ejemplos populares en los que se utiliza un algoritmo de retroceso.
Al retroceder, comenzamos con una posible solución, que satisface todas las condiciones requeridas. Luego pasamos al siguiente nivel y si ese nivel no produce una solución satisfactoria, regresamos un nivel hacia atrás y comenzamos con una nueva opción.
Rama y atado
Un algoritmo de bifurcación y acotación es una técnica de optimización para obtener una solución óptima al problema. Busca la mejor solución para un problema dado en todo el espacio de la solución. Los límites de la función que se va a optimizar se fusionan con el valor de la última mejor solución. Permite que el algoritmo encuentre partes del espacio de la solución por completo.
El propósito de una búsqueda de bifurcaciones y límites es mantener la ruta de menor costo hacia un objetivo. Una vez que se encuentra una solución, puede seguir mejorando la solución. La búsqueda de bifurcaciones y límites se implementa en la búsqueda con límites de profundidad y la búsqueda en profundidad.
Programación lineal
La programación lineal describe una amplia clase de trabajo de optimización donde tanto el criterio de optimización como las restricciones son funciones lineales. Es una técnica para obtener el mejor resultado, como la máxima ganancia, el camino más corto o el costo más bajo.
En esta programación, tenemos un conjunto de variables y tenemos que asignarles valores absolutos para satisfacer un conjunto de ecuaciones lineales y maximizar o minimizar una función objetivo lineal dada.