Algoritmo de Hopcroft–Karp

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Em ciência da computação, o algoritmo de Hopcroft–Karp é um algoritmo que recebe como entrada um grafo bipartido e produz como saída um máximo de cardinalidade de acoplamento – um conjunto de quantas arestas forem possíveis com a propriedade de que não há duas bordas compartilhando um ponto na extremidade. Ele roda em tempo  no pior caso, onde é o conjunto de arestas do grafo, e é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se e para grafos aleatórios ele é executado em tempo quase linear.

O algoritmo foi encontrado por John Hopcroft e Richard Karp (1973) . Como nos métodos anteriores para acoplamento, tais como o algoritmo húngaro e o trabalho de Edmonds (1965), o algoritmo de Hopcroft–Karp aumenta várias vezes o tamanho de um acoplamento parcial encontrando caminhos extensores. No entanto, em vez de encontrar apenas um único caminho extensor por iteração, o algoritmo encontra um conjunto máximo de caminhos extensores mais curtos. Como resultado, apenas iterações são necessárias. O mesmo princípio também foi utilizado para desenvolver algoritmos mais complicados para acoplamentos não-bipartidos com o mesmo tempo de execução assintótica do algoritmo de Hopcroft–Karp.

Caminhos Extensores[editar | editar código-fonte]

Um vértice que não é uma extremidade de uma aresta em algum acoplamento parcial  é chamado de vértice livre. O conceito básico do algoritmo baseia-se em que cada caminho extensor, um caminho que começa em um vértice livre, termina em um vértice livre, e alterna entre arestas acopladas e não-acopladas dentro do caminho. Note que, exceto para os pontos da extremidade, todos os outros vértices (se houver) no caminho extensor devem ser vértices não-livres. Um caminho extensor poderia consistir em apenas dois vértices (ambos vértices livres) e uma única aresta não-acoplada entre elas. 

Se  é um acoplamento, e  é um caminho extensor relativo a , então a diferença simétrica dos dois conjuntos de arestas, , formaria um acoplamento de tamanho . Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.

Por outro lado, suponha que um acoplamento  não é ótimo, e seja  a diferença simétrica onde  é um acoplamento ótimo. Pelo fato de  e  serem ambos acoplamentos, cada vértice tem grau no máximo 2 em . Então  deve formar uma coleção de caminhos extensores disjuntos e ciclos ou caminhos em que arestas acopladas e não acopladas são de igual número; a diferença de tamanho entre  e  é o número de caminhos extensores em . Assim, se nenhum caminho extensor for encontrado, um algoritmo pode terminar com segurança, já que neste caso  deve ser ótimo.

Um caminho extensor em um problema de acoplamento está intimamente relacionado com o surgimento de problemas do fluxo máximo, caminhos ao longo do qual se pode aumentar a quantidade de fluxo entre os terminais do fluxo. É possível transformar o problema do acoplamento bipartido em uma instância máxima de fluxo, tal que os caminhos alternados do problema do acoplamento se tornam caminhos extensores do problema do fluxo.[1] De fato, uma generalização da técnica usada pelo algoritmo de Hopcroft–Karp para um fluxo arbitrário de redes é conhecido como algoritmo de Dinic.

Entrada: Grafo bipartido 
Saída: Acoplamento 
repita
 conjunto máximo de vértices disjuntos de caminhos extensores mais curtos
até

Algoritmo[editar | editar código-fonte]

Sejam  e  dois conjuntos da bipartição de , e considere o acoplamento de   para  a qualquer tempo sendo representado como um conjunto .

O algoritmo é executado em fases. Cada fase consiste nos seguintes passos.

  • Uma busca em largura particiona os vértices do grafo em camadas. Os vértices livres em  são usados como sendo os vértices iniciais dessa busca e formando a primeira camada dessa partição. No primeiro nível da busca, existem apenas arestas não acopladas, desde que vértices livres em  são por definição não adjacentes a nenhuma aresta não acoplada. Em níveis subsequentes da busca, as arestas que cruzam são obrigados a alternar entre acopladas e não acopladas. Ou seja, na busca de sucessores de um vértice em , somente arestas não acopladas podem ser cruzadas, enquanto a partir de um vértice em  somente arestas acopladas podem ser cruzadas. A busca termina na primeira camada  onde um ou mais vértices livres em  são alcançados.
  • Todos os vértices livres em   na camada  são reunidas em um conjunto . Ou seja, um vértice  é colocado em  se e somente se ele termina um caminho extensor mais curto.
  • O algoritmo acha um conjunto máximo de vértices disjuntos de caminhos extensores de tamanho . Este conjunto pode ser computado por uma busca em profundidade de  para os vértices livres em , usando a camada da busca em largura para guiar a busca: a profundidade da busca somente é permitida para seguir as arestas que levam para um vértice não utilizado na camada anterior, e os caminhos da árvore da busca em profundidade devem alternar entre arestas acopladas e não acopladas. Uma vez que um caminho extensor que envolva um dos vértices em , a busca em profundidade é continuada a partir do próximo vértice de início.
  • Cada um dos caminhos encontrados desta forma é utilizado para ampliar .

O algoritmo termina quando não há mais caminhos extensores a serem encontrados em uma das fases da busca em largura.

Análise[editar | editar código-fonte]

Cada fase consiste em uma única busca em largura e uma única busca em profundidade. Assim, uma única fase pode ser implementada em tempo linear. No entanto, as primeiras  fases, em um grafo com  vértices e arestas, levam um tempo .

Pode ser demonstrado que cada fase aumenta o tamanho do caminho extensor mais curto no mínimo em um: a fase encontra um conjunto máximo de caminhos extensores dado um comprimento, portanto, qualquer caminho extensor restante deve ser maior. Assim, uma vez que  fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo  arestas. No entanto, a diferença simétrica de um eventual acoplamento ótimo e de um acoplamento parcial M encontrado pelas fases iniciais formam uma coleção de vértices disjuntos de caminhos extensores e ciclos alternados. Se cada um dos caminhos nesta coleção tem comprimento de pelo menos , pode haver no máximo caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de  por no máximo arestas. Uma vez que cada fase do algoritmo aumenta o tamanho do acoplamento por pelo menos um, pode haver no máximo  fases adicionais antes do algoritmo terminar.

Uma vez que o algoritmo executa um total de, no máximo fases, é preciso um tempo total de no pior caso.

Em muitos casos, no entanto, o tempo gasto pelo algoritmo pode ser ainda mais rápido do que a análise de pior caso indica. Por exemplo, no caso médio para grafos esparsos aleatórios , Bast et al. (2006) (melhorando o resultado anterior de Motwani 1994) mostrou com grande probabilidade que todos os acoplamentos não ótimos possuem caminhos extensores de tamanho logaritmo. Como consequência, para esses grafos, o algoritmo de Hopcroft–Karp leva  fases e um tempo total de .

Comparação com outros algoritmos de correspondência bipartida[editar | editar código-fonte]

Para grafos esparsos o algoritmo de Hopcroft–Karp continua a ter a melhor performance conhecida no pior caso, no entanto para grafos densos um algoritmo mais recente por Alt et al. (1991) alcança um limitante de tempo um pouco melhor , . Este algoritmo é baseado no uso de um algoritmo de fluxo máximo de push-relabel e, em seguida, quando um acoplamento for criado por este algoritmo, este torna-se perto de ótimo, alternando para o método de Hopcroft–Karp.

Vários autores têm realizado comparações experimentais em algoritmos de acoplamento bipartido. Esses resultados em geral tendem a mostrar que o método de Hopcroft–Karp não é tão bom na prática quanto na teoria: ele é superado por uma simples busca em largura e estratégias de busca em profundidade para encontrar caminhos extensores, e pelas técnicas de push-relabel.[2]

Grafos não bipartidos[editar | editar código-fonte]

A mesma ideia de achar um conjunto máximo de caminhos extensores mais curtos funciona também para achar acoplamentos de cardinalidade máxima em grafos não bipartidos, e pelas mesmas razões dos algoritmos baseados nessa mesma ideia levam  fases. No entanto, para grafos não bipartidos, a tarefa de achar um caminho extensor em cada fase é mais difícil. Com base no trabalho de vários predecessores mais lentos, Micali & Vazirani (1980) mostraram como implementar uma fase em tempo linear, resultado em um algoritmo de acoplamento não bipartido com o mesmo limitante de tempo do que o algoritmo de Hopcroft–Karp para grafos bipartidos. A técnica de Micali–Vazirani é complexa, e seus autores não forneceram provas completas de seus resultados; posteriormente, a "explicação clara" foi publicado por Peterson & Loui (1988) e métodos alternativos foram descritos por outros autores.[3] Em 2012, Vazirani ofereceu uma nova prova simplificada do algoritmo de Micali-Vazirani.[4]

Pseudocódigo[editar | editar código-fonte]

/* 
 G = U ∪ V ∪ {NIL}
 onde U e V são partições do grafo e NIL é um vértice especial nulo
*/
  
função BFS ()
    para u em U
        se Pair_U[u] == NIL
            Dist[u] = 0
            Enqueue(Q,u)
        senão
            Dist[u] = ∞
    Dist[NIL] = ∞
    enquanto Empty(Q) == falso
        u = Dequeue(Q)
        se Dist[u] < Dist[NIL] 
            para cada v em Adj[u]
                se Dist[ Pair_V[v] ] == ∞
                    Dist[ Pair_V[v] ] = Dist[u] + 1
                    Enqueue(Q,Pair_V[v])
    retorne Dist[NIL] != ∞

função DFS (u)
    se u != NIL
        para cada v em Adj[u]
            se Dist[ Pair_V[v] ] == Dist[u] + 1
                se DFS(Pair_V[v]) == verdadeiro
                    Pair_V[v] = u
                    Pair_U[u] = v
                    retorne verdadeiro
        Dist[u] = ∞
        retorne falso
    retorne verdadeiro

função Hopcroft-Karp
    para cada u em U
        Pair_U[u] = NIL
    para cada v em V
        Pair_V[v] = NIL
    matching = 0
    enquanto BFS() == verdadeiro
        para cada u em U
            se Pair_U[u] == NIL
                se DFS(u) == verdadeiro
                    matching = matching + 1
    retorne matching
Execução em um exemplo gráfico que mostra o grafo de entrada e a correspondência após a iteração intermediária 1 e a iteração final 2.

Explicação[editar | editar código-fonte]

Considere que o nosso grafo tenha duas partições . A ideia chave é adicionar dois vértices postiços em cada lado no grafo: se conecta a todos os vértices não marcados em e se conecta a todos os vértices não marcados em . Agora se executarmos uma busca em largura a partir de para então podemos obter o caminho mais curto entre um vértice não acoplado em para um vértice não acoplado em . Devido à natureza do grafo bipartido, este caminho seria um zig zag de para . No entanto, precisamos ter certeza de que quando se passa de para , nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em  . Se nós temos certeza destes critérios durante uma busca em largura então o caminho gerado irá reunir os requisitos para ser um caminho extensor mais curto.

Uma vez que tenhamos encontrado o caminho extensor mais curto, queremos ter certeza de que ignorar quaisquer outros caminhos que são maiores do que caminhos mais curtos. O algoritmo de busca em largura marca os nós em um caminho com a distância da fonte como sendo 0. Assim, depois de realizar uma busca em largura, podemos começar a partir de cada vértice não acoplado em , seguir o caminho percorrendo os nós incrementando a distância por 1. Quando finalmente chegarmos ao destino , se a sua distância é maior em 1 do que o último nó em então sabemos que o caminho que percorremos (uma dentre várias possibilidades)  é o caminho mais curto. Nesse caso, podemos ir em frente e atualizar os pares de vértices nos caminhos de e . Note que cada vértice em sobre um caminho, exceto pelo último, não é um vértice livre. Então, atualizando os pares destes vértices em para diferentes vértices em é equivalente a remover previamente uma aresta correspondente e adicionar uma nova aresta não acoplada em uma acoplada. Isto é o mesmo que fazer a diferença simétrica (i.e. remover arestas em comum a acoplamentos anteriores e adicionar arestas que não estão em comum no caminho extensor em novo acoplamento).

Como podemos ter certeza de que caminhos extensores são vértices disjuntos? Isto já é garantido: Depois de fazer a diferença simétrica para um caminho, nenhum dos seus vértices poderia ser considerado novamente apenas porque o Dist[ Pair_V[v] ] não vai ser igual a Dist[u] + 1 (seria exatamente Dist[u]).

Então, qual é a missão destas duas linhas em pseudocódigo?:

Dist[u] = ∞ retorne falso

Quando não formos capazes de encontrar qualquer caminho extensor menor a partir de um vértice, a busca em profundidade retorna falso. Neste caso, seria bom para marcar esses vértices para não visitá-los novamente. Essa marcação é simplesmente feita configurando Dist[u] como sendo igual a infinito.

Finalmente, nós realmente não precisamos de pois ele está lá apenas para colocar todos os vértices não acoplados de em uma fila quando a busca em largura começa. Que podemos fazer apenas como uma inicialização. O pode ser anexado em por conveniência em muitas implementações e inicializar o acoplamento padrão para todo apontar para . Dessa forma, se o vértice final em não tem qualquer vértice correspondente em , em seguida, finalmente terminamos em que é o final do nosso caminho extensor. No pseudocódigo acima  é denotado como sendo Nil.

Veja também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

Referências[editar | editar código-fonte]