Geralmente, chamamos um algoritmo de "bom algoritmo" se o tempo de execução for polinomial no pior dos casos. Mas em alguns casos (por exemplo, algoritmo Simplex), mesmo que o pior caso do algoritmo seja exponencial, ele poderia funcionar muito bem na prática.
Existem exemplos (determinísticos) nessa situação além do algoritmo Simplex?
ds.algorithms
Arman
fonte
fonte
Respostas:
Os algoritmos modernos de solução de SAT são capazes de resolver a maioria das instâncias com bastante rapidez, mesmo que o pior caso de execução seja, obviamente, exponencial. Nesse caso, no entanto, a velocidade prática é mais o resultado de anos de engenharia de algoritmos, do que a de um único algoritmo elegante. Embora eu tenha entendido que o aprendizado de cláusulas orientadas a conflitos causou um grande salto no desempenho dos solucionadores de SAT, as melhorias posteriores são muitas vezes obtidas com o uso inteligente de várias heurísticas nos algoritmos.
fonte
O algoritmo -eans para clustering é comprovadamente exponencial, mesmo no plano, mas funciona muito bem na prática.k
fonte
A inferência do tipo Hindley-Milner é EXPTIME-complete, mas nos programas que as pessoas normalmente escrevem é bastante próxima do linear.
fonte
let z = (let y = e in e') in e''em vez delet y = e in let z = e' in e''.O programa de nauty de Brendan McKay (No AUTomorphisms, Yes?) Resolve o problema de rotulagem canônica de gráficos (resolvendo simultaneamente os problemas de Isomorfismo em Gráfico e Automorfismo em Gráfico) e tem desempenho exponencial no pior dos casos (Miyazaki, 1996). No entanto, ele funciona muito rapidamente para a maioria dos gráficos, especialmente aqueles com poucos automorfismos.
Especificamente, o algoritmo começa particionando os vértices por grau, depois pelo grau entre cada parte. Quando esse processo se estabiliza, é preciso fazer uma escolha para distinguir um vértice em uma parte não trivial, e isso leva ao comportamento exponencial. Na maioria dos gráficos, a profundidade desse procedimento de ramificação é pequena.
fonte
Vários algoritmos para jogos estocásticos simples funcionam bem na prática, apesar de terem tempos de execução exponenciais no pior dos casos. Obviamente, esse problema está, em certo sentido, relacionado à programação linear, embora não se saiba que esteja em tempo polinomial.
fonte
Existe um algoritmo para encontrar equilíbrios mistos de Nash que é semelhante ao algoritmo simplex para LPs. (Eu esqueço o nome.) Ele tem uma complexidade exponencial de pior caso, mas tenho uma vaga memória de que muitas vezes se comporta bem na prática.
fonte
A embalagem do compartimento (muitas variantes) é um problema cuja complexidade é conhecida como NP-hard:
http://en.wikipedia.org/wiki/Bin_packing_problem
No entanto, muitas heurísticas, quando aplicadas a versões "práticas", se dão muito bem. Para caixas unidimensionais que embalam algumas dessas heurísticas, como primeiro ajuste; primeiro ajuste decrescente; melhor ajuste; A redução do melhor ajuste é muito atraente como tópicos para mostrar aos alunos. Os alunos geralmente podem descobrir algumas das heurísticas básicas por si mesmos.
fonte
O algoritmo de persistência (originário de Edelsbrunner-Letscher-Zomorodian, com muitas variações desde então) é o pior caso cúbico, mas parece que a experimentação geralmente é executada em tempo linear.
fonte