Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 16 - Coggle Diagram

- - - - A ideia é construir soluções um por um e evaluar os componentes parcialmente construídos.
        
        Um nó em uma árvore estado-espaço é chamada promissora se corresponde a uma solução parcialmente construída que pode lidar a uma solução completa
        
        Um nó em uma árvore estado-espaço é chamada não-promissora se nãocorresponde a uma solução parcialmente construída que pode lidar a uma solução completa
        
        Problemas conhecidos
        
        Problema de n-Queens
        
        Um exemplo conhecido; o problema é colocar n rainhas em um campo de xadrez NxN, de forma que nenhumas duas rainhas se ataquem.
        
        Vai iterando colocar rainhas na matriz até encontrar um caminho sem fim; então reiniciando de um certo ponto, realocando a posição da rainha.
        
        Problema do Circuito Hamiltoniano
        
        Dado o problema de encontrar um circuito hamiltoniano em um grafo...
        
        Se um circuito Hamiltoniano existe, começa no vértice a; sendo este a raiz da árvore estado-espaço.
        
        O primeiro componente da futura solução, se existe, é a primeira vértice intermediária de um circuito Hamiltoniano a ser construído.
        
        Segue em um caminho até encontrar um dead end, dando assim um backtrack
        
        Problema de Subset-Soma
        
        Achar a subset de um dado set A, de n integers de soma D.
        
        Após ordenar crescentemente, criamos a árvore estado-espaço como uma árvore binária para o determinado A e d. Sua esquerda e direita representam a inclusão e exclusão de a1 no set buscado.
        
        Assim, um caminho da raiz ao node no nével i indica quais dos primeiros i números têm sido incluidos no subset representado por aquele node.
        
        Gravando o valor de s, a soma dos números, no node, achamos a solução do problema quando s é igual a d.
        
        Perspectivas Gerais
        
        De uma visão mais geral, a maioria dos algoritmos de backtracking seguem a mesma linha:
        
        O output é uma n-upla onde cada xi é um elemento de um set linear ordenado finito Si
        
        A tupla pode precisar satisfazer condições e ter tamanho dependente do problema.
        
        Gera implicitamente ou explicitamente uma árvore de estado-espaço.
        
        Não chegue à falsa conclusão que backtracking é uma técnica muito eficiente. A esperança, porém, é que o algoritmo backtracking irá remover ramos suficientes da árvore de estado-espaço antes de esgotar tempo e/ou memória.
  - - - Seus nós refletem escolhas específicas feitas para os componentes da solução.
    - - Problemas Conhecidos
        
        Knapsack Problem
        
        Traveling Salesman Problem
        
        Assignment Problem
        
        Exemplo: associar n pessoas a n cargos para que o custo total seja o mínimo possível.
        
        Podemos descobrir qual nó é mais promissor comparando o bound menor dos nós utilizados. É lógico considerar o nó com o melhor bound como o mais promissor. Essa é a estratégia de best-first branch-and-bound
      - Esse tipo de problema visa minimizar ou maximizar alguma função objetiva, geralmente dentro de alguns limites.
        
        Uma solução viável é um ponto no espaço de busca do problema que satisfaz todas suas limitações.
        
        Uma solução ótima é uma solução viável com o melhor valor de função objetiva.
      - Dois itens adicionais, comparados ao Backtracking
        
        Uma maneira de dispor, para todo nó de uma árvore de estado-espaço, um bound no melhor valor da função objetiva em qualquer solução que pode ser obtida ao adicionar componentes à solução parcialmente construída representada pelo nó.
        
        Com essa info, podemos comparar o valor bound de um nó com o valor da melhor solução encontrada.
        
        O valor da melhor solução visto até agora.
      - Em geral, podemos terminar um caminho de busca no nó atual em uma árvore estado-espaço de um algoritmo branch-and-bound para qualquer uma das seguintes razões
        
        O nó não representa qualquer solução plausível, por violar restrições
        
        O subset de possíveis soluções representado pelo node é apenas um ponto. Nesse caso, comparamos o vetor da função objetiva pra essa solução possível com aquela da melhor solução encontrada até agora, e atualizamos se a solução for melhor.
        
        O valor do bound não é maior que o valor da melhor solução até agora