Please enable JavaScript.

Coggle requires JavaScript to display documents.

M15 - Coggle Diagram

- - - - De uma perspectiva mais geral, a maioria dos algoritmos de backtracking se encaixa na seguinte descrição. Uma saída de um algoritmo de retrocesso pode ser considerada como um n-tupla
        onde cada coordenada xi é um elemento de algum conjunto finito linearmente ordenado Si.
    - - Problema do Circuito Hamiltoniano:
        Sem perda de generalidade, podemos supor que, se existe um circuito hamiltoniano,
        começa no vértice a. Assim, tornamos o vértice a a raiz do state-space tree.
        O circuito a ser analisado eh o da figura 12.3 do levitin
        
        O primeiro componente de nossa solução futura, se existir, é um
        primeiro vértice intermediário de um circuito hamiltoniano a ser construído. Usando o ordem alfabética para quebrar o laço de três vias entre os vértices adjacentes a um, nós selecionamos o vértice b. De b, o algoritmo avança para c, depois para d, depois para e, e finalmente para f, o que prova ser uma incongruência
        
        Portanto, o algoritmo faz o backtracking de f
        para e, depois para d e depois para c, que fornece a primeira alternativa para o algoritmo para seguir. Ir de c para e eventualmente se mostra inútil, e o algoritmo tem que fazer o backtracking de e para ce depois para b. A partir daí, ele vai para os vértices f, e, c, e d, a partir do qual pode legitimamente retornar a a, produzindo o circuito hamiltoniano a, b,
        f, e, c, d, a
      - Soma de Sub sets.
        : encontre um subconjunto de um determinado
        conjunto A = {a1, ..., an} de n inteiros positivos cuja soma é igual a um dado positivo
        inteiro d
        
        A space-state tree pode ser construída como uma árvore binária como a da Figura 12.4 para o subset A = {3, 5, 6, 7} e d = 15.
        A raiz da árvore representa o começo
        ponto, sem decisões sobre os elementos dados feitas até agora. os filhos esquerdo e direito representam, respectivamente, inclusão e exclusão de a1 no conjunto que se busca.
        
        Da mesma forma, ir para a esquerda de um nó do primeiro nível corresponde à inclusão de a2 indo para a direita corresponde à sua exclusão, e assim por diante. Assim, um caminho
        da raiz a um nó no nível i da árvore indica qual dos primeiros i números foram incluídos nos subconjuntos representados por esse nó
        
        Registramos o valor de s, a soma desses números, no nó. Se s é igual
        para d, temos uma solução para o problema. Podemos relatar este resultado e parar ou, se todas as soluções precisam ser encontradas, continue retrocedendo até o nó pai. Se s não for igual ad, podemos encerrar o nó como não prometedor se qualquer um
        das duas desigualdades a seguir se mantém:
        
        s + ai+1 > d (a soma é muito grande),
        
        s + somatorio de j = i+1 até n aj < d (a soma é muito pequena.
      - Problema das N rainhas:
        O problema é colocar n rainhas em um tabuleiro de xadrez n × n para que não haja duas
        rainhas atacam umas às outras por estarem na mesma linha ou na mesma coluna ou
        a mesma diagonal
        
        Começamos com o tabuleiro vazio e, em seguida, colocamos a rainha 1 no primeiro lugar 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 ele, que é o quadrado (2, 3), a casa na linha 2 e coluna 3. Isso prova ser uma incongruência
        
        Porque não há posição aceitável para a rainha 3. Então, o algoritmo faz o backtracking
        e coloca a rainha 2 na próxima posição possível em (2, 4). Então a rainha 3 é colocada em (3, 2), que prova ser outra incongruência. O algoritmo então rastreia todos
        o caminho para a rainha 1 e move-o para (1, 2). Rainha 2 então vai para (2, 4), rainha 3 para (3, 1) e rainha 4 a (4, 3), que é uma solução para o problema
    - - Falando agora sobre Backtracking.
        O diretor da escola
        ideia é construir soluções, um componente de cada vez, e avaliá-las parcialmente
        candidatos construídos da seguinte forma.
        
        Se uma solução parcialmente construída pode ser desenvolvida ainda mais sem violar as restrições do problema, isso é feito tomando
        a primeira opção legítima restante para o próximo componente. Se não houver opção legítima para o próximo
        
        Um nó em uma árvore de espaço de estado é considerado promissor se corresponder a um
        solução parcialmente construída que ainda pode levar a uma solução completa; caso contrário, é chamado de não promissor
      - As técnicas diferem na natureza dos problemas que
        pode ser aplicado. Branch-and-bound é aplicável apenas a problemas de otimização enquanto Backtracking é utilizada para problemas que nao precisam de otimização
- - - - Knapsack Problem:
        Dados n itens de pesos conhecidos wi e valores vi, i = 1, 2,. . . , n, e uma mochila de capacidade W, encontre o subconjunto mais valioso dos itens que cabem na mochila.
        
        É natural estruturar a árvore de espaço de estado para este problema como uma árvore binária
        construído assim:
        cada nó no nível i representa todos os sub sets de itens que cabem no knapsack.
        O primeiro item tem o maior custo-benefício e o ultimo tem o pior.
        É normal fazer a representação desse problema como uma arvore binária
        
        Registramos o peso total w e o valor total v deste seleção no nó, junto com algum limite superior ub no valor de qualquer subconjunto que pode ser obtido adicionando zero ou mais itens a esta seleção. Uma maneira simples de calcular o limite superior ub é adicionar av, o valor total de os itens já selecionados, o produto da capacidade restante da mochila W - w e o melhor payoff por unidade entre os itens restantes, que é vi + 1 / wi + 1:
        ub = v + (W − w)(vi+1/wi+1).
      - O problema do vendedor viajante:
        No livro nao vi falando o que esse problema significa mas ele fala que resolveremos esse problema se chegarmos a um limite inferior razoável na turnê comprimentos.
        
        Um limite inferior muito simples pode ser obtido encontrando o menor elemento na matriz de distância intermunicipal D e multiplicando-o pelo número de cidades n. Mas há um limite inferior menos óbvio e mais informativo para as instâncias
        com matriz simétrica D, que não requer muito trabalho para calcular
        
        Para cada cidade i, 1 ≤ i ≤ n, encontre
        a soma si das distâncias da cidade i às duas cidades mais próximas; calcule a soma s desses n números, divida o resultado por 2 e, se todas as distâncias forem inteiras, arredonde o resultado para o número inteiro mais próximo:
        lb = [s/2].
        Mais do que isso para qualquer subconjunto de passeios que deve incluir bordas específicas de um determinado
        gráfico, podemos modificar o limite inferior de acordo
        
        Em primeiro lugar, sem perda de generalidade, podemos considerar apenas tours que começam em a. Em segundo lugar, porque nosso grafo não é direcionado, podemos gerar apenas tours nos quais b é visitado antes de c. Além disso, depois de visitar n - 1 = 4 cidades, um tour não tem escolha a não ser visitar a cidade não visitada restante e retornar ao
        começar um.
      - Assignment Problem:
        Selecione um elemento em cada linha da matriz, de modo que não haja dois elementos selecionados no mesma coluna e sua soma é a menor possível
        
        Em vez de gerar um único filho do último nó promissor como
        que fizemos no backtracking, vamos gerar todos os filhos do mais promissor
        nó entre as folhas não terminadas na árvore atual.
        
        Como podemos saber qual dos nós é mais
        promissor? Podemos fazer isso comparando os limites inferiores dos nós ativos. Isto é sensato considerar um nó com o melhor limite como o mais promissor, embora
        isso, é claro, não exclui a possibilidade de que uma solução ótima pertença, em última instância, a um ramo diferente da árvore do espaço de estados. Esta variação do
        estratégia é chamada de best-first branch-and-bound
        
        Voltando ao problema, temos quatro folhas vivas - nós 1 a 4 - que podem conter um ótimo
        solução. O mais promissor deles é o nó 2 porque tem o menor valor de limite inferior. Seguindo nossa estratégia de pesquisa "best-first search", partimos desse primeiro nó considerando as três maneiras diferentes de selecionar um elemento do
        segunda linha e não na segunda coluna - os três trabalhos diferentes que podem ser atribuído à pessoa b
        
        Das seis folhas vivas - nós 1, 3, 4, 5, 6 e 7 - que podem conter um ótimo solução, escolhemos novamente aquele com o menor limite inferior, nó 5. Primeiro, nós consideramos selecionar o elemento da terceira coluna da linha de c. Isso nos deixa sem escolha a não ser selecionar o elemento da quarta coluna da linha d Isso produz a folha 8 que corresponde à solução viável .Seu irmão, o nó 9, corresponde à solução viável com o custo total de 25. Já que seu custo é maior que o custo da solução representada pela folha 8, o nó 9 é simplesmente encerrado
        
        Agora, conforme inspecionamos cada uma das folhas vivas da última árvore de espaço de estado, descobrimos que seus valores de limite inferior são
        não menor que 13, o valor da melhor seleção visto até agora. Consequentemente,
        terminamos todos eles e reconhecemos a solução representada pela folha 8 como o
        solução ideal para o problema.
    - - Em geral, encerramos um caminho de pesquisa no nó atual em um espaço de estado
        árvore de um algoritmo branch-and-bound por um dos três motivos a seguir:
        
        O nó não representa soluções viáveis porque as restrições do
        problema já foram violados.
        
        O subconjunto de soluções viáveis representado pelo nó consiste em um único ponto (e, portanto, nenhuma outra escolha pode ser feita) - neste caso, comparamos
        o valor da função objetivo para esta solução viável com o da melhor solução vista até agora e atualize o último com o anterior se o novo
        solução é melhor
        
        O valor do limite do nó não é melhor do que o valor da melhor solução
        visto até agora