Generalização do algoritmo húngaro em gráficos gerais não direcionados?

14

O algoritmo húngaro é um algoritmo de otimização combinatória que resolve o problema de correspondência bipartida de peso máximo em tempo polinomial e antecipou o desenvolvimento posterior do importante método primal-duplo . O algoritmo foi desenvolvido e publicado por Harold Kuhn em 1955, que deu o nome "algoritmo húngaro" porque o algoritmo foi baseado nos trabalhos anteriores de dois matemáticos húngaros: Dénes Kőnig e Jenő Egerváry. Munkres revisou o algoritmo em 1957 e observou que é realmente polytime. Desde então, o algoritmo também é conhecido como algoritmo de Kuhn-Munkres.

Embora o húngaro contenha a idéia básica do método primal-dual, ele resolve o problema de correspondência bipartida de peso máximo diretamente, sem usar nenhuma máquina de programação linear (LP). Assim, em resposta à seguinte pergunta , Jukka Suomela comentou

É claro que você pode resolver qualquer LP usando um solucionador de LP de uso geral, mas algoritmos especializados geralmente têm um desempenho muito melhor. [...] Você também pode evitar problemas como usar números racionais exatos vs. números de ponto flutuante; tudo pode ser feito facilmente com números inteiros.

Em outras palavras, você não precisa se preocupar em como arredondar uma solução de ponto flutuante / racional do solucionador de LP para obter uma correspondência perfeita de peso máximo de um determinado gráfico bipartido.

Minha pergunta é a seguinte:

Existe uma generalização do algoritmo húngaro que funcione para grafos gerais não direcionados sem o uso de máquinas LP semelhante ao espírito do algoritmo húngaro original?

Eu preferiria uma exposição moderna e fácil de ler em vez de um papel complicado original. Mas qualquer ponteiro será muito apreciado!

Muito obrigado antecipadamente e Feliz Natal !!!


Atualização: A pergunta é bem respondida por Arman abaixo. Quero apenas salientar que outra boa fonte para estudar o algoritmo de flor de Edmonds (para o caso ponderado) é o capítulo 11 da otimização combinatória da Korte e da Vygen . O livro do Google, na verdade, mostra quase todas as partes necessárias para entender o algoritmo.

Dai Le
fonte
2
E o algoritmo de correspondência de Edmonds? en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
Arman
1
@Arman - Era o que eu estava pensando também. Obrigado pelo link, a Wikipedia apresenta uma exposição surpreendentemente detalhada do algoritmo de flores de Edmond.
Abraham Flaxman
2
A propósito, o algoritmo de correspondência de Edmonds também é baseado no método Primal-Dual.
Arman
1
Obrigado Arman. O link da wikipedia também aponta para o livro "Lovász, László; Plummer, Michael (1986). Matching Theory" para a versão ponderada do algoritmo de Edmonds. Eu realmente deveria conferir esse livro. Muito obrigado pelos seus comentários! Talvez se algum de vocês puder explicar em alto nível como o algoritmo generaliza o algoritmo húngaro, você pode definitivamente fazer uma resposta.
Dai Le
1
Eu acho que é uma resposta muito boa como é :). Arman, você deve adicioná-lo assim
Suresh Venkat

Respostas:

16

O algoritmo de correspondência de Edmonds (também chamado de algoritmo de flor) resolve a correspondência máxima nos gráficos gerais. Na verdade, é uma generalização do método de caminhos alternados. (Não tenho certeza do nome do método, mas deve ser o método König-Hall.) Ele basicamente encontra caminhos aumentados (consulte a página da wikipedia: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ) para estender o correspondência atual e para se não houver mais caminhos de aumento. Em gráficos gerais, o único problema ocorre em ciclos ímpares. No algoritmo de correspondência de Edmonds, ciclos ímpares são contratados (flores) e gastos de volta para ter uma solução.

Existe também uma correspondência entre o algoritmo Blossom e o método Primal Dual. Ciclos ímpares causam pontos extremos fracionários. Portanto, adicionamos as chamadas desigualdades de flor para cada ciclo ímpar.

Problemas mínimos de correspondência perfeita ponderada e de correspondência de peso máximo também podem ser tratados com essa abordagem.

Para detalhes do algoritmo, consulte http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

Para formulação matemática e o método primal-dual correspondente, consulte http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf

Arman
fonte
9

Dois anos atrás, ao pesquisar o algoritmo de flor (não ponderado), encontrei dois grandes conjuntos de notas, uma de Tarjan e outra de Zwick. Eles fizeram o caso não ponderado parecer bastante direto e eu pude implementá-lo no Mathematica usando recursão. Funciona muito bem.

As notas que achei úteis são

http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf e http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf

Eles destilam tudo em termos muito simples que permitem pensar recursivamente e depois, como observado, programar recursivamente.

Eu acho que tudo deve funcionar no caso ponderado, que eu estou tentando implementar agora.

Stan Wagon
fonte
E eu tenho demos que podem ser assistidos por qualquer pessoa com o software livre: O primeiro mostra florescer muito bem ... < demonstrations.wolfram.com/… > < demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm > < demonstrations.wolfram.com/ PlacingDominoesOnACheckerboard >
Stan Wagon
E acabei de programar a flor não ponderada, conforme indicado no Korte / Vygen. Vejo que algumas acelerações são possíveis para seu código (por exemplo, comece com uma correspondência máxima, em vez de nada), mas o bom é que seu código de procedimento é fornecido de uma forma que pode ser facilmente traduzida em código de trabalho. A seguir: flor ponderada, que é muito mais difícil.
Stan Wagon