O algoritmo predileto do Knuth
Meu repositórios oldies tem muitas das coisas que já programei, mas não tem tudo. Uma boa parte está perdida por aí em backups e hard prints. Semana passada eu recuperei um pacotinho que tinha uma lib legal que fiz em 2011, e a história dela começa com o Knuth.
A única vez que vi o Knuth ao vivo foi em 2011. Na ocasião, perguntaram qual o algoritmo predileto dele, e ele disse que era o BDD (binary decision diagram), porque ele tinha acabado de publicar um livro sobre isso e o algoritmo que você mais gosta, em geral, tende a ser que o você acabou de aprender. Bom, se era o preferido do Knuth tinha que ser divertido, eu não podia deixar de implementar né?
O BDD é uma estrutura de dados que serve para guardar uma fórmula booleana em memória, de maneira otimizada. Lembra um pouco o mapa de Karnaugh, mas escala muito melhor, Karnaugh você não faz com mais 3 variáveis, BDD você chega em centenas fácil.
Intuitivamente você espera que guardar toda a fórmula em memória ocupe espaço exponencial (2^número de variáveis). E é isso mesmo! PORÉM, esse é o valor esperado para fórmulas aleatórias. As fórmulas da vida real costumam ter estrutura, e essa estrutura aparece magicamente quando você monta uma BDD. Na prática elas são bem melhores que o exponencial.
A BDD tem várias utilidades, mas eu suspeito que o Knuth gosta delas porque são ótimas para resolver puzzles! No livro Selected Papers on Fun And Games, o Knuth usa uma BDD para resolver o Slitherlink. Na minha implementação, eu usei para resolver o Torto Reverso. A figura mostra o BDD montado para uma instância pequena de Torto Reverso.
(Essa era resposta que eu esperava no ricbit jam #3, que até hoje ninguém resolveu. Eu declaro então o concurso terminado por falta de participantes).
Abaixo o link da lib e a wiki correspondente para quem quiser saber mais:
https://github.com/ricbit/Oldies/tree/master/2011-05-bdd https://en.wikipedia.org/wiki/Binary_decision_diagram
Meu repositórios oldies tem muitas das coisas que já programei, mas não tem tudo. Uma boa parte está perdida por aí em backups e hard prints. Semana passada eu recuperei um pacotinho que tinha uma lib legal que fiz em 2011, e a história dela começa com o Knuth.
A única vez que vi o Knuth ao vivo foi em 2011. Na ocasião, perguntaram qual o algoritmo predileto dele, e ele disse que era o BDD (binary decision diagram), porque ele tinha acabado de publicar um livro sobre isso e o algoritmo que você mais gosta, em geral, tende a ser que o você acabou de aprender. Bom, se era o preferido do Knuth tinha que ser divertido, eu não podia deixar de implementar né?
O BDD é uma estrutura de dados que serve para guardar uma fórmula booleana em memória, de maneira otimizada. Lembra um pouco o mapa de Karnaugh, mas escala muito melhor, Karnaugh você não faz com mais 3 variáveis, BDD você chega em centenas fácil.
Intuitivamente você espera que guardar toda a fórmula em memória ocupe espaço exponencial (2^número de variáveis). E é isso mesmo! PORÉM, esse é o valor esperado para fórmulas aleatórias. As fórmulas da vida real costumam ter estrutura, e essa estrutura aparece magicamente quando você monta uma BDD. Na prática elas são bem melhores que o exponencial.
A BDD tem várias utilidades, mas eu suspeito que o Knuth gosta delas porque são ótimas para resolver puzzles! No livro Selected Papers on Fun And Games, o Knuth usa uma BDD para resolver o Slitherlink. Na minha implementação, eu usei para resolver o Torto Reverso. A figura mostra o BDD montado para uma instância pequena de Torto Reverso.
(Essa era resposta que eu esperava no ricbit jam #3, que até hoje ninguém resolveu. Eu declaro então o concurso terminado por falta de participantes).
Abaixo o link da lib e a wiki correspondente para quem quiser saber mais:
https://github.com/ricbit/Oldies/tree/master/2011-05-bdd https://en.wikipedia.org/wiki/Binary_decision_diagram
Nenhum comentário:
Postar um comentário