Sub-Vetor de Soma Mínima Contínuo: Algoritmos de Programação Dinâmica e Força Bruta

Prévia do material em texto

RELATÓRIO 3 
Sub-Vetor de Soma Mínima Contínuo 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
UNIVERSIDADE FEDERAL FLUMINENSE 
INSTITUTO DE COMPUTAÇÃO 
DISCIPLINA: ANÁLISE E PROJETO DE ALGORITMOS 
PROFESSORA: KARINA MOCHETTI 
ALUNO: JORGE FELIPE CAMPOS CHAGAS 
 
 
 
OBJETIVO 
 
 Construir e analisar 2 algoritmos para o resolver o problema do Sub-Vetor de Soma Mínima 
Contínuo, onde dado um conjunto de elementos deve-se retornar o subconjunto que possui a menor soma. 
Serão construídos 2 algoritmos um por programação dinâmica e outro por força bruta. 
 
INTRODUÇÃO 
 
 
Programação dinâmica também é sintetizar a solução para grandes problemas com as soluções de 
problemas menores. A idéia central subjacente ao DP é desenvolver uma função de recursão para 
transferir um estado para outro. Suponha que tenhamos conhecido a soma máxima de subseqüências 
para os primeiros elementos i (V (1) ... V (i)). Para a sequência V (1) ... V (i + 1), precisamos determinar se 
a subsequência máxima inclui ou não o elemento V (i + 1). Se incluir, a subseqüência máxima para os 
primeiros elementos i + 1 é uma subsequência que termina com o elemento A (i). Caso contrário, a 
subsequência máxima para os primeiros elementos i + 1 é a mesma que a dos primeiros i elementos. A 
função de recursão é definida da seguinte maneira: sub (i) = MAX {sub (i - 1), soma (i)} onde soma(i) é a 
soma máxima da subsequência terminada com o elemento A (i). 
Já o algoritmo de força bruta vai expandir todas as possíveis subsequências e guardar aquela que 
retorna o menor valor. Dado um conjunto de n elementos o número máximo de subsequências geradas 
será de 2n, ou seja, dado um conjunto de 4 elementos A={0,1,2,3}, ela vai gerar no máximo 24 
subsequências e uma delas será a de menor soma. No primeiro loop do algoritmo escolhemos o elemento 
A(i), então a partir do elemento A(i) realizamos a soma até A(n), em seguinda, A(n-1) até A(i+1), e o loop 
segue até percorrermos todos os elementos. 
 
 
DESENVOLVIMENTO 
 
 
 No trabalho foi utilizado um notebook i3-6100u(3MB Cache e 2.4GHZ),1 MÓDULO de 4GB RAM 
DDR3 1600 MHZ(memória compartilhada com placa de vídeo), HD 500GB 7200RPM SATA3, INTEL HD 
GRAPHICS 520HD(Integrado), SO WINDOWS 10,compilador GCC. Na tabela a seguir temos os testes , 
na colunas colunas seguinte o número de comparações dos 2 algoritmos e o nº de elementos e a soma. 
 
 
TABELA 1: Número de comparações por algoritmo 
TESTE Brute Force P.Dinâmica Nº Elementos SOMA 
1 2 2 1 -9076 
2 15 3 2 -1256 
3 627 11 10 -6616 
4 3742 31 20 -40304 
5 358734 115 100 -37562 
6 2767324 229 200 -20227 
7 335836764 1061 1000 -248612 
8 -1618293996 2085 2000 -396370 
9 -1424083764 10214 10000 -949162 
10 Falhou Falhou 20000 -719196 
 
Análise dos testes: 
A partir dos teste 8 a representação numérica teve overflow e não foi possível contar corretamente 
o número de comparações do força bruta. O teste 10 estourou o espaço de memória e o pc travou. 
 
 
CONSIDERAÇÕES FINAIS 
 
 Apesar do algoritmo força bruta ter tido um desempenho bem pior que o de programação dinâmica 
ele tem a vantagem de não precisarmos ter uma subestrutura ótima e não dependemos da sobreposição 
de problemas ao custo de tempo. A programação dinâmica precisa alocar os resultados dos subproblemas 
em uma tabela e a alocação de memória vai estar vinculada a maneira que dividimos os subproblemas.