Algoritmo de divisão e conquista - Divide-and-conquer algorithm

Na ciência da computação , dividir para conquistar é um paradigma de projeto de algoritmo . Um algoritmo de divisão e conquista divide recursivamente um problema em dois ou mais subproblemas do mesmo tipo ou de tipo relacionado, até que se tornem simples o suficiente para serem resolvidos diretamente. As soluções para os subproblemas são então combinadas para fornecer uma solução para o problema original.

A técnica de dividir e conquistar é a base de algoritmos eficientes para muitos problemas, como classificação (por exemplo, classificação rápida , classificação por mesclagem ), multiplicação de grandes números (por exemplo, o algoritmo de Karatsuba ), localização do par de pontos mais próximo , análise sintática ( por exemplo, analisadores de cima para baixo ) e computando a transformada discreta de Fourier ( FFT ).

Projetar algoritmos de divisão e conquista eficientes pode ser difícil. Como na indução matemática , muitas vezes é necessário generalizar o problema para torná-lo passível de uma solução recursiva. A exatidão de um algoritmo de divisão e conquista é geralmente provada por indução matemática, e seu custo computacional é freqüentemente determinado resolvendo relações de recorrência .

Dividir e conquistar

Abordagem de divisão e conquista para classificar a lista (38, 27, 43, 3, 9, 82, 10) em ordem crescente. Metade superior: divisão em sublistas; mid: uma lista de um elemento é classificada trivialmente; metade inferior: compondo sublistas ordenadas.

O paradigma dividir para conquistar é frequentemente usado para encontrar uma solução ótima para um problema. Sua ideia básica é decompor um determinado problema em dois ou mais subproblemas semelhantes, mas mais simples, para resolvê-los por sua vez e compor suas soluções para resolver o problema em questão. Problemas de simplicidade suficiente são resolvidos diretamente. Por exemplo, para classificar uma determinada lista de n números naturais, divida-a em duas listas de cerca de n / 2 números cada, classifique cada um deles e intercale ambos os resultados apropriadamente para obter a versão classificada da lista fornecida (consulte o foto). Essa abordagem é conhecida como algoritmo de classificação por mesclagem .

O nome "dividir para conquistar" às vezes é aplicado a algoritmos que reduzem cada problema a apenas um subproblema, como o algoritmo de busca binária para encontrar um registro em uma lista ordenada (ou seu análogo na computação numérica , o algoritmo de bissecção para raiz encontrar ). Esses algoritmos podem ser implementados com mais eficiência do que algoritmos gerais de divisão e conquista; em particular, se eles usam recursão de cauda , eles podem ser convertidos em loops simples . De acordo com essa definição ampla, entretanto, todo algoritmo que usa recursão ou loops pode ser considerado um "algoritmo de divisão e conquista". Portanto, alguns autores consideram que o nome "dividir para conquistar" deve ser usado apenas quando cada problema pode gerar dois ou mais subproblemas. O nome diminuir e conquistar foi proposto em vez da classe de subproblema único.

Uma aplicação importante de dividir e conquistar é na otimização, onde se o espaço de busca é reduzido ("podado") por um fator constante em cada etapa, o algoritmo geral tem a mesma complexidade assintótica da etapa de poda, com a constante dependendo do fator de poda (somando as séries geométricas ); isso é conhecido como podar e pesquisar .

Exemplos históricos primitivos

Os primeiros exemplos desses algoritmos são basicamente diminuídos e conquistados - o problema original é sucessivamente dividido em subproblemas únicos e, de fato, pode ser resolvido iterativamente.

A pesquisa binária, um algoritmo de diminuição e conquista em que os subproblemas têm aproximadamente metade do tamanho original, tem uma longa história. Embora uma descrição clara do algoritmo em computadores tenha aparecido em 1946 em um artigo de John Mauchly , a ideia de usar uma lista ordenada de itens para facilitar a pesquisa remonta pelo menos à Babilônia em 200 aC. Outro antigo algoritmo de diminuição e conquista é o algoritmo euclidiano para calcular o maior divisor comum de dois números, reduzindo os números a subproblemas cada vez menores equivalentes, que datam de vários séculos aC.

Um exemplo inicial de um algoritmo de divisão e conquista com vários subproblemas é a descrição de 1805 de Gauss do que agora é chamado de algoritmo de transformação rápida de Fourier (FFT) de Cooley-Tukey , embora ele não tenha analisado sua contagem de operação quantitativamente, e FFTs o fez não se espalharam até serem redescobertos um século depois.

Um dos primeiros algoritmos D&C de dois subproblemas que foi desenvolvido especificamente para computadores e devidamente analisado é o algoritmo de classificação por mesclagem , inventado por John von Neumann em 1945.

Outro exemplo notável é o algoritmo inventado por Anatolii A. Karatsuba em 1960 que poderia multiplicar dois números de n dígitos em operações (em notação Big O ). Este algoritmo refutou a conjectura de Andrey Kolmogorov de 1956 de que as operações seriam necessárias para essa tarefa. ${\ displaystyle O (n ^ {\ log _ {2} 3})}$ ${\ displaystyle \ Omega (n ^ {2})}$

Como outro exemplo de um algoritmo de dividir e conquistar que originalmente não envolvia computadores, Donald Knuth fornece o método que uma agência dos correios normalmente usa para encaminhar correspondências: as cartas são classificadas em bolsas separadas para diferentes áreas geográficas, cada uma dessas bolsas é separada em lotes para sub-regiões menores e assim por diante até que sejam entregues. Isso está relacionado a uma classificação radix , descrita para máquinas de classificação de cartões perfurados já em 1929.

Vantagens

Resolvendo problemas difíceis

Dividir para conquistar é uma ferramenta poderosa para resolver problemas conceitualmente difíceis: tudo o que requer é uma maneira de dividir o problema em subproblemas, de resolver os casos triviais e de combinar subproblemas ao problema original. Da mesma forma, diminuir e conquistar requer apenas a redução do problema a um único problema menor, como o quebra-cabeça clássico da Torre de Hanói , que reduz o movimento de uma torre de altura para mover uma torre de altura . ${\ displaystyle n}$ ${\ displaystyle n-1}$

Eficiência do algoritmo

O paradigma dividir para conquistar muitas vezes ajuda na descoberta de algoritmos eficientes. Era a chave, por exemplo, para o método de multiplicação rápida de Karatsuba, os algoritmos quicksort e mergesort, o algoritmo Strassen para multiplicação de matrizes e as transformadas rápidas de Fourier.

Em todos esses exemplos, a abordagem D&C levou a uma melhoria no custo assintótico da solução. Por exemplo, se (a) os casos base têm tamanho limitado constante, o trabalho de dividir o problema e combinar as soluções parciais é proporcional ao tamanho do problema , e (b) há um número limitado de subproblemas de tamanho ~ em cada estágio, o custo do algoritmo de divisão e conquista será . ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle n / p}$ ${\ displaystyle O (n \ log _ {p} n)}$

Paralelismo

Os algoritmos de divisão e conquista são naturalmente adaptados para execução em máquinas com vários processadores, especialmente sistemas de memória compartilhada , onde a comunicação de dados entre os processadores não precisa ser planejada com antecedência porque subproblemas distintos podem ser executados em processadores diferentes.

Acesso à memória

Os algoritmos de divisão e conquista tendem naturalmente a fazer uso eficiente dos caches de memória . A razão é que uma vez que um subproblema é pequeno o suficiente, ele e todos os seus subproblemas podem, em princípio, ser resolvidos dentro do cache, sem acessar a memória principal mais lenta. Um algoritmo projetado para explorar o cache dessa maneira é chamado de cache-oblivious , porque não contém o tamanho do cache como um parâmetro explícito. Além disso, os algoritmos D&C podem ser projetados para algoritmos importantes (por exemplo, classificação, FFTs e multiplicação de matrizes) para serem algoritmos esquecidos do cache ideais - eles usam o cache de uma maneira provavelmente ótima, em um sentido assintótico, independentemente do tamanho do cache. Em contraste, a abordagem tradicional para explorar o cache é o bloqueio , como na otimização de ninho de loop , onde o problema é explicitamente dividido em pedaços do tamanho apropriado - isso também pode usar o cache de forma otimizada, mas apenas quando o algoritmo é ajustado para o específico tamanhos de cache de uma máquina específica.

A mesma vantagem existe em relação a outros sistemas de armazenamento hierárquico, como NUMA ou memória virtual , bem como para vários níveis de cache: uma vez que um subproblema é pequeno o suficiente, pode ser resolvido dentro de um determinado nível da hierarquia, sem acessando os níveis mais altos (mais lentos).

Controle de arredondamento

Em cálculos com aritmética arredondada, por exemplo, com números de ponto flutuante , um algoritmo de divisão e conquista pode produzir resultados mais precisos do que um método iterativo superficialmente equivalente. Por exemplo, pode-se adicionar N números por um loop simples que adiciona cada dado a uma única variável ou por um algoritmo D&C chamado soma de pares que divide o conjunto de dados em duas metades, calcula recursivamente a soma de cada metade e, em seguida, adiciona as duas somas. Embora o segundo método execute o mesmo número de adições que o primeiro e pague a sobrecarga das chamadas recursivas, geralmente é mais preciso.

Problemas de implementação

Recursão

Os algoritmos de divisão e conquista são naturalmente implementados como procedimentos recursivos . Nesse caso, os subproblemas parciais que levam ao que está sendo resolvido no momento são armazenados automaticamente na pilha de chamadas de procedimento . Uma função recursiva é uma função que chama a si mesma dentro de sua definição.

Pilha explícita

Os algoritmos de divisão e conquista também podem ser implementados por um programa não recursivo que armazena os subproblemas parciais em alguma estrutura de dados explícita, como uma pilha , fila ou fila de prioridade . Esta abordagem permite mais liberdade na escolha do subproblema a ser resolvido a seguir, um recurso que é importante em algumas aplicações - por exemplo, na recursão em amplitude e no método branch-and-bound para otimização de função. Essa abordagem também é a solução padrão em linguagens de programação que não fornecem suporte para procedimentos recursivos.

Tamanho da pilha

Em implementações recursivas de algoritmos D&C, deve-se ter certeza de que há memória suficiente alocada para a pilha de recursão, caso contrário, a execução pode falhar devido ao estouro da pilha . Os algoritmos de D&C que são eficientes em termos de tempo geralmente têm uma profundidade de recursão relativamente pequena. Por exemplo, o algoritmo de classificação rápida pode ser implementado de forma que nunca exija mais do que chamadas recursivas aninhadas para classificar itens. ${\ displaystyle \ log _ {2} n}$ ${\ displaystyle n}$

O estouro de pilha pode ser difícil de evitar ao usar procedimentos recursivos, pois muitos compiladores assumem que a pilha de recursão é uma área contígua da memória e alguns alocam uma quantidade fixa de espaço para ela. Os compiladores também podem salvar mais informações na pilha de recursão do que o estritamente necessário, como endereço de retorno, parâmetros inalteráveis e as variáveis internas do procedimento. Assim, o risco de estouro de pilha pode ser reduzido minimizando os parâmetros e variáveis internas do procedimento recursivo ou usando uma estrutura de pilha explícita.

Escolhendo os casos básicos

Em qualquer algoritmo recursivo, existe uma liberdade considerável na escolha dos casos base , os pequenos subproblemas que são resolvidos diretamente para encerrar a recursão.

Escolher o menor ou o mais simples caso base possível é mais elegante e geralmente leva a programas mais simples, porque há menos casos a serem considerados e são mais fáceis de resolver. Por exemplo, um algoritmo FFT pode parar a recursão quando a entrada é uma única amostra, e o algoritmo de classificação de lista de classificação rápida pode parar quando a entrada é uma lista vazia; em ambos os exemplos, há apenas um caso base a ser considerado e não requer processamento.

Por outro lado, a eficiência geralmente melhora se a recursão for interrompida em casos de base relativamente grandes, e estes são resolvidos de forma não recursiva, resultando em um algoritmo híbrido . Essa estratégia evita a sobrecarga de chamadas recursivas que fazem pouco ou nenhum trabalho e também pode permitir o uso de algoritmos não recursivos especializados que, para aqueles casos base, são mais eficientes do que a recursão explícita. Um procedimento geral para um algoritmo recursivo híbrido simples é curto-circuitar o caso base , também conhecido como recursão arm's-length . Neste caso, se a próxima etapa resultará no caso base é verificado antes da chamada da função, evitando uma chamada de função desnecessária. Por exemplo, em uma árvore, em vez de recorrer a um nó filho e depois verificar se ele é nulo, verifique se ele é nulo antes de recorrer; evita metade das chamadas de função em alguns algoritmos em árvores binárias. Uma vez que um algoritmo de D&C eventualmente reduz cada problema ou instância de subproblema a um grande número de instâncias de base, eles geralmente dominam o custo geral do algoritmo, especialmente quando a sobrecarga de divisão / junção é baixa. Observe que essas considerações não dependem se a recursão é implementada pelo compilador ou por uma pilha explícita.

Assim, por exemplo, muitas implementações de biblioteca de quicksort mudarão para um algoritmo de classificação por inserção baseado em loop simples (ou similar) assim que o número de itens a serem classificados for suficientemente pequeno. Observe que, se a lista vazia fosse o único caso base, classificar uma lista com entradas implicaria em chamadas de classificação rápida ao máximo que não fariam nada além de retornar imediatamente. Aumentar os casos base para listas de tamanho 2 ou menos eliminará a maioria dessas chamadas de não fazer nada e, mais geralmente, um caso base maior que 2 é normalmente usado para reduzir a fração de tempo gasto em sobrecarga de chamada de função ou manipulação de pilha. ${\ displaystyle n}$ ${\ displaystyle n}$

Alternativamente, pode-se empregar grandes casos de base que ainda usam um algoritmo de divisão e conquista, mas implementar o algoritmo para um conjunto predeterminado de tamanhos fixos onde o algoritmo pode ser completamente desenrolado em código que não tem recursão, loops ou condicionais (relacionados a técnica de avaliação parcial ). Por exemplo, esta abordagem é usada em algumas implementações FFT eficientes, onde os casos base são implementações desenroladas de algoritmos FFT de divisão e conquista para um conjunto de tamanhos fixos. Métodos de geração de código-fonte podem ser usados para produzir o grande número de casos base separados desejáveis para implementar esta estratégia de forma eficiente.

A versão generalizada dessa ideia é conhecida como recursão "desenrolamento" ou "engrossamento", e várias técnicas foram propostas para automatizar o procedimento de ampliação do caso base.

Compartilhando subproblemas repetidos

Para alguns problemas, a recursão ramificada pode acabar avaliando o mesmo subproblema várias vezes. Em tais casos, pode valer a pena identificar e salvar as soluções para esses subproblemas sobrepostos, uma técnica comumente conhecida como memoização . Seguido até o limite, leva a algoritmos de divisão e conquista de baixo para cima , como programação dinâmica e análise de gráficos .

Languages

In other projects