Please enable JavaScript.

Coggle requires JavaScript to display documents.

IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram

- - - - Avaliam as soluções parcialmente construída
        
        Pior caso ainda ocorre a "explosão" exponencial
    - - Nós refletem escolhas para um componente da solução
      - Se sua solução não é promissora, "ramo" é descartado
    - - Primeira solução legítima sobrando é usada para o próximo componente
      - Se der errado, substitui o último componente da solução parcialmente construída com sua próxima opção (backtracking)
      - state-space tree
        
        promissor
        
        solução parcial que pode levar para uma solução completa
        
        não-promissor
        
        não leva
      - Construída geralmente por DFS
      - Problemas
        
        n-rainhas
        
        n rainhas em um tabuleiro nxn
        
        Sendo que duas rainhas não ataquem uma a outra
        
        Coloca as rainhas em suas posições aceitáveis
        
        Se uma solução não for possível, volta e tenta outra posição pra anterior
        
        P/ qualquer n>= 4, a solução pode ser encontrada em tempo linear
        
        Circuito Hamiltoniano
        
        Se existe, começa no vértice "a"
        
        Se não for possível voltar a ele mesmo -> Backtrack (Tenta o próximo)
        
        Encontrar circuitos hamiltonianos em um grafo
        
        Soma em Subsets
        
        Achar uma soma dentro de um subset
        
        Ordenar o set em ordem crescente
        
        Condições para saber se o ramo é promissor
        
        Soma muito grande
        
        Soma muito pequena
        
        Se não é, backtrack
      - Observações gerais
        
        sst com nós que constroem tuplas
        
        Eficiência ainda não é tão grande
        
        Pode ficar intratável
        
        Eficiência temporal depende do problema e da instância do problema
        
        Formas de otimizar
        
        Explorar simetria de problemas combinatórios
        
        Designar valores previamente
        
        Rearranjar informações de uma dada instância
    - - Problema da otimização
        
        minimizar ou maximizar uma função objetiva
        
        feasible solution
        
        Satisfaz todas as restrições
        
        optimal solution
        
        Feasible e com o melhor valor da função objetiva
      - 2 itens a mais do que o backtracking
        
        Limite com o melhor valor da função objetiva
        
        Melhor valor até agora
      - Nós com o limite "Pior" que o da melhor solução são "podados"
      - Nós que não produzem soluções "feasible" são podados
      - Se soluções melhores forem encontradas, o valor da melhor solução é atualizado
      - Problemas
        
        Assignment
        
        n pessoas para n trabalhos com o custo sendo o menor possível
        
        Limite inferior é a soma dos menores elementos de cada fileira
        
        best-first branch-and-bound
        
        Gerar todos os filhos do nó mais promissor
        
        Hungarian method
        
        Mais prático
        
        Knapsack
        
        n itens de peso w, knapsack de capacidade W
        
        Subset de maior valor dos itens que cabem na knapsack
        
        Cada nó da árvore representa uma subset dos itens dados
        
        Usada para atualizar informação do melhor
        
        Traveling Salesman
        
        Menor circuito Hamiltoniano em um grafo
        
        Limite inferior
        
        Soma das distâncias de duas cidades próximas
        
        Ajustar limite inferior considerando as arestas
        
        Simplificações
        
        Apenas "tours" que começam em um nó arbitrário
        
        Depois de visitar n-1 cidades precisa visitar a restante e voltar ao início
        
        Se o grafo é direcionado, ignorar tours simétricos
      - Considerações finais
        
        Mesmas considerações gerais que o Backtracking
        
        Best-first nem sempre é a melhor estratégia
        
        Achar uma função bound não é simples
        
        Fácil de computar
        
        Não pode ser muito simplista