Algoritmos: Union Find

by Bugan 0 Comments
Algoritmos: Union Find

Estudar algoritmos é uma tarefa que todo programador deveria se propor a fazer regularmente. O fato é que existem muitos algoritmos já criados para uma enorme variedade de tarefas computacionais e conhecendo alguns desses códigos pode facilitar e muito a solução de um problemas dentro de seu jogo. Seja um problema de lógica ou um problema de performance. Então aqui estou eu voltando a escrever para a Paralaxy (depois de muitos meses sem dar noticias, eu sei….) e resolvi trazer fazer uma série de posts sobre algoritmos, então vamos lá!

 

Para começarmos a estudar algoritmos devemos ter um método de como iremos atacar os problemas apresentados de forma pragmática e consistente. Aqui estão alguns passos que veremos frequentemente durante a analise de diversos algoritmos: 

  • Analise e modelagem do problema
  • Busca por um algoritmo que resolva o problema
  • O algoritmo é rápido o suficiente? Ele está dentro das especificações do uso de memória?
  • Se não, procuraremos o porquê.
  • Desenvolveremos novas formas de solucionar o problema
  • Repetir esses passos até que o algoritmo satisfaça as especificações.

Esses passos são parte de uma abordagem cientifica para resolvermos os problemas, onde construímos modelos matemáticos para saber o que está acontecendo e fazemos experimentos para validar nossas hipóteses.

Para o problema de hoje iremos explorar o problema de conectividade dinâmica dentro de um grafo.

O Problema

O problema da conectividade dinâmica se refere a uma estrutura de dados que consiga manter informações de quais elementos estão interconectados dentro de um grafo. Digamos que temos um conjuntos de N objetos e fazemos uma série de operações para liga-los uns aos outros através do comando Union assim os elementos (4, 3) , (3, 8), (6, 5), (9, 4) e (2, 1) estarão ligados após essa série de operações. Agora queremos saber se os elementos 0 e 7 estão ligados ou se por acaso 8 e 9 estão ligados, para isso usaremos o comando Connected que dever retornar um valor verdadeiro ou falso.paralaxy-quickfind-01

“Para que eu vou usar isso?”

Depende…. Depende muito de quais os objetos que você está utilizando; se estivermos dentro de uma rede de computadores nossos objetos serão os próprios computadores, em uma rede social as pessoas, esse algoritmo também é utilizado no processamento de imagens, onde usaríamos pixels como nossos objetos. Dentro de um jogo podemos pensar que o grafo representaria nosso mapa e poderíamos verificar se dois pontos do mapa estão ligados antes de executar um algoritmo de Path Finding para descobrir o caminho que o personagem deve seguir. Eu particularmente gosto de usar números já que eles são facilmente abstraídos dando assim flexibilidade ao algoritmo.

Assim agora que temos um problema definido, vamos pensar em quais são os elementos e funções que nosso código deve suportar para conseguirmos resolver esse problema. Claramente temos que dar suporte a dois métodos dentro de nosso código um que irá conectar dois elementos do grafo(Union) e outro que irá verificar se dois elementos estão ligados (Connected) para que esses métodos executem corretamente temos que dar um suporte às informações que elas irão alterar/verificar, assim devemos ter um  array contendo os objetos de nosso grafo.

Classe UnionFind

Trazendo o problema mais para o lado prático podemos agora construir um modelo de Classe que resolva nosso problema, levando em conta que:

  • O grafo pode ter N componentes, onde N pode ser um numero gigante.
  • Podemos executar M comandos, novamente, M podendo ser um numero gigante.
  • Os comandos de Union e Connected podem ser executados alternadamente.

paralaxy-quickfind-02

Quick Find

Essa solução para o problema da conectividade dinâmica é conhecido também como eager approach e é simples de ser implementado, apesar de que podemos nos confundir em um dos passos causando um bug dentro do código. Para implementarmos essa solução iremos utilizar como estrutura de dados um Array id[] de tamanho N onde os elementos p e estão conectados se e somente se tiverem o mesmo id

paralaxy-quickfind-03

O bug que eu comentei acima acontece geralmente na função Union  onde ao invés de colocarmos

Utilizaríamos

Vou deixar para que vocês deduzam o porque que isso cauda um bug no algoritmo.

Eficiência

Notem que eu também coloquei  um comentário na primeira linha de cada função com a quantidade de vezes que aquela função acessa o array Id, isso porque podemos usar acessos a array como um parâmetro de eficiência para nosso código. Uma vez que cada acesso ao array significa que estamos indo buscar algo na memória do computador e cada acesso a memória pode ser feito em alguns nanosegundos se executarmos muitos acessos teremos uma resposta demorada de nosso programa.

Ao analisarmos esses valores veremos que o QuickFind tem um defeito, a função Union é muito lenta. Se executarmos N conexões em  N objetos veremos que teríamos uma quantidade de N2 acessos ao array Id e algoritmos que executam nessas proporções não escalam conforme a tecnologia evolui. Pois uma vez que temos computadores 10 vezes mais memória podemos endereçar problemas 10 vezes maiores e assim demoraríamos 10 vezes mais tempo para obter a resposta.

Espero que vocês tenham gostado e que tenha sido instrutivo, voltarei aqui com outro algoritmo para esse mesmo problema que, com sorte, resolverá o problema que achamos no QuickFind e não se esqueça de curtir e compartilhar com seus amigos programadores e se puder dá uma passada na nossa página do Facebook!

Deixe uma resposta