Please enable JavaScript.

Coggle requires JavaScript to display documents.

Lidando com as limitações de Poder Algorítmico - Coggle Diagram

- - - - Estas técnicas funcionam construindo uma árvore de Espaço de estados, onde os nós representam as decisões tomadas para a composição de uma solução. Um nó é deletado assim que é garantido que, independente das decisões tomadas, os descendentes daquele nó não irão solucionar o problema
        
        Branch-and-bound
        
        No back-tracking, a ideia central era de simplesmente cortar os galhos da árvore no momento que era deduzido que aquele galho não levaria a uma solução. Branch-and-bound foca em problemas de otimização, logo, ele leva essa idéia além.
        
        Branch-and-bound busca maximizar ou minimizar uma função objetiva. Esta função pode ser o comprimento de um caminho, o valor total de uma compra. E estas funções sempre estão sujeitas a restrições, afinal, o mundo real tem restrições. No exemplo da compra, o orçamento que uma pessoa tem para uma compra é limitado, e o ideal é sempre comprar todos os itens da lista (se houver uma).
        
        Na terminologia de otimização de problemas, uma solução factível é uma solução que, considerando todo o escopo do problema, é uma solução que satisfaz todas as restrições do problema.
        
        Se comparado ao back-tracking, o branch-and-bound necessita de mais dois ítens
        
        Uma funcionalidade que forneça, para cada nó da árvore, o melhor resultado da função objetivo obtida a partir de incrementos de novos componentes à árvore parcialmente construída de soluções.
        
        O valor da melhor solução encontrado até então
        
        Com essas informações, é possível comparar o valor viculado a um nó com o valor da melhor solução encontrada até agora. Se o valor do nó não é melhor do que o valor da melhor solução encontrada até então, este nó é "não promissor". Naturalmente, este nó é deletado, visto que não é possível vim, deste nó e de seus descendentes, uma solução melhor do que a que já foi encontrada.
        
        1 more item...
        
        Exemplos de problemas resolvíveis com branch-and-bound
        
        Assignment problem / Problema da atribuição
        
        Em um caso onde tenho n trabalhos disponíveis, n pessoas para realizar estes trabalhos, e existe um custo associado à pessoa i realizar o trabalho j, como devo distribuir estes trabalhos de forma que o custo total seja o menor possível?
        
        Knapsack problem / Problema da mochila
        
        Outro problema introduzido anteriormente, dado n itens, cada um com um diferente peso E valor associado, e uma mochila de capacidade máxima W, qual é o subconjunto mais valioso possível que a mochila suporta carregar?
        
        O caixeiro viajante
        
        Problema clássico, um caixeiro viajante precisa percorrer várias cidades para realizar seu serviço, sabendo quais são os custos/tamanhos da viagem entre duas das cidades, qual é a menor rota que este caixeiro pode fazer?
        
        Back-tracking
        
        Árvore desenvolvida similarmente a uma DFS
        
        São construídas, uma por vez, candidatas a soluções, que quando estiverem parcialmente construídas serão avaliadas
        
        Se uma solução candidata pode ser desenvolvida sem violar as restrições do problema, ela segue para o próximo estágio
        
        Se uma solução candidata apresenta não apresenta descendentes que possam alcançar uma solução legítima, eles não precisam ser considerados (os nós da árvore de espaço e estados é deletado)
        
        Neste caso, o algoritmo retrocede para o componente anterior da solução (nó pai), e tenta a sua próxima opção (o outro nó filho)
        
        Na árvore de espaço de estados, a raiz representa o estado inicial, antes da busca começar
        
        Os primeiros nós são as primeiras decisões tomadas na tentativa de encontrar uma solução
        
        1 more item...
        
        Exemplos de problemas resolvíveis com back-tracking
        
        Problema do circuito Hamiltoniano
        
        Exemplo mencionado anteriormente, o circuito Hamiltoniano, em um grafo G, é o caminho que passa por todos os vértices deste grafo, sem passar pelo mesmo vértice duas vezes.
        
        Subset sum problem / Problema da soma de subconjuntos
        
        Para um conjunto A, contendo n inteiros positivos (a1, a2, ..., an), quais os subconjuntos de A tem soma igual a um inteiro arbitrário d?
        
        n-Queens problem / Problema das 8 damas
        
        Como distribuir n rainhas em um tabuleiro de xadrez n x n, sem que elas compartilhem uma linha ou coluna (ou seja, sem que elas se ataquem).
      - Embora estas abordagens facilite a solução de alguns problemas considerados muito difíceis, o pior caso ainda é o mesmo de qualquer abordagem por força bruta, de crescimento exponencial.