Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com limitações dos algoritmos - Coggle Diagram
Lidando com limitações dos algoritmos
Existem certos problemas que tem muitos problemas com o tempo de execução
Para ajudar a resolver esses problemas, existem dois design de algoritmos que tornam possivel resolver algumas instancias desses problemas. Que são o backtracking e o branch-and-bound
Esses métodos podem gerar todas as possibilidaes no worst case (problema igual a busca exaustiva), mas dá a esperança de conseguir resolver alguns casos.
Backtracking
Ideia
Construir uma solução (um componente por vez) a partir de um componente gerado. Se o compontente tenha violado as regras de um problema, esse componente é "fechado" e o algoritmo volta a ultimo bom candidato criado e continua construindo até encontrar a solução
State-space tree
A root representa o estado antes do algoritmo começar. Cada nivel sequente representa um novo compontente sendo adicionado a resposta.
Um node é promissor se ainda pode levar a solução e não promissor é um node que não pode. OBS: o node não promissor é descartado e não tem novos componentes adicionados
Ela é gerada de modo DFS.
Resolve problemas de não-otimização
Branch-and-bound
Ideia
Cada solução deve ter um valor que diga se ela é melhor ou pior que outras. Então, o algoritmo sempre irá priorizar o melhor atual, gerando todos os seus novos componentes até chegar a uma resposta. Ao chegar a uma solução, todas as outras que não puderem ser melhores que essa, são consideradas descartadas
Resolve problemas de otimização
State-space tree
A root representa o estado antes do algoritmo começar. Cada nivel sequente representa um novo compontente sendo adicionado a resposta. OBS: Cada node tem um valor
Um node é promissor se ainda pode levar a solução e não promissor é um node que não pode. OBS: o node não promissor é descartado e não tem novos componentes adicionados
Ela é gerada de modo best-first.