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 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
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
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
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
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
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
/* 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
Explicação
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
- Acoplamento (teoria dos grafos)
- Hungarian algorithm
- Assignment problem
Notas
- ↑ Ahuja, Magnanti & Orlin (1993), section 12.3, bipartite cardinality matching problem, pp. 469–470.
- ↑ Chang & McCormick (1990); Darby-Dowman (1980); Setubal (1993); Setubal (1996).
- ↑ Gabow & Tarjan (1991) and Blum (2001).
- ↑ Vazirani (2012)
Referências
- Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall .
- Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M. (1991), «Computing a maximum cardinality matching in a bipartite graph in time », Information Processing Letters, 37 (4): 237–240, doi:10.1016/0020-0190(91)90195-N .
- Bast, Holger; Mehlhorn, Kurt; Schafer, Guido; Tamaki, Hisao (2006), «Matching algorithms are fast in sparse random graphs», Theory of Computing Systems, 39 (1): 3–14, doi:10.1007/s00224-005-1254-y .
- Blum, Norbert (2001), A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs, Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn .
- Chang, S. Frank; McCormick, S. Thomas (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia . As cited by Setubal (1996).
- Darby-Dowman, Kenneth (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University . As cited by Setubal (1996).
- Edmonds, Jack (1965), «Paths, Trees and Flowers», Canadian J. Math, 17: 449–467, MR 0177907, doi:10.4153/CJM-1965-045-4 .
- Gabow, Harold N.; Tarjan, Robert E. (1991), «Faster scaling algorithms for general graph matching problems», Journal of the ACM, 38 (4): 815–853, doi:10.1145/115234.115366 .
- Hopcroft, John E.; Karp, Richard M. (1973), «An n5/2 algorithm for maximum matchings in bipartite graphs», SIAM Journal on Computing, 2 (4): 225–231, doi:10.1137/0202019 .
- Micali, S.; Vazirani, V. V. (1980), «An algorithm for finding maximum matching in general graphs», Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12 .
- Peterson, Paul A.; Loui, Michael C. (1988), «The general maximum matching algorithm of Micali and Vazirani», Algorithmica, 3 (1-4): 511–533, doi:10.1007/BF01762129 .
- Motwani, Rajeev (1994), «Average-case analysis of algorithms for matchings and related problems», Journal of the ACM, 41 (6): 1329–1356, doi:10.1145/195613.195663 .
- Setubal, João C. (1993), «New experimental results for bipartite matching», Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, pp. 211–216 . As cited by Setubal (1996).
- Setubal, João C. (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas .
- Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm, CoRR abs/1210.4594 .