Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com limitações de poder algorítimico - Coggle Diagram
Lidando com limitações de poder algorítimico
Permitem resolver algumas instâncias maiores de problemas combinacionais
Backtracking
Problemas de não-otimização
Geralmente, a árvore do problema é gerada em profundidade
Ao invés de registrar as possíveis soluções até o final, registra somente até o passo que dá errado
Desenvolve a solução avaliando a viabilidade do próximo valor
Se não houver viabilidade em nada, nenhuma das possíveis respostas será válida
O algoritmo volta à minha possível solução, ao último passo antes de dar tudo errado e substituir a antiga escolha por outra possível
State Space Tree
Promising: Candidato a guiar a uma solução válida
Nonpromising- O contrário
Folhas: Becos sem saída ou soluções
Geralmente construída em dfs
branch-and-bound
Problemas de otimização
Geralmente, a árvore do problema é gerada de acordo com várias regras diferentes
Melhoria sobre busca exaustiva
Criam soluções candidatas a um problema
Se não houver valores potenciais restantes que podem levar a uma solução, aquele caminho é descartado
Risco de Explosão Esponencial