Divisão e Conquista

Projeto e Análise de Algoritmos

Aula 03 – Técnicas de Projeto de Algoritmos

(Divisão e Conquista)

Edirlei Soares de Lima

<edirlei@iprj.uerj.br>

Estratégias de Projeto de Algoritmos

•

Força Bruta (Brute Force)

Dividir e Conquistar (Divide and Conquer)

Diminuir e Conquistar (Decrease and Conquer)

Transformar e Conquistar (Transform and Conquer)

Compromisso Tempo–Espaço (Space and Time Tradeoffs)

Estratégia Gulosa (Greedy)

Programação Dinâmica (Dynamic Programming)

Voltando Atrás (Backtracking)

Ramificar e Limitar (Branch and Bound)

Algoritmos Aproximados

Divisão e Conquista

•

Ideia geral:

1

2

3

. Dividir a instância do problema em duas ou mais

instâncias menores;

. Resolver as instâncias menores (geralmente

recursivamente);

. Obter a solução para as instâncias originais (maiores)

através da combinação destas soluções.

Divisão e Conquista

•

O paradigma de dividir e conquistar envolve 3 passos:

Dividir

Conquistar

Combinar

Divisão e Conquista

•

Exemplo: calcular a soma de n números ꢀ₀ + … + ꢀ_ꢁ₋₁

Se n > 1, podemos dividir o problema em duas

instâncias do mesmo problema:

–

Soma dos primeiros ꢂ/2 números;

–

Soma dos ꢂ/2 números restantes;

•

Uma vez estas duas somas computadas, adicionamos

seus valores para obter o resultado final:

ꢀ₀

+ … + ꢀ_ꢁ₋₁ = (ꢀ₀ + … + ꢀ _ꢁ_/_ꢃ₋₁) + (ꢀ₀ + … + ꢀ _ꢁ_/_ꢃ₋₁)

Divisão e Conquista

•

Esta é uma maneira eficiente de calcular a soma de n

números?

•

É mais eficiente do que uma adição força bruta?

Nem todos os algoritmos baseados na técnica de

dividir e conquistar são mais eficientes do que uma

solução força bruta.

Divisão e Conquista

•

Em geral, o tempo gasto na execução das três etapas

do algoritmo dividir e conquistar, é menor do que a

resolução por outros métodos.

A estratégia dividir e conquistar produz alguns dos

algoritmos mais importantes e eficientes da área da

computação.

Importante: a estratégia dividir e conquistar pode ser

facilmente adaptada a computação paralela.

Exemplo 1: Multiplicação de Inteiros Grandes

•

Problema: realizar a multiplicação de inteiros

grandes (da ordem de 100 digitos decimais).

–

Ex: 358712253797428009 × 153461234908764388 = ?

Multiplicação Tradicional:

Algoritmo de Força Bruta:

-

multiplicação dígito a dígito;

soma dígito a dígito;

u

9

999

___⁷__⁷_⁷__⁷_ ^v

9993

_

6

Complexidade: O(n² + n) = O(n²)

6

_

_____________

7

7762223 u ×v

Exemplo 1: Multiplicação de Inteiros Grandes

•

Problema: realizar a multiplicação de inteiros

grandes (da ordem de 100 digitos decimais).

–

Outra forma de multiplicar números grandes?

Passo 1 - Multiplicação dos Grandes

A = x₁× y₁ A = 12 × 56 = 672

Passo 2 - Multiplicação dos Pequenos

B = x₂× y₂ B = 34 × 78 = 2652

Passo 3 - Soma os dois grupos de x

C = x₁+ x₂ C = 12 + 34 = 46

Passo 4 - Soma os dois grupos de y

D = y₁+ y₂ D = 56 + 78 = 134

Passo 5 - Multiplique as somas dos grupos

E = C × D E = 46 × 134 = 6164

x₁x₂

x 12 34

y

5

6 78

^y¹^y2

Exemplo 1: Multiplicação de Inteiros Grandes

•

Problema: realizar a multiplicação de inteiros

grandes (da ordem de 100 digitos decimais).

–

Outra forma de multiplicar números grandes?

Passo 6 - Subtraia o produto da soma dos dois grupos (E),

o produto dos grandes (A) e o produto dos pequenos (B)

^x¹^x2

F = E - A - B

F = 6164 - 672 - 2652 = 2840

Passo 7 - Shift do produto dos grandes

x 12 34

G = A × ꢄꢅ ²

m

2x2

G = 672 × 10 = 6720000

y

5

6 78

Passo 8 - Shift do resultado das subtrações

y₁y₂

H = F × ꢄꢅ ^m

H = 2840 × 10 = 284000

2

Passo 9 - Soma Final

I = G + B + H I = 6720000 + 2652 + 284000

Exemplo 1: Multiplicação de Inteiros Grandes

•

Algoritmo de Karatsuba

1

2

3

4

5

6

7

8

9

1

. KARATSUBA(u, v, n)

. se n < 3 então

. retorne u × v

. senão

O(ꢉ^ꢊ^ꢋ^ꢌ^ꢍ^ꢎ) = O(n¹^.⁵⁸⁵)

. m ← ꢂ/2

. a ← ꢆ/ꢄꢅ^ꢇ

. b ← u mod 10^m

. c ← ꢈ/ꢄꢅ^ꢇ

. d ← v mod 10^m

0. ac ← KARATSUBA(a, c, m)

1. bd ← KARATSUBA(b, d, m)

2. y ← KARATSUBA(a + b, c + d, m + 1)

3. x ← ac × 10²^m + (y - ac - bd)× 10^m + bd

4. retorne x

Exemplo 1: Multiplicação de Inteiros Grandes

•

Multiplicação Tradicional: O(ꢂ^ꢃ)

Algoritmo de Karatsuba: O(ꢂ^ꢏ^ꢐ^ꢑ^ꢒ³

)

Wolfram Alpha:

plot n^2 from n=0 to 15, n ^ log base 2 of 3 from n=0 to 15

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois

deles que estão à distância mínima.

ꢓꢔꢕꢖꢀꢂꢗꢔꢀ(ꢘ₁, ꢙ₁, ꢘ_ꢃ, ꢙ_ꢃ) = (ꢘ₁ꢚꢘ_ꢃ)^ꢃ + (ꢙ₁ꢚꢙ_ꢃ)

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois

deles que estão à distância mínima.

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois

deles que estão à distância mínima.

Divide…

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois

deles que estão à distância mínima.

Divide… Conquista...

d_E

d_D

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois

deles que estão à distância mínima.

Divide… Conquista... Combina!

d_E

^dED

d_D

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois deles

que estão à distância mínima.

–

Dividir: X[1 .. q], Y[1 .. q] (esquerda)

X[q+1 .. n], Y [q+1 .. n] (direita)

onde q := ꢂ/2

–

Conquistar: Determine, recursivamente, a menor distância d_E entre

dois pontos da esquerda e a menor distância d_D entre dois pontos da

direita.

Combinar: Devolva o mínimo entre d_E, d_D e a menor distância d_E_D

entre um ponto da esquerda e um ponto da direita.

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois deles

que estão à distância mínima.

Como realizar a função COMBINE de forma eficiente?

–

COMBINE precisa considerar apenas pontos que estão a uma distância menor

que d = min{d_E, d_D} da reta vertical.

Problema: todos os pontos podem estar nessa faixa.

Exemplo 2: Par de Pontos mais Próximos

•

Problema: Dados n pontos no plano, determinar dois deles

que estão à distância mínima.

Como realizar a função COMBINE de forma eficiente?

–

Para cada ponto na faixa, olhamos apenas para pontos da faixa que tenham a

coordenada Y no máximo d mais que este ponto.

Em cada um dos dois quadrados de lado d, há no máximo 4 pontos porque

d ≤ d_E e d ≤ d_D. Logo há não mais que 7 pontos assim (excluindo o ponto).

Exemplo 2: Par de Pontos mais Próximos

1

2

3

4

5

6

7

. PAR_MAIS_PROX(x, y, n)

. para i ← 1 até n faça

. p_x[i] ← i

. p_y[i] ← i

. MERGE-SORT(p_x, n, x)

. MERGE-SORT(p_y, n, y)

. retorne PAR_MAIS_PROX_REC(x, y, p_x, p_y, n)

1

2

3

4

. PAR_MAIS_PROX_REC(x, y, p_x, p_y, n)

. se n <= 3 então

. retorna PAR_MAIS_PROX_FORCA_BRUTA(x, y, n)

. senão

ꢛ_ꢜ^ꢝ, ꢛ_ꢞ^ꢝ , ꢂ , ꢛ_ꢜ^ꢟ , ꢛ_ꢞ^ꢟ , ꢂ ← DIVIDE(x, y, p_x, p_y, n)

ꢝ

ꢟ

5.

ꢝ

6

. i^e, j^e ← PAR_MAIS_PROX_REC(x, y, ꢛ_ꢜ^ꢝ , ꢛ_ꢞ^ꢝ , ꢂ )

ꢟ

7

. i^d, j^d ← PAR_MAIS_PROX_REC(x, y, ꢛ_ꢜ^ꢟ , ꢛ_ꢞ^ꢟ , ꢂ )

8

. retorna COMBINA(x, y, i^e, j^e, i^d, j^d, p^x, p^y, n)

Exemplo 2: Par de Pontos mais Próximos

1

2

3

4

. DIVIDE(x, y, p_x, p_y, n)

. n^e ← ⌊n/2⌋

. n^d ← n − n^e

.

ꢛ_ꢜ^ꢝ[1..n^e] ← p_x[1..n^e]

5

6

7

8

9

1

.

ꢛ_ꢜ^ꢟ[1..n^d] ← p_x[n_e+1..n]

. x_c ← x[p_x[n^e]]

. i ← 0

. j ← 0

. para k ← 1 até n faça

0. se x[p_y[k]] <= x_c então

1.

i ← i + 1

ꢛ_ꢞ^ꢝ[i] ← p_y[k]

2.

13. senão

1

4.

5.

j ← j + 1

ꢛ_ꢞ^ꢟ[j] ← p_y[k]

1

6. devolva ꢛ_ꢜ^ꢝ , ꢠ , n^e, ꢛ_ꢜ^ꢟ , ꢛ_ꢞ^ꢟ , n^d

ꢝ

1

2

3

4

5

6

7

8

9

1

2

. COMBINA(x, y, i^e, j^e, i^d, j^d, p_x, p_y, n)

ꢡ ← min{DIST(x, y, i^e, j^e),DIST(x, y, i^d, j^d)}

.

. x_c ← x[p_x[⌊n/2⌋]]

. m ← ꢡ

.

t ← 0

. para k ← 1 até n faça

. se |x[p_y[k]] − x_c| <= ꢡ então

.

t ← t + 1

f_y[t] ← p_y[k]

0. para i ← 1 até t − 1 faça

1. para j ← i + 1 até min{i + 7, t} faça

2.

3.

4.

5.

6.

d ← DIST(x, y, f_y[i], f_y[j])

se d < m então

m ← d

p₁← f_y[i]

p₂← f_y[j]

7. se m = ꢡ então

8. retorne argmin{DIST(x,y,i^e,j^e),DIST(x,y,i^d,j^d)}

9. senão

0. retorne p₁, p₂

Exemplo 2: Par de Pontos mais Próximos

•

Análise da função DIVIDE:

–

Linha 2-3

Linha 4-5

Linha 6-8

Linha 9-15

Linha 16

→ O(1)

→ O(n)

→ O(1)

→ O(n)

→ O(1)

–

Total → O(2n + 3) = O(n)

Exemplo 2: Par de Pontos mais Próximos

•

Análise da função COMBINA:

–

Linha 2-5

Linha 6-9

Linha 10

Linha 11-16 → O(1)

Linha 17-20 → O(1)

→ O(1)

→ O(n)

–

Total → O(2n + 3) = O(n)

Exemplo 2: Par de Pontos mais Próximos

1

2

3

4

5

6

7

. PAR_MAIS_PROX(x, y, n)

. para i ← 1 até n faça

. p_x[i] ← i

O(n log n)

. p_y[i] ← i

. MERGE-SORT(p_x, n, x)

. MERGE-SORT(p_y, n, y)

. retorne PAR_MAIS_PROX_REC(x, y, p_x, p_y, n)

. PAR_MAIS_PROX_REC(x, y, p_x, p_y, n)

1

2

3

4

O(n log n)

. se n <= 3 então

. retorna PAR_MAIS_PROX_FORCA_BRUTA(x, y, n)

. senão

ꢛ_ꢜ^ꢝ, ꢛ_ꢞ^ꢝ , ꢂ , ꢛ_ꢜ^ꢟ , ꢛ_ꢞ^ꢟ , ꢂ ← DIVIDE(x, y, p_x, p_y, n)

ꢝ

ꢟ

5.

ꢝ

6

. i^e, j^e ← PAR_MAIS_PROX_REC(x, y, ꢛ_ꢜ^ꢝ , ꢛ_ꢞ^ꢝ , ꢂ )

ꢟ

7

. i^d, j^d ← PAR_MAIS_PROX_REC(x, y, ꢛ_ꢜ^ꢟ , ꢛ_ꢞ^ꢟ , ꢂ )

8

. retorna COMBINA(x, y, i^e, j^e, i^d, j^d, p^x, p^y, n)

Divisão e Conquista

•

Outros algoritmos importantes baseados em divisão

e conquista que veremos ao longo do curso:

–

Merge Sort

Quick Sort

Quando Utilizar Divisão e Conquista?

•

Existem três condições que indicam que a estratégia

de divisão e conquista pode ser utilizada com

sucesso:

–

Deve ser possível decompor uma instância em sub-

instâncias.

A combinação dos resultados dever ser eficiente (trivial se

possível).

As sub-instâncias devem ser mais ou menos do mesmo

tamanho.

Comentários sobre a Divisão e Conquista

•

Muitos algoritmos eficientes são baseados nesta

técnica.

–

Contudo, ela pode ser inaplicável e inferior a soluções

algorítmicas mais simples.

Outras estratégias semelhantes:

–

Diminuir e Conquistar (Decrease and Conquer)

–

Transformar e Conquistar (Transform and Conquer)

Comentários sobre a Divisão e Conquista

•

Vantagens:

–

Pode gerar algoritmos eficientes com forte tendência a complexidade

logarítmica;

–

Facilmente paralelizável;

•

Desvantagens:

–

Geralmente são algoritmos recursivos (problema de estouro de pilha);

–

Repetição de sub-problemas;

Exercícios

Lista de Exercícios 03 – Divisão e Conquista

http://www.inf.puc-rio.br/~elima/paa/

Leitura Complementar

•

Levitin. Introduction to the Design and

Analysis of Algorithms, 3rd Edition, 2011.

Capítulo 5: Divide-and-Conquer