Algoritmos: Quick Union

by Bugan 0 Comments
Algoritmos: Quick Union

No ultimo post sobre algoritmos falei sobre o Union Find Problem e sobre o algoritmos que chamamos de Quick Find que resolve nosso problema, fazendo as ligações entre elementos dentro de um grafo. Porém a solução que encontramos era muito lenta para problemas reais onde podemos ter milhões de dados para serem processados. É por isso que estou aqui hoje, para falarmos de uma outra possível solução para esse problema, se você ainda não viu o post onde eu falo sobre Union Find é melhor você correr lá antes de continuar lendo esse texto.

Bom então vamos lá…

Como vimos o método Union do código anterior  fazia N2 acessos à memória, no pior caso, para então unir dois nós dentro do nosso grafo. Pensando em reduzir o processamento do nosso programa precisamos achar novas formas de visualizar o problema e como soluciona-lo, de preferência utilizando a mesma estrutura de dados. Ao estudar algoritmos você verá metodologias criadas para ajudar na solução de problemas diversos, uma dessas metodologias é chamada de Lazy Approach onde evitamos fazer qualquer trabalho até que seja estritamente necessário.

Por exemplo, no algoritmo do Quick Find ao executarmos a função Union mudávamos todos os valores do Array Id que fossem iguais a id[p] para serem iguais a id[q]. Seguindo o lazy approach devemos pensar em uma maneira de alterar apenas o mínimo possível os dados em nossa estrutura.

Estrutura de Dados

Para esse algoritmo utilizaremos a mesma estrutura de dados utilizada no Quick Find, ou seja um array Id onde cada entrada representa um nó dentro do grafo. Apesar de estarmos usando a mesa estrutura nossa interpretação sobre os valores desse array devem mudar. O valor dentro do array Id não irá mais indicar a qual grupo aquele nó pertence, ele irá representar quem é o pai daquele elemento, assim estarão ligados elementos que tiverem o mesmo pai ou raiz. Essa nova interpretação cria uma estrutura de árvores e para conectarmos dois grupos de elementos devemos ligar suas respectivas raízes. Facilitando muito o trabalho de ligar grupos grande.

paralaxy-quickunion-04

A desvantagem dessa interpretação é que perdemos performance na função Connected que precisará percorrer as árvores procurando a raiz delas para, então, verificar se os elementos possuem a mesma raiz.

Quick Union

A implementação desse algoritmo é muito parecida com a do QuickFind, apenas acrescentamos uma função a mais que é responsável por achar a raiz de um nó da arvore. E alteramos as funções Union e Connected para se comportarem de acordo com a nova interpretação dos dados do Array id

Eficiência

Infelizmente esse algoritmo ainda é muito lento, apesar de que na maioria das vezes ele ser mais rápido que o Quick Find no pior caso ele é mais lento. Os métodos Connnected Union estão diretamente vinculados ao método root assim dependem de quão bem essa parte do código consegue exercer sua função. Bom, o método root em seu melhor caso (Quando o elemento analisado é a raiz da árvore) irá executar 1 única vez o loop  para achar a raiz de uma árvore, porém em seu pior caso (Quando todos os elementos estão ligados em uma sequência.) ele deverá passar por todos os elementos do grafo para chegar a raiz executando o loop N vezes.

paralaxy-quickunion-05

Assim esse algoritmo é mais eficiente que o anterior em alguns casos, mas ainda não é rápido o suficiente. Vou ficando por aqui e pensando em melhorias que posso fazer para achar a solução para esse problema. Enquanto isso dêem uma curtida na nossa página do Facebook e digam aqui embaixo  o que vocês estão achando desse Algoritmo.

Deixe uma resposta