Please enable JavaScript.

Coggle requires JavaScript to display documents.

LIMITAÇÕES DE UM ALGORITMO - Coggle Diagram

- - - - Note que na terminologia padrão de problemas de otimização, uma "SOLUÇÃO VIÁVEL" é um ponto do espaço de busca do problema que satisfaz todas as restrições do problema no qual uma solução ótima é uma solução viável com o melhor valor da função objetiva).
        
        (Ex: Um circuito Hamiltoniano no problema do caixeiro viajante, ou um subconjunto cujo de itens cujo peso total não exceda a capacidade da mochila(Knapsack) no Problema da Mochila.)
        
        Soluções: O menor circuito Hamiltoniano, e o conjunto de itens com o maior valor no Problema da Mochila.
        
        Em comparação ao Backtracking, o Branch and Bound requer mais 2 itens:
        
        Uma forma de prover, para cada nó da arvore do espaço de estados, um limite no melhor valor da função objetiva para qualquer solução que possa ser obtida pela adição de outros componentes para a solução parcialmente construída, a qual é representada pelo nó.
        
        O valor da melhor solução até o momento.
        
        Se esta info estiver disponivel, podemos comparar os limites de um nó com o valor da melhor solução até então. Se o valor de limite não for melhor que o valor da melhor solução, não for menor para o problema de minimização, não for maior para um problema de maximização, o nó é dito não promissor e é terminado.
        
        Nenhuma solução obtida dele poderá obter uma solução melhor que a atual.
        
        Em geral, termina-se um caminho de busca em um nó da arvore de espaço de estados quando:
        
        O valor do limite do nó não é melhor que o valor da melhor solução até agora.
        
        O nó não representa uma saída viável por conta de restrições do problema.
        
        O subconjuto de soluções viáveis representadas pelo nó consiste em único ponto. Neste caso, comparamos o valor da função objetiva para esta solução viável com a melhor vista até agora e atualizamos se o valor for melhor.
- - - - Existe um algoritmo que resolve o problema em tempo polinomial "Método Húngaro".
    - - Comparamos os limites inferiores dos nós das Lives. É sensato considerar o nó com o melhor limite como promissor, embora isso não o torne, mas adiante a possibilidade de uma solução ótima. Essa variação é chamada de "Melhor primeiro Branch and Bound)
- - - - É conveniente ordenar os itens da instancia informada em ordem decrescente da razão de valor/peso, de modo que o primeiro item tenha o melhor valor por peso e o último, o pior.
        
        Estrutura-se a árvore de estados para este problema como uma árvore binária. Nela, cada nó no i-gésimo nível da árvore representa todos os subconjuntos de n itens que incluem uma seleção particular feita dos primeiros i itens ordenados. Esta seleção é determinada pelo caminho da raiz até o nó: um ramo para esquerda indica inclusão de um item, para a direita, exclusão de um item. Registramos o peso total ( w )e o valor total ( v ) desta seleçao no nó, junto de algum limite superior para o valor de cada subconjunto.
        
        Uma maneira simples de calcular o limite superior é somá-lo a v, valor total dos itens já selecionados.
        
        Ler exemplo da paǵ 437/438
  - - - Ademais, para cada subconjunto de tours que devem incluir arestas particulares de um dado grafo, podemos modificar o limite inferior.
        
        Ler ex do livro na pag 439
- - - - As folhas representam becos sem saída não promissores ou soluções completas encontradas pelo algoritmo
      - Na maioria dos casos, uma árvore de espaço de estados para um algoritmo de backtracking é construído na forma de profundidade
        
        Se o nó atual não for promissor, o algoritmo volta ao pai do nó para considerar a próxima opção possível para seu último componente; se não houver essa opção, ele retrocede mais um nível da árvore e assim por diante
        
        Se o nó atual for promissor, seu filho gerado é adicionando a primeira opção legítima restante para o próximo componente de uma solução, e o processamento passa para esse filho
        
        Finalmente, se o algoritmo chegar a uma solução completa para o problema, ele para (se apenas uma solução for necessária) ou continua procurando outras soluções possíveis
- - - - Como cada uma das 4 rainhas deve ser colocada em sua própria linha, tudo o que precisamos fazer é atribuir uma coluna para cada rainha no tabuleiro
        
        Começamos com o tabuleiro vazio e depois colocamos a rainha 1 na primeira posição possível posição de sua linha, que está na coluna 1 da linha 1
        
        Em seguida colocamos a rainha 2, após tentando sem sucesso as colunas 1 e 2, na primeira posição aceitável para ela, que é o quadrado (2, 3), o quadrado na linha 2 e na coluna 3
        
        Isso prova ser um beco sem saída porque não há posição aceitável para a rainha 3. Então, o algoritmo volta e coloca a rainha 2 na próxima posição possível em (2, 4). Então a rainha 3 é colocada em (3, 2), o que prova ser outro beco sem saída
        
        O algoritmo então retrocede até a rainha 1 e move-a para (1, 2).A rainha 2 então vai para (2, 4), rainha 3 para (3, 1) e rainha 4 para (4, 3), o que é uma solução para o problema.
        
        Ver imagem no livro para entender os movimentos
- - - - O primeiro componente da nossa solução futura, se existir, é um primeiro vértice intermediário de um circuito hamiltoniano a ser construído. Usando a ordem alfabética para quebrar o empate triplo entre os vértices adjacentes a a, selecionamos o vértice b. De b, o algoritmo prossegue para c, depois para d, depois para e e, finalmente, para f, o que revela um beco sem saída
        
        Portanto, o algoritmo retrocede de f para e, depois para d e depois para c, o que fornece a primeira alternativa a ser seguida pelo algoritmo. Ir de c para e eventualmente se mostra inútil, e o algoritmo tem que voltar de e para c e depois para b. A partir daí, ele vai para os vértices f , e, c, e d, dos quais pode retornar legitimamente para a, produzindo o circuito hamiltoniano a, b, f, e, c, d, a. Se quiséssemos encontrar outro circuito hamiltoniano, poderíamos continuar este processo retrocedendo a partir da folha da solução encontrada.
      - Ver imagem no livro