Algum dos algoritmos de fluxo máximo de última geração é prático?

30

Para o problema de vazão máxima , parece haver um número de algoritmos muito sofisticados, com pelo menos um desenvolvido recentemente no ano passado. O fluxo máximo de Orlin no tempo O (mn) ou melhor fornece um algoritmo que roda em O (VE).

Por outro lado, os algoritmos que eu normalmente vejo implementados são (não pretendo ter feito uma pesquisa exaustiva; isso é apenas por observação casual):

  • Edmonds-Karp: ,O(VE2)
  • Re-rotular push: ou O ( V 3 ) usando a seleção de vértice FIFO,O(V2E)O(V3)
  • Algoritmo de Dinic: .O(V2E)

Os algoritmos com melhor tempo de execução assintótico não são práticos para os tamanhos de problemas no mundo real? Além disso, vejo que "Árvores dinâmicas" estão envolvidas em alguns algoritmos; estes são usados ​​na prática?

Nota: esta pergunta foi originalmente feita no estouro de pilha aqui , mas me disseram que seria um ajuste melhor aqui.

EDIT : Fiz uma pergunta relacionada no cs.stackexchange , especificamente sobre os algoritmos que usam árvores dinâmicas (também conhecidas como árvores cortadas por link), que podem ser de interesse para as pessoas que seguem esta pergunta.

ds.algorithms graph-algorithms application-of-theory max-flow Rob Lachlan
fonte
11
falando de um modo geral, se um algoritmo é "prático" versus se é "implementado" é um pouco diferente. idealmente, os autores lançariam implementações de seus próprios algoritmos, caso em que normalmente seria "prático" usá-los. se isso é mais uma exceção na literatura da TCS. mas muitas vezes não é "prático" implementar "algoritmos" de outros autores apenas com descrições em documentos escritos em pseudocódigo, que às vezes são significativamente ou altamente complexos ... a implementação bem-sucedida inclui um bom teste de correção, um processo às vezes assustador ...
vzn
3
Andrew Goldberg costumava ter uma boa base de código para diferentes variantes do fluxo máximo, com base em seu trabalho de re-envio de push. Eu usei o código no passado e era muito limpo. Infelizmente, o site parece estar desativado.
Suresh Venkat
3
@vzn Estou interessado em saber se os algoritmos se prestam à implementação prática. Existem algoritmos que não o fazem, e algumas pessoas começaram a chamar esses "algoritmos galácticos", porque eles têm um excelente comportamento assintótico, mas com tanta sobrecarga que atualmente não há nenhum ganho prático para implementá-los. (Afinal, os termos de ordem inferior são importantes.) A multiplicação de matrizes é o melhor exemplo em que consigo pensar, onde as melhores soluções assintoticamente nunca veem uso prático. Estou curioso para saber se o fluxo máximo é uma situação semelhante.
precisa
5
se um algoritmo é "prático" ou se é "implementado" é um pouco diferente. - Está correto. Um algoritmo pode ser implementado sem ser prático, mas não vice-versa.
Jeffε
2
Aqui está o código do estudo experimental de algoritmos de corte mínimo .
Austin Buchanan

Respostas:

22

Eu sou um dos autores do artigo acima.

Só quero mencionar que usamos `` estado da arte '' para significar algoritmos (com implementações disponíveis ao público) que apresentam bom desempenho em instâncias de fluxo máximo que surgem na visão por computador.

Eu também gostaria de acrescentar que, dentro desse contexto restrito (mas prático), geralmente os algoritmos com bom desempenho são aqueles com más garantias teóricas. Por exemplo, ref [5] do nosso artigo (algoritmo de Boykov-Kolmogorov) é amplamente utilizado na comunidade de visão computacional, mas não possui um limite de tempo de execução fortemente polimejado.

Finalmente, caso alguém esteja interessado, os dados de nossas experiências estão disponíveis aqui: http://ttic.uchicago.edu/~dbatra/research/mfcomp/index.html

O código também estará disponível em breve também.

Dhruv Batra
fonte
muito legal que você se juntou ao grupo! bem vinda! uma pergunta sobre o artigo [desde a primeira vez que o encontrei]. seria muito interessante ouvir mais sobre o processo de seleção de algoritmos usados ​​no artigo - não parecia elaborar completamente isso. talvez você possa compartilhar algumas notas de bastidores "nos bastidores" em algum lugar [por exemplo, página da web?] sobre quais algoritmos foram selecionados, quais foram omitidos, por que, quais desafios havia na obtenção / execução de implementações, o que você acha mais exótico algoritmos como o Orlins recente e suas perspectivas de eventual implementação, etc.
vzn
7

existem várias maneiras de responder a essa pergunta, mas não necessariamente uma resposta de consenso. geralmente algoritmos que foram implementados e liberados para distribuição pública são "práticos". no entanto, alguns algoritmos que foram criados, mas ainda não foram implementados, podem ser práticos, mas "o júri está fora" deles, por assim dizer. **

uma boa estratégia para fins práticos é procurar uma pesquisa. também para os interessados ​​em algoritmos práticos, os benchmarks em relação aos dados do mundo real podem ser uma excelente diretriz quanto ao comportamento esperado do "mundo real".

uma pesquisa de benchmarking pode ser suficiente, mas irá errar ao lado de algoritmos viáveis. é uma análise empírica recente e completa de 14 algoritmos de fluxo máximo "avançados" comparados empiricamente em relação a instâncias de processamento de visão, em que o fluxo máximo tem muitas aplicações. "estado da arte" é utilizado para se referir a algoritmos "implementados".

[1] MaxFlow Revisited: Uma comparação empírica dos algoritmos Maxflow para problemas de visão densa por Verma e Batra, 2012

** alguns algoritmos teóricos estão cada vez mais em uma categoria na comunidade do TCS, sendo informalmente referidos como "galácticos", mas infelizmente, os autores do TCS atualmente não rotulam seus algoritmos nesta categoria e não há critérios publicados ou geralmente aceitos para algoritmos "galácticos", embora exista referência em blogs .

a praticidade nesse sentido é possivelmente uma nova dimensão emergente para o estudo teórico. idealmente, haveria uma pesquisa de algoritmos de fluxo máximo especificamente sobre esse eixo / critério "prático", mas provavelmente isso não existe até o momento da escrita. é um conceito mais recentemente reconhecido / reconhecido no TCS que ainda não foi completamente formalizado (ao contrário de, por exemplo, a ampla aceitação dos algoritmos P como "eficientes").

vzn
fonte
3
+1. Não sei por que isso foi rebaixado; Estou lendo o artigo ao qual você vinculou e foi muito útil analisar quais são as abordagens práticas, pelo menos nesse domínio do problema.
precisa
3
Robert Sedgewick disse em uma conversa bastante recente que o criador do algoritmo que não realiza experimentos corre o risco de se perder na abstração. A conversa é sobre encontrar caminhos nos gráficos e também está um pouco relacionada ao maxflow. Não responde à pergunta, mas pode ser interessante para alguém.
Juho
5
@ Rob, a única parte relevante nesta resposta é um link para o artigo e não há muito na resposta que explique por que esse artigo está vinculado. Eu acho que o OP encontrou o link pelo Google e não o leu. O restante da resposta são algumas observações e comentários gerais que afirmam a perspectiva pessoal do OP sobre questões nas quais ele não é especialista e não é realmente relevante aqui. Respostas não são postagens de blog. Um link para um artigo relevante pode ser bom como um comentário, mas não dá uma resposta. Esta é uma resposta ruim se for uma. É por isso que votei contra.
Kaveh
2
@ Kaveh justo o suficiente. Achei o artigo um indicador útil do que as pessoas consideram algoritmos praticamente úteis. Concordo que muito resta sem resposta.
precisa
3
Também não entendo os votos negativos. Não há razão para acreditar que o pôster NÃO leu o artigo vinculado e parece relevante. Eu posso ver o desejo de não votar, mas não um voto negativo.
Suresh Venkat