Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com as Limitações do Poder do Algoritmo - Coggle Diagram
Lidando com as Limitações do Poder do Algoritmo
Encontrar formas de lidar com problemas importantes que são difíceis de resolver através de algoritmos.
Backtracking
Problemas que precisam achar um elemento com uma propriedade especial em um domínio que crescem de forma exponencialmente rápida de acordo com o tamanho da entrada do problema.
Backtracking é uma variação mais inteligente da abordagem de busca exaustiva (gerar todos os candidatos à solução e identificar um ou mais com a propriedade desejada).
No caso da abordagem do backtracking, as soluções são construídas parcialmente e seus componentes são avaliados um a um. Se um componente satisfazer os requisitos da solução (não violar as restrições), ela continua sendo construída a partir das opções legítimas restantes. Caso contrário, o algoritmo volta para substituir o último componente da solução parcialmente construída com a próxima opção.
Esse processo geralmente é implementado com uma árvore de escolhas chamada state-space-tree. A raiz representa um estado inicial antes da busca pela solução começar. Os nós no primeiro nível são todas as opções para o primeiro componente, os nós do segundo nível representam todas as opções para o segundo componente e assim por diante.
Um nó é promissor se ele corresponde a uma solução parcialmente construída. Caso contrário, ele é dito não-promissor.
As folhas representam nós não promissores ou soluções completas.
Geralmente, essas árvores são construídas através de DFS.
3 more items...