Dividir para conquista

Dividir para Conquistar

Cristina da Silva Matos¹, Tiago de Alcântara Esmeraldino¹.

¹Acadêmico do curso de Ciência da Computação – Unidade Acadêmica de Ciências, Engenharias e Tecnologias - Universidade do Extremo Sul Catarinense (UNESC) – Criciúma, SC - Brasil

{tiago.dragonheart,cristinamatos.pk}@gmail.com

Resumo. Este artigo apresenta o Paradigma de Projeto de Algoritmos Divisão e Conquista, uma técnica usada para resolução de algoritmos de tendência recursiva. Essa técnica consiste em dividir o problema, grande e complexo, em subproblemas pequenos e de solução simples. Os pequenos problemas são resolvidos e combinados de forma que resolva o problema original.

Palavras-chave: Divisão e conquista; Análise de Algoritmo.

1. Introdução

Cada padrão de estratégia de algoritmo se relaciona com uma dada categoria de problemas. Dado um problema a ser resolvido, podemos achar que existem diversas estratégias de solução possíveis para ele. Podemos também achar que apenas uma estratégia ou mesmo que nem uma delas se aplica. Aqui será estudada a estratégia de solução de algoritmo Divisão e Conquista. Que consiste em transformar um grande problema em vários pequenos problemas, que combinado resolvem o problema global.

2. Conceito de Divisão e conquista

Divisão e conquista é uma estratégia de solução de algoritmos que consiste em dividir o problema a ser resolvido em partes menores e mais simples, cada um dos subproblemas é resolvido separadamente, e ao final as soluções dos subproblemas são combinadas fim de se obter a solução do problema original [Preiss, 2000].

Os algoritmos de divisão e conquista são frequentemente utilizados com recursividade, Entretanto, nem todos os métodos recursivos são algoritmos de divisão e conquista. Geralmente os subproblemas resolvidos por um algoritmo de divisão e conquista não se sobrepõem[Ziviani, 2007]..A técnica soluciona o problema em três fases: -