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.
Respostas:
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
fonte
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.
fonte