Please enable JavaScript.
Coggle requires JavaScript to display documents.
ATALHOS PARA REFINAR A ANÁLISE EXAUSTIVA - Coggle Diagram
ATALHOS PARA REFINAR A ANÁLISE EXAUSTIVA
Backtracking
Características
Aplicável em problemas que envolvem encontrar instâncias especiais em um conjunto que se expande exponencialmente com o input
State-space tree é construída de maneira similar a uma abordagem Depth-first
Classifica soluções parciais em promissoras (se estas ainda podem guiar a uma solução completa) ou não promissoras
Quando um nódulo da árvore é considerado não promissor, é feito um retorno até soluções parciais passadas
Exemplos de aplicação
Problema das n rainhas
Problema da soma de um sub-conjunto
Coloração de um grafo
Problema do cavalo
Circuito Hamiltoniano
Ramificar e Limitar
Características
Aplicável em problemas de optimização: quando se deseja maximizar o valor ou minimizar o custo de uma disposição de elementos
State-space tree construída a partir de uma abordagem Best-First
IA as vezes é uma melhor opção que a abordagem Best-First
Faz uso de limites mínimos e máximos que servem para verificar se um ramo de soluções possui de fato as soluções mais otimizadas
Desafio de definir um bom limite superior/inferior
Precisa ser fácil de computar
Não pode ser simples demais
Similar ao backtracking com a adição da complexidade extra decorrente do uso dos limites e do armazenamento da "melhor solução até o momento
Exemplos de aplicação
Problema da Mochila
Problema do caixeiro viajante
Problema da atribuição
Características gerais
Os métodos não tornam os problemas tratáveis, os piores casos ainda estão sujeitos à expansão exponencial
É conveniente construir uma árvore que organize às escolhas feitas, chamada de
state-space tree
Algumas instâncias largas dos problemas serão solucionadas em tempo tratável com o uso desses métodos
Consistem em formular soluções parciais, um componente por vez, verificando se estas escolhas favorecem uma solução geral e abandonando-as quando se revelam becos sem saída
Otimizações
Organizar previamente os dados da ocorrência
Uso de simetria para encontrar outras soluções a partir de uma primeira