Retrocedendo - Backtracking

Backtracking é um algoritmo geral para encontrar soluções para alguns problemas computacionais , notavelmente problemas de satisfação de restrição , que constrói de forma incremental candidatos às soluções e abandona um candidato ("backtracks") assim que determina que o candidato não pode ser concluído para um solução.

O exemplo clássico do uso de backtracking é o quebra-cabeça de oito rainhas , que pede todos os arranjos de oito rainhas de xadrez em um tabuleiro de xadrez padrão para que nenhuma rainha ataque qualquer outra. Na abordagem de retrocesso comum, os candidatos parciais são arranjos de k rainhas nas primeiras k linhas do tabuleiro, todas em diferentes linhas e colunas. Qualquer solução parcial que contenha duas rainhas que se atacam mutuamente pode ser abandonada.

O retrocesso pode ser aplicado apenas para problemas que admitem o conceito de uma "solução candidata parcial" e um teste relativamente rápido para saber se ela pode ser completada para uma solução válida. É inútil, por exemplo, para localizar um determinado valor em uma tabela não ordenada. Quando aplicável, entretanto, o retrocesso costuma ser muito mais rápido do que a enumeração por força bruta de todos os candidatos completos, pois pode eliminar muitos candidatos com um único teste.

O retrocesso é uma ferramenta importante para resolver problemas de satisfação de restrições , como palavras-cruzadas , aritmética verbal , Sudoku e muitos outros quebra-cabeças. Freqüentemente, é a técnica mais conveniente para análise , para o problema da mochila e outros problemas de otimização combinatória . É também a base das chamadas linguagens de programação lógica , como Icon , Planner e Prolog .

O retrocesso depende dos " procedimentos de caixa preta " fornecidos pelo usuário que definem o problema a ser resolvido, a natureza dos candidatos parciais e como eles são estendidos para candidatos completos. É, portanto, uma metaheurística em vez de um algoritmo específico - embora, ao contrário de muitas outras meta-heurísticas, seja garantido que encontrará todas as soluções para um problema finito em um período de tempo limitado.

O termo "retrocesso" foi cunhado pelo matemático americano DH Lehmer na década de 1950. A linguagem pioneira de processamento de strings SNOBOL (1962) pode ter sido a primeira a fornecer uma facilidade de retrocesso geral embutida.

Descrição do método

O algoritmo de retrocesso enumera um conjunto de candidatos parciais que, em princípio, podem ser completados de várias maneiras para dar todas as soluções possíveis para o problema dado. A conclusão é feita de forma incremental, por uma sequência de etapas de extensão candidatas.

Conceitualmente, os candidatos parciais são representados como os nós de uma estrutura de árvore , a árvore de pesquisa potencial. Cada candidato parcial é o pai dos candidatos que diferem dele por uma única etapa de extensão; as folhas da árvore são os candidatos parciais que não podem ser estendidos mais.

O algoritmo de retrocesso percorre esta árvore de pesquisa recursivamente , da raiz para baixo, na ordem de profundidade primeiro . Em cada nó c , o algoritmo verifica se c pode ser concluído para uma solução válida. Se não puder, toda a subárvore com raiz em c será ignorada ( podada ). Caso contrário, o algoritmo (1) verifica se o próprio c é uma solução válida e, se for, a relata ao usuário; e (2) enumera recursivamente todas as subárvores de c . Os dois testes e os filhos de cada nó são definidos por procedimentos fornecidos pelo usuário.

Portanto, a árvore de pesquisa real que é percorrida pelo algoritmo é apenas uma parte da árvore potencial. O custo total do algoritmo é o número de nós da árvore real vezes o custo de obtenção e processamento de cada nó. Este fato deve ser considerado ao escolher a árvore de busca potencial e implementar o teste de poda.

Pseudo-código

Para aplicar o retrocesso a uma classe específica de problemas, deve-se fornecer os dados P para a instância particular do problema a ser resolvido e seis parâmetros procedimentais , raiz , rejeição , aceitação , primeiro , próximo e saída . Esses procedimentos devem ter os dados de instância P como parâmetro e devem fazer o seguinte:

  1. root ( P ): retorna o candidato parcial na raiz da árvore de pesquisa.
  2. rejeitar ( P , c ): retorna verdadeiro somente se o candidato parcial c não vale a pena ser completado.
  3. aceitar ( P , c ): retorna verdadeiro se c for uma solução de P e falso caso contrário.
  4. primeiro ( P , c ): gera a primeira extensão do candidato c .
  5. next ( P , s ): gera a próxima extensão alternativa de um candidato, após a extensão s .
  6. saída ( P , c ): use a solução c de P , conforme apropriado para a aplicação.

O algoritmo de backtracking reduz o problema ao backtrack de chamada ( root ( P )), onde backtrack é o seguinte procedimento recursivo:

procedure backtrack(c) is
    if reject(P, c) then return
    if accept(P, c) then output(P, c)
    s ← first(P, c)
    while s ≠ NULL do
        backtrack(s)
        s ← next(P, s)

Considerações de uso

O rejeitar procedimento deve ser uma função com valor de boolean que retorna verdadeiro somente se é certo que nenhum possível extensão do c é uma solução válida para P . Se o procedimento não pode chegar a uma conclusão definitiva, ele deve retornar falso . Um resultado verdadeiro incorreto pode fazer com que o procedimento bt perca algumas soluções válidas. O procedimento pode assumir que rejeitar ( P , t ) retornou falso para cada ancestral t de c na árvore de pesquisa.

Por outro lado, a eficiência do algoritmo de retrocesso depende da rejeição retornando true para candidatos que estão o mais próximo possível da raiz. Se rejeitar sempre retorna falso , o algoritmo ainda encontrará todas as soluções, mas será equivalente a uma pesquisa de força bruta.

O procedimento de aceitação deve retornar verdadeiro se c for uma solução completa e válida para a instância do problema P e falso caso contrário. Ele pode assumir que o candidato parcial c e todos os seus ancestrais na árvore passaram no teste de rejeição .

O pseudocódigo geral acima não assume que as soluções válidas são sempre folhas da árvore de pesquisa potencial. Em outras palavras, ele admite a possibilidade de que uma solução válida para P possa ser posteriormente estendida para produzir outras soluções válidas.

O primeiro e o próximo procedimento são usados ​​pelo algoritmo de backtracking para enumerar os filhos de um nó c da árvore, ou seja, os candidatos que diferem de c por um único passo de extensão. A primeira chamada ( P , c ) deve produzir o primeiro filho de c , em alguma ordem; e a chamada next ( P , s ) deve retornar o próximo irmão do nó s , nessa ordem. Ambas as funções devem retornar um candidato "NULL" distinto, se o filho solicitado não existir.

Juntas, as funções raiz , primeira e próxima definem o conjunto de candidatos parciais e a árvore de pesquisa potencial. Eles devem ser escolhidos de forma que cada solução de P ocorra em algum lugar da árvore e nenhum candidato parcial ocorra mais de uma vez. Além disso, eles devem admitir um predicado de rejeição eficiente e eficaz .

Variantes de parada antecipada

O pseudocódigo acima chamará a saída para todos os candidatos que são uma solução para a instância P fornecida . O algoritmo pode ser modificado para parar após encontrar a primeira solução ou um número especificado de soluções; ou depois de testar um número especificado de candidatos parciais ou depois de gastar uma determinada quantidade de tempo de CPU .

Exemplos

Um Sudoku resolvido por retrocesso.

Exemplos em que o retrocesso pode ser usado para resolver quebra-cabeças ou problemas incluem:

A seguir está um exemplo em que o retrocesso é usado para o problema de satisfação de restrição :

Satisfação de restrição

O problema geral de satisfação de restrição consiste em encontrar uma lista de inteiros x = ( x [1], x [2], ..., x [ n ]) , cada um em algum intervalo {1, 2, ..., m }, que satisfaça alguns restrição arbitrária (booleano função) F .

Para esta classe de problemas, a instância de dados P seriam os inteiros m e n , e o predicado F . Em uma solução típica de retrocesso para este problema, pode-se definir um candidato parcial como uma lista de inteiros c = ( c [1], c [2], ..., c [k]) , para qualquer k entre 0 e n , que devem ser atribuídos às primeiras k variáveis x [1], x [2],…, x [ k ] . O candidato raiz seria então a lista vazia (). O primeiro e o próximo procedimento seriam então

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)
function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Aqui, o comprimento ( c ) é o número de elementos na lista c .

A chamada rejeitada ( P , c ) deve retornar true se a restrição F não puder ser satisfeita por qualquer lista de n inteiros que comece com os k elementos de c . Para que o retrocesso seja eficaz, deve haver uma maneira de detectar essa situação, pelo menos para alguns candidatos c , sem enumerar todos aqueles m n - k n -tuplos.

Por exemplo, se F é a conjunção de vários predicados booleanos, F = F [1] ∧ F [2] ∧… ∧ F [ p ] , e cada F [ i ] depende apenas de um pequeno subconjunto das variáveis x [1 ],…, X [ n ] , então o procedimento de rejeição poderia simplesmente verificar os termos F [ i ] que dependem apenas das variáveis x [1],…, x [ k ] e retornar verdadeiro se algum desses termos retornar falso . Na verdade, rejeitar precisa apenas verificar os termos que dependem de x [ k ], uma vez que os termos que dependem apenas de x [1],…, x [ k - 1] terão sido testados mais acima na árvore de pesquisa.

Assumindo que rejeitar seja implementado como acima, então, aceitar ( P , c ) precisa apenas verificar se c está completo, ou seja, se tem n elementos.

Em geral, é melhor ordenar a lista de variáveis ​​de modo que comece com as mais críticas (ou seja, aquelas com menos opções de valor ou que tenham um impacto maior nas escolhas subsequentes).

Pode-se também permitir que a próxima função escolha qual variável deve ser atribuída ao estender um candidato parcial, com base nos valores das variáveis ​​já atribuídas por ela. Melhorias adicionais podem ser obtidas pela técnica de propagação de restrição .

Além de reter os valores mínimos de recuperação usados ​​no backup, as implementações de backtracking geralmente mantêm uma trilha variável para registrar o histórico de alteração de valor. Uma implementação eficiente evitará a criação de uma entrada de trilha variável entre duas mudanças sucessivas quando não houver um ponto de escolha, pois o retrocesso apagará todas as mudanças como uma única operação.

Uma alternativa para a trilha da variável é manter um registro de data e hora de quando a última alteração foi feita na variável. O carimbo de data / hora é comparado ao carimbo de data / hora de um ponto de escolha. Se o ponto de escolha tiver um tempo associado posterior ao da variável, não é necessário reverter a variável quando o ponto de escolha é retrocedido, pois ela foi alterada antes de ocorrer o ponto de escolha.

Veja também

Notas

Referências

Leitura adicional

links externos