22 Algoritmo de Prim
Transcrição
22 Algoritmo de Prim
Algoritmo de Prim para encontrar uma MST de um grafo ENTRADA: Grafo G=<V,E> e uma função w(u,v) que atribui valores a cada aresta (u,v) de E. SAÍDA: Uma MST de G. Na verdade o que realmente importa é o conjunto de arestas. Estratégia: Constrói uma árvore a partir de um vértice inicial qualquer, incorporando os outros vértices de V um a um, junto com as arestas que o conectam à nova árvore sendo construída. Note que o que realmente importa são as arestas que vão sendo usadas para conectar os vértices incorporados. No algoritmo abaixo as arestas serão colocadas em E´e os vértices incorporados à MST sendo construída serão colocados em S. ALGORITMO de Prim (overview): 1. Inicializa o conjunto S (saída) com um vértice qualquer de V, digamos r, de raiz. Inicializa o conjunto Q com todos os vértices menos r ( Q <- V- {r} ). Note que sempre vamos ter a invariante F = V-Q. Inicializa o conjunto E´com vazio. 2. Faz |V|-1 vezes: 1. Escolha uma aresta <u,v> tal que e , que tenha valor mínimo dentre todas as outras. Isto é: considere o conjunto {<u,v>| e }, das arestas que conectam um vértice de S com um vértice de Q. O algoritmo escolhe a aresta de menor valor deste conjunto. 2. Insira <u,v> em E´ 3. Remova v de Q 4. Insira v em S 3. Perguntas: 1. Suponha que existam duas implementações diferentes do algoritmo acima, e ambas sejam executadas sobre o mesmo grafo, iniciando com o mesmo vértice r em S. É possível que as duas implementações gerem como saída MSTs diferentes? Justifique. 2. Por que o algoritmo funciona? Esta é a pergunta que não quer calar. 1. Primeiro convença que a escolha do vértice inicial r a ser colocado em S é irrelevante. 2. Depois verifique que, a cada início/fim de iteração, o grafo G´=<S,E´> é um subgrafo de G, e é uma árvore. 3. Considere a cada início de iteração o conjunto das arestas que cruzam entre S e Q, isto é, o conjunto {<u,v>| e }. Convença-se que pelo menos uma das arestas deste conjunto deverá ser incluída na MST sendo construída em <S,E´>. (Aliás, qualquer que seja a MST, construída por qualquer algoritmo, deverá ter pelo menos uma aresta deste conjunto. Por que?). Isto significa que a restrição na escolha das arestas à este conjunto a cada passo não é um problema. 4. O último ( e mais difícil ponto a ser provado ) é que a escolha da aresta de melhor valor, que é uma escolha ótima local, também conduz a um resultado ótimo global, isto é, a uma MST. Este argumento será visto em aula. Definições adicionais relacionadas ao algoritmo de Prim: 1. Um corte (cut) em um grafo G=<V,T> é uma partição qualquer de V com duas classes de equivalências. Representaremos o corte como um par <S, V-S> onde S é um subconjunto qualquer de V e V-S, obviamente, o seu complemento. No algoritmo acima, a cada início/fim de iteração, <S, Q> define um corte no grafo. 2. Uma aresta <u,v> cruza (crosses) um corte <S, V-S> se lembre que o grafo é não dirigido). e (ou vice-versa, Complexidade: A parte relevante do algoritmo é o passo 2, que executa |V| vezes os passos 2.1 até 2.4. Dentre estes o passo crítico é 2.1, que procura a aresta adequada. É fácil ver que a implementação deste algoritmo pode ser feita em O(|V|*|E|), basta fazer uma pesquisa sequencial em todas as arestas. Se o grafo for denso (como no exemplo da instalação elétrica que o grafo era completo, isto significará ~ passos. Como fazer para reduzir a complexidade? Ordenar as arestas? Fazer pesquisa binária no conjunto ordenado das arestas? AQUI CABE UM MOMENTO DE REFLEXÃO SOBRE AS ALTERNATIVAS A escolha de Prim foi pelo uso de uma "priority queue", implementada com uma "heap". (Aliás o escopo de uso de heaps é bem mais amplo do simplesmente um componente do heapsort.) A priority queue usa uma heap com operações para inserir elemento, extrair o maior/menor elemento (dependendo da utilização) e para consultar o maior/menor elemento.As operações de inserção e remoção são O(log n) e a de consulta O(1). Uma outra operação que pode ser também implementada na heap em O(log n) e adicionada à interface da priority queue é a de alteração da chave de um elemento (alteração da prioridade), com consequente necessidade de rearranjá-lo na heap. Esta operação é usada no algoritmo abaixo. No algoritmo abaixo, pode-se supor que Q é implementado como uma heap dos vértices, e a ordem dos vértices é de acordo com a função key[u]. A heap é organizada por valor mínimo e não máximo como no heapsort. O acesso à heap e através das primitivas de priority queue usadas no algoritmo. ALGORITMO de Prim (detalhe): MST-PRIM (G = <V, E>, w) // w é a função de valor 1. para cada vértice v de V 1. key[v] <- infinito 2. anterior[v] <- NULL 2. para algum vértice r qualquer de V 1. key[r] <- 0 3. Q <- V // Cria a heap (build-heap) usando a key[v] para comparar os vértices // Note que r está na raiz da heap 4. E' <- {} // Conjunto de arestas da MST inicia vazio 5. while Q != vazio (ou, faça |V| vezes) 1. u < extract-min // extrai vértice da raiz da heap e reorganiza heap 2. se (anterior[u] != NULL) 1. E'. insere (<anterior[u], u>) 3. para cada v em Adj(u) 1. if v está em Q e w(u,v) < key[v] 1. anterior [v] <- u 2. key [v] <- w(u,v) // Atenção: Isto também reorganiza a heap, mas de uma forma que não tinhamos visto antes (* ver nota abaixo *) 6. NOTA: O algoritmo acima exige uma heap que suporte alteração do valor da chave dos seus elementos (alteração de prioridade) !!!! Infelizmente as heaps das bibliotecas das linguagens (e.g. biblioteca STL do C++) não tem esta operação, que aliás pode ser feita em tempo . Complexidade do algoritmo: 1. Passo 3 é Theta (|V|) 2. O passo 4.1 é executado um total de |V| vezes cada vez com tempo log(n´) onde n´ é o número de vértices remanescentes na heap. No total o custo é Theta (|V| log (|V|)). 3. O passo 4.2.1.1 também leva tempo log(n´), mas é executado uma vez para cada aresta (confira isto). O total, portanto, é Theta (|E|*log(|V|). Somando tudo, a complexidade é número de arestas é no mínimo |V|-1, podemos simplificar como . Como o grafo é conexo, e assim o . NOTA: A análise acima assume que as operações da heap tem custo . Isto corresponde à heap vista anteriormente com o heapsort. Existem implementações de heap ainda mais eficientes do que aquela (binomial heap, Fibonacci heap). Naquele momento isto não fazia diferença, mas para este algoritmo faz. Não vamos abordar isto aqui. Fazer exemplo completo em aula executando o algoritmo
Documentos relacionados
Problema da Árvore Geradora Mínima
elétricas) entre um conjunto de localidades, utilizando a infra-estrutura das rodovias com o menor uso de material. Outros casos como análise de clusters, armazenamento de informações, dentre outro...
Leia maisMinimum Spanning Tree Algoritmos de Prim e Kruskal Algoritmo de
Algoritmos e Estrutura de Dados II
Leia mais