A abordagem mais comum em problemas que pedem para contar o número de soluções ou minimizar alguma função é o ataque por busca exaustiva, ou seja, testar todas as soluções possíveis e realizar o que é pedido no problema para cada uma delas. Todavia, esse paradigma de resolução não é muito eficiente e pode levar a muitos TLEs (Time Limit Exceeded), portanto é bom saber em quais situações usá-lo e também maneiras de aumentar a eficiência.
Assunto: Busca Exaustiva
Bibliografia principal:
- Competitive Programming, capítulo 3 (3.2) - Complete Search
- Introduction to Algorithms, apêndice A - Summations
- Top Coder - Computational Complexity: Section 2
- Top Coder - An Introduction to Recursion, Part 1
- Top Coder - An Introduction to Recursion, Part 2
- Matemática Concreta, capítulo 2 - Somas
- Introduction to Algorithms, capítulo 3 - Growth of Functions
- UVa 435 (Block Voting): gerar todos os subconjuntos.
- UVa 11205 (The Broken Pedometer): simulação bem interessante, mas deve ser feita com cuidado.
- UVa 624 (CD): problema clássico da mochila, só que com pouquíssimos itens, podendo simular totalmente.
- UVa 11195 (Another n-Queen Problem): melhor problema de busca exaustiva, pois não aceita a solução simples das 8 rainhas, sendo essencial uma boa noção de "escovar bits".
Nenhum comentário:
Postar um comentário