Algoritmo Paralelo - Técnicas de Projeto
Selecionar uma técnica de projeto adequada para um algoritmo paralelo é a tarefa mais difícil e importante. A maioria dos problemas de programação paralela pode ter mais de uma solução. Neste capítulo, discutiremos as seguintes técnicas de projeto para algoritmos paralelos -
- Dividir e conquistar
- Método ganancioso
- Programaçao dinamica
- Backtracking
- Branch & Bound
- Programação linear
Método de divisão e conquista
Na abordagem de dividir para conquistar, o problema é dividido em vários pequenos subproblemas. Em seguida, os subproblemas são resolvidos recursivamente e combinados para obter a solução do problema original.
A abordagem de dividir para conquistar envolve as seguintes etapas em cada nível -
Divide - O problema original está dividido em subproblemas.
Conquer - Os subproblemas são resolvidos recursivamente.
Combine - As soluções dos subproblemas são combinadas para obter a solução do problema original.
A abordagem de dividir para conquistar é aplicada nos seguintes algoritmos -
- Busca binária
- Ordenação rápida
- Mesclar classificação
- Multiplicação inteira
- Inversão de matriz
- Multiplicação da matriz
Método ganancioso
No algoritmo guloso de otimização da solução, a melhor solução é escolhida a qualquer momento. Um algoritmo ganancioso é muito fácil de aplicar a problemas complexos. Ele decide qual etapa fornecerá a solução mais precisa na próxima etapa.
Este algoritmo é chamado greedyporque quando a solução ótima para a instância menor é fornecida, o algoritmo não considera o programa total como um todo. Uma vez que uma solução é considerada, o algoritmo guloso nunca considera a mesma solução novamente.
Um algoritmo guloso funciona recursivamente criando um grupo de objetos a partir das menores partes componentes possíveis. Recursão é um procedimento para resolver um problema em que a solução de um problema específico depende da solução da instância menor desse problema.
Programaçao dinamica
A programação dinâmica é uma técnica de otimização, que divide o problema em subproblemas menores e depois de resolver cada subproblema, a programação dinâmica combina todas as soluções para obter a solução final. Ao contrário do método de dividir e conquistar, a programação dinâmica reutiliza a solução para os subproblemas muitas vezes.
O algoritmo recursivo para a série Fibonacci é um exemplo de programação dinâmica.
Algoritmo de Backtracking
Backtracking é uma técnica de otimização para resolver problemas combinacionais. É aplicado a problemas programáticos e da vida real. O problema das oito rainhas, o quebra-cabeça de Sudoku e a passagem por um labirinto são exemplos populares de algoritmos de retrocesso.
No retrocesso, partimos de uma solução possível, que satisfaça todas as condições exigidas. Em seguida, passamos para o próximo nível e se esse nível não produzir uma solução satisfatória, retornamos um nível para trás e começamos com uma nova opção.
Branch and Bound
Um algoritmo branch and bound é uma técnica de otimização para obter uma solução ótima para o problema. Busca a melhor solução para um determinado problema em todo o espaço da solução. Os limites na função a ser otimizada são mesclados com o valor da melhor solução mais recente. Ele permite que o algoritmo encontre partes do espaço de solução completamente.
O objetivo de uma pesquisa de ramificação e limite é manter o caminho de custo mais baixo para um destino. Assim que uma solução for encontrada, ele pode continuar melhorando a solução. A pesquisa de ramificação e limite é implementada na pesquisa limitada em profundidade e na pesquisa em profundidade.
Programação linear
A programação linear descreve uma ampla classe de trabalho de otimização em que tanto o critério de otimização quanto as restrições são funções lineares. É uma técnica para obter o melhor resultado, como lucro máximo, caminho mais curto ou custo mais baixo.
Nesta programação, temos um conjunto de variáveis e devemos atribuir-lhes valores absolutos para satisfazer um conjunto de equações lineares e maximizar ou minimizar uma determinada função objetivo linear.