Please enable JavaScript.

Coggle requires JavaScript to display documents.

M15 - Coggle Diagram

- - - - uma maneira de fornecer, para cada nó de uma árvore de espaço de estado, um limite no melhor valor da função objetivo1 em qualquer solução que possa ser obtida adicionando outros componentes à solução parcialmente construída representada pelo nó
      - o valor da melhor solução vista até agora
    - - Trata-se de atribuir n trabalhos a n pessoas, de tal forma que o custo disso seja o menor possível
    - - Trata-se do seguinte problema: dados n itens de peso w, valores de 1 até n, e uma mochila de capacidade w, qual é o subconjunto mais valioso de itens que cabem na mochila
    - - Trata-se de achar um limite para o seguinte: para cada cidade, achar a soma das distâncias dessas para as duas cidades mais próximas, então calcular a soma desses n números e dividir por 2. O limite será o resto dessa divisão
  - - - O problema é colocar n rainhas em um tabuleiro de xadrez n × n de modo que duas rainhas não se ataquem por estarem na mesma linha, na mesma coluna ou na mesma diagonal.
      - Começamos com o tabuleiro vazio e, em seguida, colocamos a rainha 1 na primeira posição possível de sua linha, que está na coluna 1 da linha 1. Em seguida, colocamos a rainha 2, após tentar sem sucesso as colunas 1 e 2, na primeira posição aceitável para ele , que é o quadrado (2, 3), o quadrado na linha 2 e 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 retrocede 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 todo o caminho até a rainha 1 e o move para (1, 2). A rainha 2 então vai para (2, 4), a rainha 3 para (3, 1) e a rainha 4 para (4, 3), o que é uma solução para o problema.
    - - Sem perda de generalidade, podemos assumir que, se existe um circuito hamiltoniano, ele começa no vértice a. Conseqüentemente, tornamos o vértice a a raiz da árvore do espaço de estados. 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 a ordem do alfabeto para quebrar o laço triplo entre os vértices adjacentes a a, 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 um beco sem saída. Portanto, o algoritmo retrocede de f para e, depois para d e, em seguida, 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 retroceder de e para ce depois para b. A partir daí, ele vai para os vértices f, e, c e d, a partir dos quais pode legitimamente retornar a a, resultando no circuito hamiltoniano a, b, f, e, c, d, a. Se quiséssemos encontrar outro circuito hamiltoniano, poderíamos continuar esse processo retrocedendo a partir da folha da solução encontrada.
        Mais sobre o texto origina
    - - Encontre um subconjunto de um determinado conjunto A = {a1,. . . , an} de n inteiros positivos cuja soma é igual a um determinado inteiro positivo d. Por exemplo, para A = {1, 2, 5, 6, 8} e d = 9, existem duas soluções: {1, 2, 6} e {1, 8}. Claro, algumas instâncias desse problema podem não ter soluções.
      - A árvore de espaço de estado pode ser construída como uma árvore binária. A raiz da árvore representa o ponto de partida, sem decisões sobre os elementos fornecidos ainda. Seus filhos esquerdo e direito representam, respectivamente, inclusão e exclusão de a1 no conjunto que está sendo buscado. Da mesma forma, ir para a esquerda de um nó do primeiro nível corresponde à inclusão de a2, enquanto ir para a direita corresponde à sua exclusão, e assim por diante. Assim, um caminho da raiz para um nó no nível i da árvore indica qual dos primeiros i números foram incluídos nos subconjuntos representados por aquele nó. Registramos o valor de s, a soma desses números, no nó. Se s for igual ad, temos uma solução para o problema. Podemos relatar esse resultado e parar ou, se todas as soluções precisarem ser encontradas, continuar retrocedendo até o pai do nó.