Técnicas de Divisão e Conquista e de Programação Dinâmica
para a resolução de Problemas de Otimização
Francisco Vando Carneiro Moreira
Gerardo Valdisio Rodrigues Viana
Faculdade Lourenço Filho
Universidade Estadual do Ceará
Resumo
Encontrar o valor máximo ou mínimo de uma função é um problema bastante utilizado em diversas áreas.
Em geral, este valor é chamado de "ótimo" pois corresponde ao melhor dentre todos os possíveis num
espaço de soluções viáveis. Neste contexto define-se a otimização, que pode ser restrita, quando a
solução atender determinadas condições impostas pelo problema, ou irrestrita, quando qualquer solução
dentro do domínio da função é investigada. Classificam-se como problemas mais difíceis aqueles em que
o espaço de soluções não é contínuo, caracterizando a chamada Otimização Discreta, ou Combinatória,
definida assim: “dado um conjunto A de elementos, deseja-se encontrar um subconjunto S ⊆ A tal que a
função objetivo, aplicada aos elementos de S, possui o valor "ótimo" que pode ser de máximo (maior de
todos) ou de mínimo (menor de todos)”. Como o número de opções para a escolha de S cresce de forma
exponencial com o tamanho do conjunto A, métodos exatos para obter a "solução ótima" precisam
percorrer todo o espaço, o que se torna impraticável. Para isto existem os métodos aproximados que
correspondem às heurísticas, meta-heurísticas e algoritmos aproximativos. Dentre estes, destacam-se as
técnicas de Divisão e Conquista e de Programação Dinâmica. Neste trabalho, mostramos o
funcionamento destes dois algoritmos aplicados a alguns problemas conhecidos de otimização
combinatória.
Palavras-chave: Divisão e Conquista, Programação Dinâmica, Algoritmos, Problema da Mochila.
1. INTRODUÇÃO
Dados, uma “mochila” com capacidade C e um conjunto A com n itens, onde cada item
i ∈ A contém um peso Pi > 0 e uma utilidade, ou valor, Vi > 0, deseja-se determinar um
subconjunto S ⊆ A tal que a soma dos pesos dos elementos de S não ultrapasse a capacidade da
mochila e a soma dos respectivos valores seja a maior possível.
Este artigo apresenta duas soluções com paradigmas distintos para este clássico
problema de otimização combinatória. O primeiro algoritmo utiliza a estratégia de Divisão e
Conquista na ordenação dos custos relativos (Peso/Valor) por intercalação (MergeSort). A
6
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
seguir é utilizada uma heurística gulosa para obter uma solução aproximada. Estando os custos
relativos em ordem não decrescente, o funcionamento do algoritmo guloso consiste em aceitar,
a cada iteração, o primeiro item que aparecer, verificando a cada passo se a capacidade da
mochila é, ou não, ultrapassada. O resultado obtido por esta estratégia é, em geral, próxima da
melhor solução possível, ou seja, da solução ótima.
O segundo algoritmo utiliza o método da programação dinâmica que sempre encontra a
solução ótima, porém, com um tempo proporcional ao “valor” da entrada e não ao seu
“tamanho”, como é comum na análise da função de complexidade de um algoritmo. Veremos
que, para uma entrada de um dado tamanho n (número de itens) com a capacidade da mochila
C, o tempo de execução deste algoritmo poderá ser relativamente grande, portanto, inviável.
Deste modo diz-se que o algoritmo de programação dinâmica possui uma complexidade
pseudo-polinomial.
Nos experimentos computacionais foram consideradas algumas instâncias do problema da
Mochila para cada um dos algoritmos implementados. Com os resultados, dispostos numa
tabela, é possível comparar a aproximação das soluções e seus respectivos tempos de execução.
2. DIVISÃO E CONQUISTA
O paradigma Divisão e Conquista consiste em dividir o problema a ser resolvido em
partes menores, encontrar soluções para as partes, e então combinar as soluções obtidas em uma
solução global. ZIVIANI (2007) cita “o uso do paradigma para resolver problemas nos quais
os subproblemas são versões menores do problema original geralmente leva a soluções
eficientes e elegantes, especialmente quando é utilizado recursivamente”.
A Divisão e Conquista emprega modularização de programas e frequentemente conduz
a um algoritmo simples e eficiente. Esta técnica é bastante utilizada em desenvolvimento de
algoritmos paralelos, onde os subproblemas são tipicamente independentes um dos outros,
podendo assim serem resolvidos separadamente.
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
7
Segundo FIGUEIREDO (2011), a técnica de Divisão e Conquista consistem em 3 passos:
•
Divisão: dividir a instância do problema original em duas ou mais instâncias
menores, considerando-as como subproblemas.
•
Conquista: resolver cada subproblema recursivamente.
•
Combinação: combinar as soluções encontradas em cada subproblema, compondo
uma solução para o problema original.
2.1 Vantagens
•
Indicado para aplicações que tem restrição de tempo.
•
É de fácil implementação.
•
Simplifica problemas complexos.
2.2 Desvantagens
•
Necessidade de memória auxiliar.
•
Repetição de Subproblemas.
•
Tamanho da pilha (número de chamadas recursivas e/ou armazenadas pode causar
estouro de memória).
2.3 Algumas aplicações
•
Multiplicação de inteiros longos.
•
Menor distância entre pontos.
•
Ordenação rápida (quicksort) e por intercalação (mergesort).
•
Pesquisa em árvore binária.
Um exemplo para ilustrar o uso dessa técnica é o algoritmo de ordenação de um vetor por
intercalação (MergeSort). Sua representação pode ser feita através de uma árvore binária,
conforme a indicada na Figura 1.
8
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
Figura 1 – Técnica de Divisão e Conquista
Fonte: MergeSort (FIGUEIREDO, 2011)
A altura (h) da árvore de execução é O (log n) e a quantidade de operações em cada nível
da árvore é assintoticamente igual a O(n), conclui-se então que a complexidade do algoritmo no
pior caso é O(n log n) (VIANA e CINTRA, 2011).
O MergeSort (ordenação por intercalação) divide o vetor de entrada em dois outros
vetores com metade do tamanho do vetor original (em caso de tamanho ímpar, um deles terá um
elemento a mais que o outro). Cada um destes vetores menores é ordenado recursivamente
utilizando o mesmo procedimento.
O MergeSort garante que os dois subproblemas têm tamanho da ordem de n/2, mas requer
alocação de memória para o vetor temporário de tamanho n.
Este algoritmo, apresentado na Figura 2, usa o procedimento de intercalação (Merge) entre
dois conjuntos previamente ordenados.
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
9
Algoritmo MERGESORT (L, ini, fim)
ENTRADA: um vetor L e as posições ini e fim
SAÍDA: o vetor L em ordem crescente da posição ini até a posição fim
inicio
se ini < fim
meio = (ini + fim)/2
// divisão inteira
se ini < meio
MERGESORT(L, ini, meio)
se (meio + 1) < fim
MERGESORT(L, meio + 1, fim)
MERGE(L, ini, meio, fim)
f i m {MERGESORT}
Figura 2 – Algoritmo para o MergeSort
Fonte: Viana e Cintra (2011, p. 30)
A Figura 3 mostra o algoritmo MERGE que faz a intercalação entre as duas partes de L.
PROCEDIMENTO MERGE ( L, ini, meio, fim )
ENTRADA: inteiros: ini, meio, fim; Vetor L[ini..fim]
// L[ini..meio] = primeira série ordenada
// L[meio+1..fim] = segunda série ordenada
SAÍDA: Registro L com uma única série ordenada
// L[ini..fim] = série intercalada /ordenada
inicio
i = ini;
k = 1; j = meio + 1
enquanto ( i ≤ meio e j ≤ fim )
se ( L[i] ≤ L[j])
S[k] = L[i]
i = i + 1
senão
S[k] = L[j]
j = j + 1
k = k + 1
// fim se
// fim enquanto
〈〈〈 continua 〉〉〉
10
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
se ( i > meio )
p = j
q = fim
senão
p = i
q = meio
para i = p até q
S[k] = L[i]
k = k + 1
// fim para
L[ini..fim] = S[1..(fim-ini+1)]
retorna (L)
f i m {MERGE}
Figura 3 – Algoritmo de Intercalação
Fonte: Viana e Cintra (2011)
3. ALGORITMO GULOSO PARA O PROBLEMA DA MOCHILA
Para resolver o problema da Mochila booleana (0/1) de forma aproximada foi utilizada
uma heurística gulosa apresentada na Figura 4. A descrição do algoritmo é feita a seguir.
A ordenação inicial refere-se à ordem não decrescente do chamado custo relativo
(Peso/Valor). A técnica de Divisão e Conquista foi utilizada como um procedimento auxiliar
para esta classificação.
Em cada passo (iteração) do algoritmo é selecionado ou escolhido o primeiro elemento do
conjunto ordenado que “caiba” na mochila. Este objeto escolhido passa a fazer parte da solução
construída até então.
Observa-se, neste contexto, que foram unidas as duas técnicas, resultando em um
algoritmo, onde se tem a estratégia gulosa baseado no custo relativo através da ordenação
MergeSort do paradigma de divisão e conquista, acima abordado.
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
11
Algoritmo MOCHILA_0/1_Guloso
ENTRADA: C= capacidade da Mochila; n = número de itens
V[1..n] vetor com os valores(custos) dos itens e
P[1..n] vetor com os pesos dos itens
SAÍDA: X[1..n] vetor binário que indica se o item i é selecionado(1) ou não (0)
Sol = solução (valor máximo da Função objetivo)
Inicio
Sol = 0
para i = 1 até n
L[i] = V[i] / P[i]
// fim para
MERGESORT ( L, 1, n )
para i = 1 até n e enquanto C ≠ 0
j = C / P[i]
// divisão inteira
X[i] = min { j , 1 }
C = C – X[i]*P[i]
Sol = Sol + X[i]*V[i]
// fim para
escreve ( Sol, X[j], j=1..n )
f i m {MOCHILA_0/1_Guloso}
Figura 4 – Algoritmo para o Problema da Mochila
Fonte: Campello e Maculan (1994)
4. PROGRAMAÇÃO DINÂMICA
A Programação Dinâmica (PD) pode ser caracterizada como um processo sequencial de
tomada de decisões, onde uma decisão ótima global pode ser obtida através da otimização de
subproblemas (ou ótimos locais) individuais, seguindo o “princípio de otimalidade de Bellman”
(DIAS et al, 2010).
Na Programação Dinâmica resolvem-se os problemas de pequena dimensão e guardam-se
as soluções em tabelas dinâmicas, a fim de evitar redundância de cálculo, ou seja, uma solução
parcial obtida somente é calculada uma única vez. Este procedimento é importante porque,
diferentemente da técnica de divisão e conquista, aqui cada subproblema é dependente de pelo
menos um outro. A solução final é obtida combinando as soluções dos problemas menores
12
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
(ROSA, 2011). Pode-se dizer que a Programação Dinâmica é uma maneira esperta de
transformar recursão em iteração, daí ser chamada de Otimização Recursiva.
Aplica-se quando uma estratégia ótima para resolver um problema continua a ser ótima
quando este é subproblema de um problema maior, ou seja, somente soluções ótimas dos
subproblemas podem compor uma solução ótima do problema original (RIBEIRO, 1999).
Muitas vezes quando o algoritmo direto tem complexidade exponencial, os algoritmos
desenvolvidos por programação dinâmica é polinomial, reduzindo drasticamente o tempo de
execução. Outras vezes, como no caso do problema do caixeiro viajante, e da partição, a
complexidade continua exponencial, mas de ordem mais baixa. A idéia básica da programação
dinâmica sugere, então, uma estrutura geral para algoritmos projetados conforme Figura 5.
Figura 5 - Estrutura Geral da Programação Dinâmica
Fonte: Munari e Augusto (2007)
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
13
Na inicialização, a entrada é decomposta em partes mínimas para as quais são obtidas
respostas diretas, a cada iteração vai aumentando tamanho das partes e obtendo respostas
correspondentes a partir das já geradas, até que as partes atingem o tamanho da entrada original.
Quando então sua solução é recuperada e o processo finalizado.
Um exemplo clássico para a aplicação desta técnica é a ordem de produto de matrizes,
citado em (ZIVIANI, 2007), que ilustra bem a técnica de programação dinâmica por meio de
determinar a melhor forma de avaliar o produto de várias matrizes: M = A1 x A2 x... x An,
Onde cada Ai é uma matriz com mi-1 linhas e mi colunas. A ordem na qual as matrizes são
multiplicadas pode ter um efeito enorme no número total de operações de adição e
multiplicação necessárias para obter M.
Por exemplo, se A1=A ( 5 0 x 2 0 ) ; A 2 = B ( 2 0 x 1 ) ; A 3 = C ( 1 x 1 0 ) e A 4 = D ( 1 0 x 1 0 0 ) ,
teríamos as seguintes possibilidades de realizar o produto, conforme colocação de parênteses
que indicam a prioridade indicada em cada uma das árvores da Figura 6. Esta ordem de
execução do produto de duas matrizes acarreta valores distintos do número de multiplicações
total e o que se deseja é minimizar este valor:
a. A x ( ( B x C ) x D )
b. ( ( A x B ) x C ) x D
c. ( A x B ) x ( C x D )
d. A x ( B x ( C x D ) )
e. ( A x ( B x C ) ) x D
Figura 6 – Possibilidades do produto de 4 matrizes. Os nós intermediários contém os
resultados parciais e a raiz, o produto AxBxCxD
Fonte: Dasgupta et al (2008, p. 170)
14
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
Considerando X ( p x q ) uma matriz com p linhas e q colunas, sabemos que o produto das
matrizes X ( p x q ) por Y ( q x r ) existe e requer (p.q.r) multiplicações para obter Z ( p x r ) = X Y .
A instância {m0, m1, . . .,mk, . . .,mn-1, mn) representa a sequência do produto das matrizes
A1, A2, . . .Ak . . . An com respectivas ordens ( m 0 x m 1 ) , ( m 1 x m 2 ) , . . . , ( m n - 1 x m n ) .
Para o exemplo anterior teríamos m0 = 50, m1 = 20, m2 = 1, m3 = 10 e m4 = 100 para
definir as ordens das n=4 matrizes A, B, C e D.
Na Tabela 1 é mostrado o custo total de cada alternativa que corresponde ao total de
multiplicações requeridas em cada caso.
Parentetização
No de multiplicações necessárias para o produto
Custo total
a) A ( ( B C ) D)
20 . 1 . 10 + 20 . 10 . 100 + 50 . 20 . 100
120200
b) ( ( A B ) C ) D
50 . 20 . 1 + 50 . 1 . 10 + 50 . 10 . 100
51050
c) ( A B ) ( C D )
50 . 20 . 1 + 1 . 10 . 100 + 50 . 1 . 100
7000
d) A ( B ( C D ) )
1 . 10 . 100 + 20 . 1 . 100 + 50 . 20 . 100
103000
e) ( A ( B C ) ) D
20 . 1 . 10 + 50 . 20 . 10 + 50 . 10 . 100
60200
Tabela 1 – Escolha do melhor arranjo (c) para o produto de 4 matrizes
Observa-se, neste exemplo, que para o pior arranjo, seriam necessárias 120200
multiplicações, isto equivale a mais de 17 vezes o melhor arranjo (7000 multiplicações). Este
valor é aproximadamente a mesma relação entre os tempos de execução do algoritmo.
O total P(n) de maneiras distintas para colocação de parênteses numa sequência de n
matrizes é dada pela seguinte forma recursiva:
P(n) cresce de forma exponencial em função de n, conforme mostra a Tabela 2.
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
n
P(n)
n
P(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
9694845 ≈ 107
35357670 ≈ 108
129644790 ≈ 109
477638700 ≈ 109
1767263190 ≈ 1010
6564120420 ≈ 1010
24466267020 ≈ 1011
91482563640 ≈ 1011
343059613650 ≈ 1012
1289904147324 ≈ 1013
4861946401452 ≈ 1013
18367353072152 ≈ 1014
69533550916004 ≈ 1014
263747951750360 ≈ 1015
1002242216651368 ≈ 1016
15
Tabela 2 – Número de alternativas para colocação de parênteses entre n matrizes
O uso da Programação Dinâmica para o problema do produto de matrizes tem por objetivo
encontrar uma estrutura de parentetização ótima sem ter que gerar todas estas possibilidades.
Considerando a notação para definir a cadeia Ai..j = Ai Ai+1 . . . Aj indicativa do produto da
sequência de matrizes Ai até Aj, podemos observar que A1..n = (A1..k) x (Ak+1..n).
Pelo princípio da otimalidade da PD, se as subcadeias A1..k e Ak+1..n tem estruturas ótimas
(ou sub-ótimas) podemos afirmar que A1..n terá estrutura ótima.
Usando a tabela dinâmica contendo valores
de multiplicações escalares para calcular a matriz Ai..j então, temos
não há nenhum cálculo e
como mínimos
pois Ai..i = Ai e
representa o menor custo para calcular Ai..k e Ak+1 .. j mais o
custo para multiplicar estas duas matrizes, ou seja:
A definição recursiva para o custo mínimo de colocar parênteses no produto Ai..j é:
16
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
Para armazenarmento da solução ótima, pode-se utilizar uma matriz S, tal que o valor de
S[i,j] contém o valor de k tal que M[i,j] é mínimo. Os algoritmos apresentados nas figuras 7 e 8
resolvem o problema do produto de matrizes.
Algoritmo PD_Produto_Matrizes
ENTRADA: um vetor P contendo as ordens das n matrizes
SAÍDA: matrizes M e S contendo a solução
inicio
para i =1 até n
M[i,i]=0
para L= 2 até n
para i= 1 até n-L+1
j = i + L – 1
M[i,j] = ∞
para k= i até j-1
q = M[i,k] + M[k+1,j] + P[i]*P[k]*P[j]
se q < M[i,j]
M[i,j] = q
S[i,j] = k
return M[1,n] , S
f i m {PD_Produto_Matrizes}
Figura 7 – Algoritmo para resolver o Problema do Produto de várias matrizes por
Programação Dinâmica
Procedimento PRINT_CADEIA ( S, i, j )
inicio
se i = j
print “A”
senão
print “(”
PRINT_CADEIA ( S, i, S[ i , j ] )
PRINT_CADEIA ( S, S[ i , j ] + 1, j )
print “)”
f i m { PRINT_CADEIA }
Figura 8 – Gera a cadeia de caracteres referente à saída do algoritmo da Figura 7
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
17
Os programas implementados em C# correspondentes aos algoritmos das Figuras 7 e 8
estão representados no Anexo A.2.
Como exemplo de seu funcionamento foi executado o programa para uma dada instância,
obtendo os seguintes resultados mostrados a seguir na Figura 9.
Figura 9 – Resultado do Programa do Anexo A.2
4.1 Vantagens da Programação Dinâmica
•
Pode ser utilizada num grande número de problemas de otimização discreta.
•
Não necessita de muita precisão numérica.
•
Útil para aplicar em problemas que exigem teste de todas as possibilidades.
18
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
4.2 Desvantagens
•
Necessita de grande espaço de memória
•
A complexidade espacial pode ser exponencial
4.3 Algumas aplicações
•
Multiplicação de várias matrizes
•
Projeto de sistemas confiáveis
5. PROBLEMA DA MOCHILA POR PROGRAMAÇÃO DINÂMICA
Conforme definido anteriormente, uma instância do Problema da Mochila booleana é
definida por um conjunto com n itens com seus pesos Pi e valores Vi para uma mochila de
capacidade C.
Como o problema é de maximização a definição recursiva para a programação dinâmica é
específica para este problema é dada por:
O algoritmo a seguir resolve o problema:
Algoritmo MOCHILA_0/1_PD
ENTRADA: C= capacidade da Mochila; n = número de itens
V[1..n] vetor com os valores(custos) dos itens e
P[1..n] vetor com os pesos dos itens
SAÍDA: X[1..n] vetor binário que indica se o item i é selecionado(1) ou não (0)
Sol = solução (valor máximo da Função objetivo)
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
inicio
para i = 1 até C
M[i,0] = 0
para j = 1 até n
M[0,j] = 0
X[j] = 0
para i = 1 até C
se P[j] > i
M[i,j] = M[i,j− 1]
senão
M[i,j] = max ( M[i,j− 1] , M[i− P[j] , j− 1] + V[j]
/ / fim para
Sol = M[C,n]
/ / rotina para determinar o vetor X (itens selecionados)
aux = Sol
j = n
enquanto j > 0
se M[C,j] ≠ M[c,j−1]
X[j] = 1
aux = aux − V[j]
k = j− 1
enquanto M[C,k] > aux
M[c,k] = aux
k = k− 1
/ / fim se
j = j− 1
/ / fim enquanto
fim { Mochila_0/1_PD }
Figura 10 – Algoritmo para o Problema da Mochila por Programação Dinâmica
19
20
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
6. EXPERIMENTOS COMPUTACIONAIS
Na abordagem utilizada para avaliar a aplicação de Técnicas de Divisão e Conquista e
Programação Dinâmica para o problema da mochila, foram utilizadas oito instâncias distintas.
Cada instância descrita em um arquivo de texto representa uma mochila com sua capacidade e
seus itens identificados nas primeiras colunas da Tabela 3.
Foi desenvolvida uma ferramenta em C#.NET 4.0 Asp.Net MVC utilizando a IDE Visual
Studio 2010 Ultimate. A avaliação das instâncias foi realizada em uma máquina com 2 GB de
Ram, processador Intel Core 2 Duo e sistema operacional Microsoft Windows XP.
A elaboração deste programa tem como objetivo ser de uso acadêmico. Para efeito de
comparação para o problema da mochila, resolvido tanto pela técnica de Divisão e Conquista
como por Programação Dinâmica, retornamos o tempo gasto por cada técnica, bem como a
solução encontrada. As demais colunas da Tabela 3 apresenta estes resultados.
Nº
Instância
Nº Itens
Capacidade
Sol_1(PD)
Tempo_1
Sol_2(DC)
Tempo_2
Sol.Ótima
Conhecida
1
KP4
4
10
70
0
70
0
70
2
KP100000
4
100000
70
0,046
70
0
70
3
KP1000
1000
500
1280
0,171
1280
0,171
12800
4
KP2500
2500
295
8560
0,125
8560
0,125
8560
5
KP5000
5000
2500
37660
2,718
37859
2,718
37660
6
KP7500
7500
3804
58165
6,250
58164
6,250
58260
7
KP10000
10000
5000
77621
11,484
77621
11,484
77621
8
KP20000
20000
10000
***
-
153576
-
254921
Tabela 3 – Resultados obtidos para algumas instâncias do Problema da Mochila
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
21
Após execução do programa descrito no Anexo A.4 apresentamos os resultados
com os valores de tempo expressos em segundos. Quando informados igual a “0”
representam um tempo menor que 0.001s e se o conteúdo for “***” indica que houve
um estouro da pilha de execução.
7. CONCLUSÃO
Os resultados mostraram que a eficiência das técnicas e o tempo e recursos demandados
estão intrinsecamente relacionados aos parâmetros de configuração de entrada. Comparando as
técnicas de Divisão e Conquista e Programação Dinâmica percebe-se que no caso da instância
com maior número de itens houve o estouro de recursos computacionais, sugerindo que a
técnica deve ser utilizada de forma controlada.
Divide-and-Conquer and Dynamic Programming Technical
for solving Optimization Problems
Abstract
Find the maximum or minimum of a function is a problem widely used in various areas. In general, this is
called "optimal value" because it corresponds to the best of all possible within a feasible solution space.
In this context it’s defined the optimization, which can be restricted when the solution satisfy the
conditions imposed by the problem, or unrestricted when any solution within domain of the function is
investigated. Among these, the most difficult problems are those in which the solution set is not
continuous, characterizing the so-called discrete or combinatorial optimization, defined as follows:
“Given a set A of elements and we want to find a subset S ⊆ A such that the objective function applied to
elements of S has the optimal value that can be maximum (greatest) or minimum (less of all). As the
number of options for selecting S grows exponentially with the size of the set A, exact methods to obtain
the "optimal solution" must search in the all space, which becomes impractical. For this there are
approximate methods that correspond to heuristics, metaheuristics and approximation algorithms. Among
these, there are the techniques of divide and conquer and dynamic programming. In this paper, we show
the performance of these two algorithms applied to some known combinatorial optimization problems.
Keywords: Divide-and-Conquer, Dynamic Programming, Algorithm, Knapsack Problem.
22
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
Referências
CAMPELLO, R.E. e MACULAN, N. (1994). Algoritmos e Heurísticas. Desenvolvimento e
Avaliação de Performance, Editora da Universidade Federal Fluminense, Niterói-RJ.
DASGUPTA, S., PAPADIMITRIOU, C. and VAZIRANI, U. (2008). Algorithms. McGraw-Hill
Higher Education.
DIAS, B.; MARCATO, A.; SOARES, S.; SILVA, I.; OLIVEIRA, E.; BRANDI, R. e RAMOS,
T. (2010). Utilização do Algoritmo de Fechos Convexos na Programação Dinâmica
Estocástica: Simpósio Brasileiro de Sistemas Elétricos.
FIGUEIREDO, J. “Divisão e Conquista. (2011). Notas de Aula da disciplina Analise e Técnicas
de Algoritmo” . Universidade Federal de Campina Grande. Disponível em:
http://www.dsc.ufcg.edu.br/~abrantes/CursosAnteriores/ATAL051/DivConq.pdf.
MUNARI Júnior e AUGUSTO, P. (2007). Paradigmas e Técnicas de Projeto de Algoritmos.
Notas de Aula. ICMC/USP.
RIBEIRO, C. (1999). Programação Dinâmica. Notas de aula da disciplina Algoritmos e
Estruturas de Dados II. Licenciatura em Engenharia Informática e Computação. FEUP
ROSA, J. (2011) Programação Dinâmica. “Paradigmas de Resolução de Problemas. Slides”.
Universidade de São Paulo - Instituto de Ciência Matemática e Computação.
TOSCANI, L.A. e VELOSO, P.A.S. (2002). Complexidade de Algoritmos. Instituto de
Informática da UFRGS. Porto Alegre: Sagra Luzzatto.
VIANA, G.V.R. e CINTRA, G.F. (2011). Pesquisa e Ordenação de Dados. Fortaleza:
Publicação do Sistema UAB/UECE.
ZIVIANI, N. (2007). “Projeto e Algoritmos com implementações em Pascal e C”. São Paulo:
Editora Thomson.
Francisco Vando Carneiro Moreira
Graduado em Ciência da Computação – FLF
Mestrando Acadêmico em Ciência da Computação – MACC/UECE
e-mail: [email protected]
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
Gerardo Valdisio Rodrigues Viana
Bacharel em Engenharia Mecânica – UFC
Licenciado em Matemática – UFC
Doutor em Ciência da Computação – UFC/USP
e-mail: [email protected]
23
24
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
ANEXOS
public List<Mitem> MergeSortDefault(List<Mitem> a) {
if (a.Count == 1)
return a;
int middle = a.Count/2;
List<Mitem> left = new List<Mitem>(middle);
for (int i = 0; i < middle; i++)
left.Add(a[i]);
List<Mitem> right = new List<Mitem>(a.Count - middle);
for (int i = 0; i < a.Count - middle; i++)
right.Add(a[i + middle]);
left = MergeSortDefault(left);
right = MergeSortDefault(right);
int leftptr = 0;
int rightptr = 0;
List<Mitem> sorted = new List<Mitem>(a.Count);
ListaNew = new List<Mitem>(a.Count);
for (int k = 0; k < a.Count; k++) {
if (rightptr == right.Count || ((leftptr < left.Count) &&
((Convert.ToDecimal(left[leftptr].peso)) <= (Convert.ToDecimal(right[rightptr].peso)))))
{
sorted.Add(left[leftptr]);
leftptr++;
}
else if (leftptr == left.Count || ((rightptr < right.Count) &&
(Convert.ToDecimal(right[rightptr].peso)) <= (Convert.ToDecimal(left[leftptr].peso)))) {
sorted.Add(right[rightptr]);
rightptr++;
}
} return sorted;
}
}
A.1 – Programa em C# para o Problema da Mochila 0/1 – utiliza a Técnica de Divisão e
Conquista para a ordenação e um Algoritmo Guloso para selecionar os itens
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
public List<ArrayList> Ordem_Multiplicacao_Matriz(string[] p, int num)
{
int q = 0; int i = 0; int j = 0; int k = 0; int l = 0;
int[,] m = new int[sz, sz]; int[,] s = new int[sz, sz];
ArrayList M = new ArrayList(); ArrayList S = new ArrayList();
List<ArrayList> RetornoGeral = new List<ArrayList>();
int n = num;
for (i = 1; i <= n; i++)
m[i, i] = 0;
for (l = 2; l <= n; l++)
for (i = 1; i <= (n - l + 1); i++)
{
j = i + l - 1;
m[i, j] = INF;
for (k = i; k <= j - 1; k++)
{
q = m[i, k] + m[k + 1, j] + int.Parse(p[i - 1]) * int.Parse(p[k]) * int.Parse(p[j]);
if (q < m[i, j])
{
m[i, j] = q;
s[i, j] = k;
}
}
}
printSolutionParentheses(s, i - 1, j);
printm(m, s, n);
S.Add(resultadoSolution);
M.Add(resultadoMatrizM);
RetornoGeral.Add(M);
RetornoGeral.Add(S);
return RetornoGeral;
}
}
A.2 – Programa em C# para o Problema do Produto de Matrizes – utiliza a Técnica de
Programação Dinâmica para minimizar o número de multiplicações
25
26
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
A.3 – Tela do programa para o problema do Produto de Matrizes
Revista Científica da Faculdade Lourenço Filho - v.8, n.1, 2011
public List<ClassDC.Mitem> MochilaProgramacaoDinamica(int C, List<Mitem> obj)
int[,] dp = new int[C + 1, obj.Count];
int[,] d = new int[C + 1, obj.Count];
int[] D = new int[obj.Count];
for (int k = 0; k <= C; k++)
if (k < obj[0].peso) {
dp[k, 0] = 0;
d[k, 0] = 0;
}
else {
dp[k, 0] = obj[0].valor;
d[k, 0] = 1;
}
for (int i = 1; i < obj.Count; i++) {
for (int k = 0; k <= C; k++) {
if (k < obj[i].peso) {
dp[k, i] = dp[k, i - 1];
d[k, i] = 0;
}
else {
if (dp[k, i - 1] > (dp[k - obj[i].peso, i - 1] + obj[i].valor)) {
dp[k, i] = dp[k, i - 1];
d[k, i] = 0;
}
else {
dp[k, i] = dp[k - obj[i].peso, i - 1] + obj[i].valor;
d[k, i] = 1;
}
}
}
}
int k1 = C;
int ii = obj.Count - 1;
while (ii >= 0) {
D[ii] = d[k1, ii];
k1 -= (obj[ii].peso * D[ii]);
ii--;
}
for (int i = 0; i < D.Length; i++)
obj[i].x = D[i];
return obj;
}
A.4 – Programa em C# para o Problema da Mochila por Programação Dinâmica
27
{