Algoritmos de Otimização

Prévia do material em texto

Universidade Estadual Paulista “Ju´lio de Mesquita Filho”
FCT-UNESP
Projeto e Ana´lise de Algoritmos
Trabalho Pra´tico - 02
Gabriel de Oliveira Almeida
Gustavo Lopes Santana
Joa˜o Victor Silva Menezes
Prof. Dr. Danilo Medeiros Eler
Presidente Prudente - SP
Suma´rio
1. Introduc¸a˜o 3
2 Associac¸a˜o de Tarefas (Assignment Problem) 3
2.1 Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 O Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3 Complexidade do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Codificac¸a˜o de Huffman 3
3.1 Algoritmo Guloso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 O Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Complexidade do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Mochila Fraciona´ria (Fractional Knapsack Problem) 5
4.1 O programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Complexidade do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5 Mochila Booleana (Knapsack Problem) 5
5.1 Programac¸a˜o Dinaˆmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2 O Programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2.1 Complexidade do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6 Subsequeˆncia Comum Ma´ximo (Longest Common Subsequence) 7
6.1 O programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Complexidade do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
7. Conclusa˜o 7
31. Introduc¸a˜o
Este trabalho tem como pauta apresentar as soluc¸o˜es para problemas computacio- nais, utilizando te´cnicas
de projeto de algoritmos, tais como Branch-and-Bound, Algoritmos Gulosos e Programac¸a˜o Dinaˆmica afim de
solucionar os problemas propostos. No decorrer deste relato´rio, cada soluc¸a˜o e´ descrita e apresentadas imagens da
execuc¸a˜o de cada algoritmo.
Todos os algoritmos foram desenvolvido na linguagem JAVA.
Problemas Propostos
2 Associac¸a˜o de Tarefas (Assignment Problem)
Esse problema consiste em associar n pessoas a n tarefas , onde cada pessoa fica com uma tarefa e a soma do
tempo dessas tarefas escolhidas seja a menor possı´vel.
2.1 Branch and Bound
O me´todo utilizado para resolver esse problema foi o branch and bound, consiste em dividir o conjunto de
soluc¸o˜es em problemas menores (branch) e um limite (bound) indica que na˜o pode conter uma soluc¸a˜o o´tima, caso
o subconjunto passe do limite ele e´ descartado ate´ que no final fique apenas a soluc¸a˜o.
2.2 O Programa
Foi utilizado uma matriz n×n contendo o tempo das tarefas de cada pessoa, e tambe´m dois vetores o da soluc¸a˜o
e um auxiliar em que cada posic¸a˜o ‘0’ dos vetores tem a soma do tempo da possı´vel soluc¸a˜o e a posic¸a˜o ‘1’ em
diante sa˜o as tarefas armazenadas.
Figura 1. Exemplo com 4 pessoas/Tarefas com dados randoˆmicos
Na interface basicamente o usua´rio escolhe o numero de pessoas/tarefas, ha´ duas escolhas de entrada de dados
manualmente ou randomicamente e embaixo sera´ o resultado total de tempo da soluc¸a˜o como demonstrado na
figura 2.
2.3 Complexidade do Algoritmo
O programa passara por todas as soluc¸o˜es, enta˜o a primeira pessoa tem n tarefas ja´ a segunda tem n−1 e assim
por diante, logo a complexidade sera´ fatorial.
Complexidade do Algoritmo no pior caso: O(n!).
3 Codificac¸a˜o de Huffman
Esse problema tem como objetivo atribui co´digos menores para sı´mbolos mais frequentes e co´digos maiores
para sı´mbolos menos frequentes de modo que seja u´nico para cada simbolo, na˜o apresentando ambiguidade.
Figura 2. Resultado do exemplo da Figura 1
3.1 Algoritmo Guloso
Para resoluc¸a˜o desse problema foi utilizado um Algoritmo Guloso, em que a te´cnica consiste em tentar resolver
o problema fazendo a escolha localmente o´tima (gulosa), isto e´, aquele que parece ser a melhor naquele momento,
desconsiderando resultados de subproblemas, feito isso, em cada fase com ha´ a finalidade de alcanc¸ar uma soluc¸a˜o
o´tima global.
3.2 O Programa
Para isso foram utilizados uma matriz de String de ordem n× 2, onde sera´ armazenado o resultado, e tambe´m
foi implementado uma Lista, para guardar o numero de repetic¸o˜es de cada cara´cter e o pro´prio cara´cter, desse
modo todos os dados sa˜o ordenados em ordem crescente em relac¸a˜o a frequeˆncia, e assim pode dar inicio a
construc¸a˜o da arvore de Huffman, em que cada novo no´ e´ a soma das duas menores frequeˆncia, e que novamente e´
posicionado a lista e ordenado - simulando uma estrutura de prioridades - ate´ que reste apenas um elemento, para
ocorrer o fim do lac¸o de repetic¸a˜o da construc¸a˜o da arvore de Huffman. Os no´s internos tera˜o o cara´cter vazio
armazenado.
Apo´s a construc¸a˜o da a´rvore, podemos iniciar a leitura da a´rvore recursivamente, 0 a` esquerda, 1 a` direita ate´
encontrar o no´ que possui o cara´cter de entrada.
A interface do programa possui apenas uma entrada, o qual sera´ codificado. Lembrando que todos os espac¸os,
tabulac¸o˜es e quebra linha, na˜o pertencera˜o a codificac¸a˜o, conforme o exemplo da figura 3.
Figura 3. Programa em execuc¸a˜o da codificac¸a˜o de Huffman
3.3 Complexidade do Algoritmo
O Algoritmo requer possui entrada de dados de tamanho n, em que sa˜o ordenado pelo me´todo sort da Classe
Collections, conforme sua documentac¸a˜o oficial utiliza o Merge Sort, portanto, e´ correto afirmar que sua com-
plexidade e´ O(n logn)
Complexidade do Algoritmo no Pior Caso: O(n2 logn)
4 Mochila Fraciona´ria (Fractional Knapsack Problem)
Seja um conjunto de n itens e uma mochila, para cada item i = 1, 2, . . . , n. e´ dado um peso p positivo e
diferente de 0 e um valor v positivo. A mochila deve apenas carregar um peso que na˜o exceda sua capacidade
ma´xima C. Dessa forma, deve-se determinar o conjunto de itens podem ser carregados na mochila, respeitando
sua capacidade, de modo a maximizar o valor transportado. A mochila Fraciona´ria pode carregar uma parcela do
item, ou seja, para o item i temos:
1. 0 6 xi 6 1, representa uma frac¸a˜o do item.
2. p · xi cada objeto contribui para o peso total.
3. v · xi cada objeto contribui para o valor total.
Desse modo, chegamos a desigualdade: 1
n∑
i=0
pi · xi 6 C (1)
4.1 O programa
Para resoluc¸a˜o desse problema foi utilizado um Algoritmo Guloso, um requisitos para encontrar a soluc¸a˜o sera´
os argumentos de entrada ordenado respeitando a desigualdade 2.
vi
pi
6 vj
pj
; i < j. (2)
O programa ficara´ responsa´vel pela ordenac¸a˜o, com os dados armazenados em uma lista, contendo as informac¸o˜es,
da proporc¸a˜o (valor por unidade de peso de cada objeto), a posic¸a˜o correspondente aos valores de entrada, e o
peso. O algoritmo sempre pegara´ o item de maior valor e subtrair seu peso com a capacidade ma´xima ate´ encher a
mochila, considera cheia quando adicionamos a primeira frac¸a˜o de um item, ou atingir sua capacidade ma´xima.
Ha´ a disponibilidade do programa executar o co´digo com valores aleato´rios de 1 a 100, pore´m a capacidade da
Mochila, gera um valor de 0 a 150, podendo ser alterado a qualquer momento pelo o usua´rio.
Apo´s pressionar o bota˜o Calcular o resultado representara´ a porcentagem (xi) do que foi colocado a mochila
do peso do item i, conforme mostrado a interface gra´fica na figura 4
4.2 Complexidade do Algoritmo
A ordenac¸a˜o dos dados e´ utilizada a mesma forma como citada na Secc¸a˜o 3.3, e que o pior caso para algoritmopara resoluc¸a˜o da Mochila Fracionaria, sera´ percorrer todo o vetor de tamanho n. Logo, podemos afirmar que a
complexidade da ordenac¸a˜o domina assintoticamente a complexidade do algoritmo guloso, enta˜o temos:
Complexidade do Algoritmo no Pior Caso: O(n log n).
5 Mochila Booleana (Knapsack Problem)
Assim como na mochila booleana fracionaria Secc¸a˜o anterior (4), tem exatamente o mesmo problema, pore´m
na˜o deve fraccionar os itens, ou seja, ele pertence ou na˜o ao resultado final, nesse caso, na˜o sera´ sempre que
ocupara´ toda a capacidade ma´xima da mochila.
Figura 4. Programa Mochila Fracionaria com valores Aleato´rios
5.1 Programac¸a˜o Dinaˆmica
Para resoluc¸a˜o desse problema, utilizaremos a programac¸a˜o dinaˆmica, como requisitado.
A programac¸a˜o a escolha depende de cada soluc¸a˜o dos subproblemas, partindo do subproblemas menores para
os maiores, armazena os resultados e reusa somente as soluc¸o˜es o´timas. Os resultados sa˜o armazenados em uma
tabela.
5.2 O Programa
Para o armazenamento dos dados, foram utilizados duas matrizes: uma com resultados o´timos de subproblemas
menores (M) e outra com os dados para recuperar resultado final.
Seja p e v o conjunto de dados de entrada, peso e valor, respectivamente. C a capacidade ma´xima da mochila e
n a quantidade dos itens, temos que:
1. i = 0, 1 . . . n
2. b = 0, 1 . . . C
3. Constro´i uma matriz(tabela) M [i, b], com a primeira linha e coluna iguais a 0.
Logo a matriz M satisfaz a recorreˆncia, para todo i > 1 e todo b.
M [i, b] =
{
M [i− 1, b]; se pi > b.
max(M [i− 1, b],M [i− 1, b− pi] + vi); se pi 6 b.
(3)
Desse modo, ha´ construc¸a˜o da tabela M e tambe´m e´ feita a tabela auxiliar A, e´ do tipo Booleano, desse modo,
temos que ela e´ construı´da a partir dos resultados recebidos pela matriz M em sua construc¸a˜o dado por:
A[i, b] =
{
true; se Mi,b =M [b− pi] + vi.
false; caso contra´rio.
(4)
Para recuperar o resultado, percorre a matriz auxiliar, se encontrar posic¸o˜es verdadeiras, adiciona verdade no
vetor soluc¸a˜o, e volta pi colunas, se na˜o, a posic¸a˜o i do vetor soluc¸a˜o recebera´ falso. O lac¸o de repetic¸a˜o continua
ate´ encontrar uma margem da matriz.
A interface gra´fica do Programa Mochila Booleana, e´ semelhante ao programa mochila fracionaria, mas ela [e
capaz de retornar em porcentagem o uso total da mochila, apo´s o termino do algoritmo, uma vez que, o algoritmo
na˜o fracciona os itens, para preencher a mochila. Como demostrado na figura 5.
5.2.1 Complexidade do Algoritmo
Por possuirmos uma matriz de ordem n× C e´ correto afirmar que:
Complexidade do Algoritmo no Pior Caso: O(n · C).
Figura 5. Programa Mochila Booleana com valores Aleato´rios
6 Subsequeˆncia Comum Ma´ximo (Longest Common Subsequence)
Uma subsequeˆncia comum de duas X e Y e´ uma sequencia que e´ tanto subsequeˆncia de X quanto de Y (por
exemplo, X = mestrados e Y = matrizes, enta˜o, temos ma). Pore´m, nosso problema consiste em encontrar
a subsequeˆncia comum ma´ximo de X e Y , em que e´ uma subsequencia comum de comprimento ma´ximo entre
todas as subsequencia comuns (no exemplo anterior, ela pode ser mtr).
6.1 O programa
Para solucionar o problema, sera´ necessa´rio utilizar conceitos da programac¸a˜o dinaˆmica, como comentado,
na secc¸a˜o anterior. Sabendo disso, precisamos criar uma tabela (matriz) para resoluc¸a˜o do problema, seja, n o
tamanho de X e m o tamanho de Y , teremos uma matriz de ordem (m+ 1) × (n+ 1), em que a primeira linha e
coluna consiste em ser igual a 0. Logo, temos que a tabela (matriz) M :
M [i, j] =
{
M [i− 1, j − 1] + 1; se Xi−1 = Yi−1.
max(M [i, j − 1],M [i− 1, j]); caso contra´rio. (5)
E tambe´m ha´ construc¸a˜o da tabela Auxiliar A para recuperac¸a˜o da soluc¸a˜o, em que consiste em receber valores
dependentes da matriz M , assim, temos os valores e seus significados para o algoritmo:
A[i, j] =

1 (Diagonal); se Mij =Mi−1,j−1 + 1.
2 (Esquerda); se Mij =Mi,j−1.
3 (Acima); se Mij =Mi−1,j .
(6)
Apo´s as construc¸o˜es das matrizes, a recuperac¸a˜o da soluc¸a˜o consiste em um algoritmo recursivo, com entrada
a matriz auxiliar, m e n. assim consiste em percorrer de acordo com os significados de cada posic¸a˜o, se diagonal
pertence a soluc¸a˜o, ate´ encontrar a margem da matriz.
A interface gra´fica do algoritmo, tem apenas duas entradas, uma para X e outra para Y , ao pressionar seu u´nico
bota˜o temos a soluc¸a˜o da problema proposto, como na figura 6.
6.2 Complexidade do Algoritmo
Por possuirmos uma matriz de ordem m× n e´ correto afirmar que:
Complexidade do Algoritmo no Pior Caso: O(m · n).
7. Conclusa˜o
Branch and Bound e´ o que exige maior esforc¸o na implementac¸a˜o e no entendimento dos seus conceitos. En-
tretanto, este algoritmo, apresentou bons resultados para o problema da Associac¸a˜o de Tarefas, apesar de possuir
complexidade fatorial no pior caso.
Figura 6. Programa Subsequencia ma´xima comum encontrada
A mochila fracionaria teve uma implementac¸a˜o simples e bem barato em relac¸a˜o ao tempo e memoria, utilizando
o algoritmo guloso, que serviu bem tambe´m a` construc¸a˜o da A´rvore de Huffman, ja´ que o menor sempre encaixa
na soluc¸a˜o do problema.
Por fim, Programac¸a˜o dinaˆmica e´ de suma importaˆncia para a soluc¸a˜o de diversos problemas, onde cada
instaˆncia maior pode ser dividida e calculada em torno de subdiviso˜es. Logo, evita-se o desperdı´cio computacional
ao se usar programac¸a˜o dinaˆmica. Para a Mochila Booleana e Subsequencia, como se trata de um problema bidi-
mensional sempre nos levara´ a soluc¸o˜es de complexidade O(n ×m). Uma vez que para encontrar a otimizac¸a˜o
global, ha´ necessidade de armazenamento em tabelas para a soluc¸a˜o o´tima dos subproblemas -locais - e logo a
soluc¸a˜o do problema.
Diante dos dados expostos, foi possı´vel observar, compreender e implementar diferentes te´cnicas de projeto de
algoritmos para solucionar os problemas propostos.
Refereˆncias
[1] M. Castro. Problema da mochila - knapsack problem. Disponivel em: https://www.slideshare.net/
mcastrosouza/problema-da-mochina-01-knapsack-problem, Acessado em: 2017-12-29.
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Algoritmos: teoria e pra´tica. Editora Campus, 2, 2002.
[3] Collection (java plataform). Disponivel em: https://docs.oracle.com/javase/7/docs/api/java/util/
Collections.html , Acessado em: 2017-12-28.
[4] P. Feofiloff. Programacao dinamica. Disponivel em: https://www.ime.usp.br/˜pf/analise_de_
algoritmos/aulas/dynamic-programming.html, Acessado em: 2017-12-28.
[5] A. Rocha and L. B. Dorini. Algoritmos gulosos: definicoes e aplicacoes. Campinas, SP, page 42, 2004.
[6] C. Tjandraatmadja. O problema da subsequeˆncia comum ma´xima sem repetic¸o˜es. PhD thesis, Universidade de Sa˜o Paulo,
2010.
	. Introdução
	Associação de Tarefas (Assignment Problem)
	Branch and Bound
	O Programa
	Complexidade do Algoritmo
	Codificação de Huffman
	Algoritmo Guloso
	O Programa
	Complexidade do Algoritmo
	Mochila Fracionária (Fractional Knapsack Problem)
	O programa
	Complexidade do Algoritmo
	Mochila Booleana (Knapsack Problem)
	Programação Dinâmica
	O Programa
	Complexidade do Algoritmo
	Subsequência Comum Máximo (Longest Common Subsequence)
	O programa
	Complexidade do Algoritmo
	. Conclusão