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 P i > 0 e uma utilidade, ou valor, V i > 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
Transcript
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 in ic io se i n i < f im m e io = ( in i + f im ) /2 / / d iv i são in te i r a se i n i < m e io M ERGESORT(L , in i , m e io ) se (m e io + 1 ) < f im M ERGESORT(L , m e io + 1 , f im ) M ERGE(L , in i , m e io , f im ) f im {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
in ic io i = in i ; k = 1 ; j = m e io + 1 enquanto ( i ≤ m e io e j ≤ f im ) 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
s e ( i > m e io ) p = j q = f im senão
p = i q = m e io para i = p a t é q S [k ] = L [ i ] k = k + 1 / / f im pa ra L [ in i . . f im ] = S [1 . . ( f im - in i+1) ] re torna (L )
f im {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) In ic io
So l = 0 para i = 1 a té n
L[ i ] = V[ i ] / P [ i ] / / f im pa ra
M ERGESORT ( L , 1 , n )
para i = 1 a té n e enquanto C ≠ 0 j = C / P [ i ] / / d iv i são in te i r a X[i ] = m in { j , 1 } C = C – X[ i ]*P[ i ] So l = So l + X[ i ]*V[ i ] / / f im pa ra escreve ( So l , X[ j ] , j=1 . .n )
f im {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(50x20) ; A 2 =B(20x1) ; A 3 =C(1x10) e A 4 =D(10x100) ,
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(pxq ) uma matriz com p linhas e q colunas, sabemos que o produto das
matrizes X(pxq ) por Y(qx r ) existe e requer (p.q.r) multiplicações para obter Z (px r )=XY .
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 xm 1 ) , (m 1 xm 2 ) , . . . , (m n - 1 xm 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 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 como mínimos
de multiplicações escalares para calcular a matriz Ai..j então, temos pois Ai..i = Ai e
não há nenhum cálculo 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 in ic io para i =1 a té n M [ i , i ]=0 para L= 2 a té n para i= 1 a té n -L+1 j = i + L – 1 M [ i , j ] = ∞ para k= i a t é 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 re turn M [1 ,n ] , S f im {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 ) in ic io se i = j p r in t “A”
senão pr in t “ (”
PRINT_CADEIA ( S , i , S [ i , j ] ) PRINT_CADEIA ( S , S [ i , j ] + 1 , j ) pr in t “ )”
f im { 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 19
in ic io para i = 1 a té C
M [ i ,0 ] = 0 para j = 1 a té n
M [0 , j ] = 0 X [ j ] = 0
para i = 1 a té C se P [ j ] > i M [i , j ] = M [ i , j− 1] senão M [ i , j ] = m ax ( M [ i , j− 1] , M [ i− P[ j ] , j− 1] + V[ j ] / / fim para So l = M [C ,n ]
/ / rotina para determinar o vetor X (itens selecionados)
aux = So l j = n enquanto j > 0 s e 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 f im { M och i la_0 /1_PD }
Figura 10 – Algoritmo para o Problema da Mochila por Programação Dinâmica
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.
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 23
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]
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 25
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
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 27
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
