Baixe o app para aproveitar ainda mais
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
Compartilhar