Algoritmo de Hopcroft–Karp

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 $O (| E | \sqrt{| V |})$ no pior caso, onde $E$ é o conjunto de arestas do grafo, e $V$ é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se $O (| V |^{2.5})$ e para grafos aleatórios ele é executado em tempo quase linear.

O algoritmo foi encontrado por Predefinição:Harvard citations. Como nos métodos anteriores para acoplamento, tais como o algoritmo húngaro e o trabalho de Predefinição:Harvtxt, 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 $O (\sqrt{n})$ 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

Um vértice que não é uma extremidade de uma aresta em algum acoplamento parcial $M$ é 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 $M$ é um acoplamento, e $P$ é um caminho extensor relativo a $M$ , então a diferença simétrica dos dois conjuntos de arestas, $M \oplus P$ , formaria um acoplamento de tamanho $| M | + 1$ . Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.

Por outro lado, suponha que um acoplamento $M$ não é ótimo, e seja $P$ a diferença simétrica $M \oplus M^{*}$ onde $M^{*}$ é um acoplamento ótimo. Pelo fato de $M$ e $M^{*}$ serem ambos acoplamentos, cada vértice tem grau no máximo 2 em $P$ . Então $P$ 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 $M$ e $M^{*}$ é o número de caminhos extensores em $P$ . Assim, se nenhum caminho extensor for encontrado, um algoritmo pode terminar com segurança, já que neste caso $M$ 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

G (U \cup V, E)

Saída: Acoplamento

M \subseteq E

M \leftarrow \emptyset

repita

𝒫 \leftarrow {P_{1}, P_{2}, \dots, P_{k}}

conjunto máximo de vértices disjuntos de caminhos extensores mais curtos

M \leftarrow M \oplus (P_{1} \cup P_{2} \cup \dots \cup P_{k})

até

𝒫 = \emptyset

Algoritmo

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

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 $U$ 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 $U$ 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 $U$ , somente arestas não acopladas podem ser cruzadas, enquanto a partir de um vértice em $V$ somente arestas acopladas podem ser cruzadas. A busca termina na primeira camada $k$ onde um ou mais vértices livres em $V$ são alcançados.
Todos os vértices livres em $V$ na camada $k$ são reunidas em um conjunto $F$ . Ou seja, um vértice $v$ é colocado em $F$ 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 $k$ . Este conjunto pode ser computado por uma busca em profundidade de $F$ para os vértices livres em $U$ , 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 $F$ , 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 $M$ .

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

Análise

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 $\sqrt{| V |}$ fases, em um grafo com $| V |$ vértices e $| E |$ arestas, levam um tempo $O (| E | \sqrt{| V |})$ .

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 $\sqrt{| V |}$ fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo $\sqrt{| V |}$ 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 $\sqrt{| V |}$ , pode haver no máximo $\sqrt{| V |}$ caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de $M$ por no máximo $\sqrt{| V |}$ arestas. Uma vez que cada fase do algoritmo aumenta o tamanho do acoplamento por pelo menos um, pode haver no máximo $\sqrt{| V |}$ fases adicionais antes do algoritmo terminar.

Uma vez que o algoritmo executa um total de, no máximo $2 \sqrt{| V |}$ fases, é preciso um tempo total de $O (| E | \sqrt{| V |})$ 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 , Predefinição:Harvtxt (melhorando o resultado anterior de Predefinição:Harvnb) 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 $O (\log | V |)$ fases e um tempo total de $O (| E | \log | V |)$ .

Comparação com outros algoritmos de correspondência bipartida

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 Predefinição:Harvtxt alcança um limitante de tempo um pouco melhor , $O (n^{1.5} \sqrt{\frac{m}{\log n}})$ . 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

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 $O (\sqrt{| V |})$ 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, Predefinição:Harvtxt 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 Predefinição:Harvtxt 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

/* 
 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

Considere que o nosso grafo tenha duas partições $U, V$ . A ideia chave é adicionar dois vértices postiços em cada lado no grafo: $u D u m m y$ se conecta a todos os vértices não marcados em $U$ e $v D u m m y$ se conecta a todos os vértices não marcados em $V$ . Agora se executarmos uma busca em largura a partir de $u D u m m y$ para $v D u m m y$ então podemos obter o caminho mais curto entre um vértice não acoplado em $U$ para um vértice não acoplado em $V$ . Devido à natureza do grafo bipartido, este caminho seria um zig zag de $U$ para $V$ . No entanto, precisamos ter certeza de que quando se passa de $V$ para $U$ , nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em $v D u m m y$ . 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 $U$ , seguir o caminho percorrendo os nós incrementando a distância por 1. Quando finalmente chegarmos ao destino $v D u m m y$ , se a sua distância é maior em 1 do que o último nó em $V$ 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 $U$ e $V$ . Note que cada vértice em $V$ sobre um caminho, exceto pelo último, não é um vértice livre. Então, atualizando os pares destes vértices em $V$ para diferentes vértices em $U$ é 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 $u D u m m y$ pois ele está lá apenas para colocar todos os vértices não acoplados de $U$ em uma fila quando a busca em largura começa. Que podemos fazer apenas como uma inicialização. O $v D u m m y$ pode ser anexado em $U$ por conveniência em muitas implementações e inicializar o acoplamento padrão para todo $V$ apontar para $v D u m m y$ . Dessa forma, se o vértice final em $V$ não tem qualquer vértice correspondente em $U$ , em seguida, finalmente terminamos em $v D u m m y$ que é o final do nosso caminho extensor. No pseudocódigo acima $v D u m m y$ é denotado como sendo Nil.

Veja também

Acoplamento (teoria dos grafos)
Hungarian algorithm
Assignment problem

Notas

Predefinição:Reflist

Referências

Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation. As cited by Predefinição:Harvtxt.
Predefinição:Citation. As cited by Predefinição:Harvtxt.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation.
Predefinição:Citation. As cited by Predefinição:Harvtxt.
Predefinição:Citation.
Predefinição:Citation.

↑ Predefinição:Harvtxt, section 12.3, bipartite cardinality matching problem, pp. 469–470.
↑ Predefinição:Harvtxt; Predefinição:Harvtxt; Predefinição:Harvtxt; Predefinição:Harvtxt.
↑ Predefinição:Harvtxt and Predefinição:Harvtxt.
↑ Predefinição:Harvtxt

[1] Predefinição:Harvtxt, section 12.3, bipartite cardinality matching problem, pp. 469–470.

[2] Predefinição:Harvtxt; Predefinição:Harvtxt; Predefinição:Harvtxt; Predefinição:Harvtxt.

[3] Predefinição:Harvtxt and Predefinição:Harvtxt.

[4] Predefinição:Harvtxt

[1]

[2]

[3]

[4]

Algoritmo de Hopcroft–Karp

Índice

Caminhos Extensores

Algoritmo

Análise

Comparação com outros algoritmos de correspondência bipartida

Grafos não bipartidos

Pseudocódigo

Explicação

Veja também

Notas

Referências

Menu de navegação

Algoritmo de Hopcroft–Karp

Caminhos Extensores

Algoritmo

Análise

Comparação com outros algoritmos de correspondência bipartida

Grafos não bipartidos

Pseudocódigo

Explicação

Veja também

Notas

Referências

Menu de navegação

Pesquisa