Algoritmos e Estruturas de Dados/Estruturas para classes de equivalência: mudanças entre as edições
Linha 3: | Linha 3: | ||
=== Introdução === | === Introdução === | ||
Diversos problemas podem ser modelados através do cálculo de classes de equivalência (uma definição formal desse conceito é apresentada logo em seguida). Um exemplo famoso é aquele de determinar os componentes conexos de um grafo. Um grafo é um conjunto de vértices que podem ser conectados dois a dois por arestas. Como determinar se, dado o conjunto das arestas, existe um caminho entre dois vértices? Se considerarmos dois vértices como equivalentes quando existe um caminho entre os dois, então | Diversos problemas podem ser modelados através do cálculo de classes de equivalência (uma definição formal desse conceito é apresentada logo em seguida). Um exemplo famoso é aquele de determinar os componentes conexos de um grafo. Um grafo é um conjunto de vértices que podem ser conectados dois a dois por arestas. Como determinar se, dado o conjunto das arestas, existe um caminho entre dois vértices? Se considerarmos dois vértices como equivalentes quando existe um caminho entre os dois, então uma solução desse problema consiste em determinar se dois vértices fazem parte da mesma classe de equivalência. | ||
Edição das 13h35min de 22 de junho de 2006
Estruturas para classes de equivalência
Introdução
Diversos problemas podem ser modelados através do cálculo de classes de equivalência (uma definição formal desse conceito é apresentada logo em seguida). Um exemplo famoso é aquele de determinar os componentes conexos de um grafo. Um grafo é um conjunto de vértices que podem ser conectados dois a dois por arestas. Como determinar se, dado o conjunto das arestas, existe um caminho entre dois vértices? Se considerarmos dois vértices como equivalentes quando existe um caminho entre os dois, então uma solução desse problema consiste em determinar se dois vértices fazem parte da mesma classe de equivalência.
Definições
Uma relação binária sobre um domínio é uma relação de equivalência se satisfaz as seguintes propriedades
- ( é simétrica);
- ( é reflexiva);
- ( é transitiva).
Seja um elemento do domínio, a classe de equivalência de é o conjunto dos elementos relacionados com .
Objetivos
O objetivo é definir um tipo abstrato de dados que permita representar e manipular eficientemente classes de equivalência que evoluem dinamicamente, podendo tanto ser criada novas classes, quanto juntadas classes existentes. Também queremos ter uma operação que permite determinar a classe de equivalência de um elemento.
Para tanto, consideramos que o cliente do tipo abstrato de dados manipula valores de um determinado domínio que nomeamos domain.
O tipo abstrato de dados possuirá três operações: criação de uma nova classe, busca da classe de um valor, e união de duas classes.
- criação de uma nova classe de equivalência
- dado um elemento d de domain, cria uma nova classe comportando apenas como elemento d e retorna o handler associado a d. O cliente apenas poderá acessar a classe de d através desse handler. Portanto, é da responsabilidade do cliente manter uma associação entre valores e handlers dos valores.
- busca da classe de equivalência
- dado o handler de um elemento d de domain, retorna a classe de d.
- união de duas classes de equivalência
- dado os handlers de dois elementos d1 e d2 de domain, realiza a união das duas classes de equivalência de d1 e d2.
Apresentação das soluções
Os algoritmos e estruturas de dados que provêm implementação eficientes desse tipo abstrato de dados são conhecidos como algoritmos Union-Find (União-Busca), pelo tipo de operações que são providas. Outros nomes encontrados são disjoint sets (conjuntos disjuntos) e dynamic equivalence relations (relações de equivalência dinâmicas).
Existe basicamente duas estruturas de dados para implementar o tipo abstrato União-Busca: a baseada em listas, e a baseada em árvores. A estrutura de dados linear, baseada em listas encadeadas, é mais apropriada para aplicações onde o número de operações de união é pequeno com relação ao número de aplicações de busca. Em contrapartida, a estrutura de dados ramificada, baseada em árvores, é mais eficiente quando o número de união é proporcionalmente mais elevado que o número de buscas.