Please enable JavaScript.

Coggle requires JavaScript to display documents.

Lidando com as limitações de poder dos algoritmos, C (A), Unlike…

- - - - A ideia principal é construir soluções um componente por vez e avaliar tais candidatos parcialmente 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 válida para o próximo componente.
        
        Se não houver uma opção legítima para o próximo componente, nenhuma alternativa para qualquer componente restante precisa ser considerada. Nesse caso, o algoritmo retrocede para substituir o último componente da solução parcialmente construída por sua próxima opção.
        
        é conveniente usar para esse tipo de abordagem as state-space trees :!:
        
        General remarks:
        
        From a more general perspective, most backtracking algorithms fit the following description. An output of a backtracking algorithm can be thought of as an n-tuple (x1, x2,...,xn) where each coordinate xi is an element of some finite linearly ordered set Si.
        
        You should not be lead to the false conclusion that backtracking is a very efficient technique. In the worst case, it may have to generate all possible candidates in an exponentially (or faster) growing state space of the problem at hand. The hope, of course, is that a backtracking algorithm will be able to prune enough branches of its state-space tree before running out of time or memory or both. The success of this strategy is known to vary widely, not only from problem to problem but also from one instance to another of the same problem.
        
        Knuth suggested generating a random path from the root to a leaf and using the information about the number of choices available during the path generation for estimating the size of the tree:
        + c1 + c1c2 + ... + c1c2 ... cn.
    - - O problema consiste em 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. Para n = 1, o problema tem uma solução trivial, e é fácil ver que não há solução para n = 2 e n = 3. Portanto, devesse considerar o problema para quatro rainhas e resolve-lo pela técnica do backtracking. Uma vez que cada uma das quatro rainhas deve ser colocada em sua própria linha, tudo o que se precisa fazer é atribuir uma coluna para cada rainha no tabuleiro.
        
        We start with the empty board and then place queen 1 in the first possible position of its row, which is in column 1 of row 1. Then we place queen 2, after trying unsuccessfully columns 1 and 2, in the first acceptable position for it, which is square (2, 3), the square in row 2 and column 3. This proves to be a dead end because there is no acceptable position for queen 3. So, the algorithm backtracks and puts queen 2 in the next possible position at (2, 4). Then queen 3 is placed at (3, 2), which proves to be another dead end. The algorithm then backtracks all the way to queen 1 and moves it to (1, 2). Queen 2 then goes to (2, 4), queen 3 to (3, 1), and queen 4 to (4, 3), which is a solution to the problem.
      - Hamiltonian Circuit Problem
        
        pode-se assumir que, se existe um circuito hamiltoniano, ele começa no vértice a. Consequentemente, tornamos o vértice (a) a raiz da state-space tree. O primeiro componente de nossa solução futura, se ele 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 (c) e depois para (b). A partir daí, ele vai para os vértices (f), (e), (c) e (d), a partir dos quais pode legitimamente retornar para (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.
        
        Subset-Sum Problem
        
        Find a subset of a given set A = {a1,...,an} of n positive integers whose sum is equal to a given positive integer d. For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions: {1, 2, 6} and {1, 8}. Of course, some instances of this problem may have no solutions. It is convenient to sort the set’s elements in increasing order. So, we will assume that:
        a1 < a2 < ... < an.
        The state-space tree can be constructed as a binary tree like that in the Figure for the instance A = {3, 5, 6, 7} and d = 15. The root of the tree represents the starting point, with no decisions about the given elements made as yet. Its left and right children represent, respectively, inclusion and exclusion of a1 in a set being sought. Similarly, going to the left from a node of the first level corresponds to inclusion of a2 while going to the right corresponds to its exclusion, and so on. Thus, a path from the root to a node on the ith level of the tree indicates which of the first i numbers have been included in the subsets represented by that node. We record the value of s, the sum of these numbers, in the node. If s is equal to d, we have a solution to the problem. We can either report this result and stop or, if all the solutions need to be found, continue by backtracking to the node’s parent. If s is not equal to d, we can terminate the node as nonpromising if either of the following two inequalities holds:
  - - - branch-and-bound requer dois itens adicionais em comparação com um backtracking:
        
        uma maneira de fornecer, para cada nó de uma state-space tree, um limite no melhor valor da função objetiva 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é o momento.
        
        Em geral, se encerra um caminho de pesquisa no nó atual em uma state-space tree de um algoritmo branch-and-bound por qualquer um dos três motivos a seguir:
        
        O valor do limite do nó não é melhor do que o valor da melhor solução vista até agora.
        
        O nó não representa soluções viáveis porque as restrições do problema já foram violadas.
        
        O subconjunto de soluções viáveis representado pelo nó consiste em um único ponto (portanto, nenhuma outra escolha pode ser feita), neste caso, se compara o valor da função objetivo para esta solução viável com aquele da melhor solução vista até agora e atualiza-se o último com o anterior, se a nova solução for melhor.
        
        Pros e contras:
        
        Similar ao backtracking: essas técnicas de state-space tree permitem resolver muitas instâncias grandes de problemas combinatórios difíceis. Como regra, no entanto, é virtualmente impossível prever quais instâncias serão solucionáveis em um período de tempo realista e quais não.
        
        A incorporação de informações adicionais pode ampliar a gama de instâncias solucionáveis. seguindo esse raciocínio, um algoritmo branch-and-bound pode às vezes ser acelerado por informações sobre o valor da função objetivo de alguma solução não trivial e viável.
    - - uma instância do problema de atribuído é especificada
        por uma matriz de custo n × n para que possamos definir o problema da seguinte maneira: selecione um elemento em cada linha da matriz para que não haja dois elementos selecionados na mesma coluna e sua soma seja a menor possível.
        
        Em vez de gerar um único filho do último nó promissor como
        feito no backtracking, serão gerados todos os filhos do nó mais promissor entre as folhas não terminadas na árvore atual. (Folhas não terminadas, ou seja, ainda promissoras, também são chamadas de vivas.) Para saber qual dos nós é mais promissor, Pode-se comparar os limites inferiores dos nós ativos. É sensato considerar um nó com o melhor limite como o mais promissor, embora isso, é claro, não exclua a possibilidade de que uma solução ótima acabará pertencendo a um ramo diferente da state-space tree. Essa variação da estratégia é chamada de best-first branch-and-bound.
      - Knapsack Problem
        
        dados n itens de pesos conhecidos wi e valores vi, i = 1, 2,. . . , n, e uma mochila com capacidade W, encontre o subconjunto mais valioso dos itens que cabem na mochila. É conveniente ordenar os itens de uma determinada instância em ordem decrescente por suas proporções de valor para peso. Então, o primeiro item dá o melhor retorno por unidade de peso e o último dá o pior retorno por unidade de peso, com empates resolvidos arbitrariamente:
        v1/w1 ≥ v2/w2 ≥ ... ≥ vn/wn
        
        É natural estruturar a state-space tree para esse problema como uma árvore binária construída da seguinte maneira. Cada nó no iº nível desta árvore, 0 ≤ i ≤ n, representa todos os subconjuntos de n itens que incluem uma seleção particular feita a partir dos primeiros i itens pedidos. Esta seleção particular é determinada exclusivamente pelo caminho da raiz ao nó: uma ramificação indo para a esquerda indica a inclusão do próximo item e uma ramificação indo para a direita indica sua exclusão. Registramos o peso total w e o valor total v dessa 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 essa seleção.
        
        A simple way to compute the upper bound ub is to add to v, the total value of the items already selected, the product of the remaining capacity of the knapsack W − w and the best per unit payoff among the remaining items, which is vi+1/wi+1:
        ub = v + (W − w)(vi+1/wi+1).
        
        :warning:
        Solving the knapsack problem by a branch-and-bound algorithm has a rather unusual characteristic. Typically, internal nodes of a state-space tree do not define a point of the problem’s search space, because some of the solution’s components remain undefined. (See, for example, the branch-and-bound tree for the assignment problem discussed in the preceding subsection.) For the knapsack problem, however, every node of the tree represents a subset of the items given. We can use this fact to update the information about the best subset seen so far after generating each new node in the tree.
        
        Traveling Salesman Problem
        
        Para aplicar a técnica de branch-and-bound a instâncias do problema do travaling salesman se chegarmos a um limite inferior razoável para a duração das viagens. Um limite inferior muito simples pode ser obtido encontrando o menor elemento na matriz D de distância intermunicipal e multiplicando-o pelo número de cidades n.
        
        há um limite inferior menos óbvio e mais informativo para instâncias com uma matriz D simétrica, que não requer muito trabalho para ser calculado. Não é difícil mostrar que podemos calcular um limite inferior no comprimento l de qualquer passeio da seguinte maneira. 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 desses n números, divida o resultado por 2 e, se todas as distâncias forem inteiros, arredonde o resultado para o número inteiro mais próximo:
        lb = [S/2] ([ ] = teto)
        
        para qualquer subconjunto de passeios que deve incluir bordas específicas de um determinado grafo, podemos modificar o limite inferior de acordo.