The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. A conclusão é feita incrementalmente, por uma sequência de etapas de extensão do candidato.Conceitualmente, os candidatos parciais são representados como os nós de uma estrutura de árvore, a árvore de busca 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 backtracking atravessa esta árvore de pesquisa recursivamente, da raiz para baixo, em profundidade-primeira ordem. Em cada nó c, o algoritmo verifica se c pode ser completado para uma solução válida. Se não puder, toda a sub-árvore enraizada em c é saltada (podada). Caso contrário, o algoritmo (1) verifica se o próprio c é uma solução válida, e se assim o reporta 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 dados pelo Usuário.
portanto, a árvore de busca real que é atravessada 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 obter e processar cada nó. Este fato deve ser considerado ao escolher a árvore de busca potencial e implementar o teste de Poda.
PseudocodeEdit
para aplicar o retrocesso a uma classe específica de problemas, deve-se fornecer os dados de P para a instância específica do problema a ser resolvido, e seis processuais parâmetros, de raiz, rejeitar, aceitar, primeiro, próximo, e de saída. Estes procedimentos devem tomar como parâmetro os dados de instância P e devem fazer o seguinte::
- root (P): devolva o candidato parcial na raiz da árvore de pesquisa.
- rejeito( P, c): return true only if the partial candidate c is not worth completing.
- accept (P, c): retorne verdadeiro se c é uma solução de P, e falso de outra forma.
- primeiro(P,c): gerar a primeira extensão do candidato c.
- next(P,s): gerar a seguinte alternativa extensão de um candidato, após a extensão de s.
- output(P,c): use a solução c de P, conforme apropriado para a aplicação.
o algoritmo de backtracking reduz o problema para o BackTrack(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)
Uso considerationsEdit
A rejeitar procedimento deve ser um valor booleano função que retorna true somente se é certo que, sem a possibilidade de extensão do c é uma solução válida para P. Se o procedimento não é possível chegar a uma conclusão precisa, ele deve retornar false. 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) devolveu falso para cada ancestral t de c na árvore de busca.
por outro lado, a eficiência do algoritmo de backtracking depende de rejeitar o retorno verdadeiro para candidatos que estão tão perto da raiz quanto possível. Se rejeitar sempre retorna falso, o algoritmo ainda vai encontrar todas as soluções, mas será equivalente a uma busca por força bruta.
o procedimento de Aceitação deve retornar verdadeiro se c é uma solução completa e válida para a instância de problema P, e falso caso contrário. Ele pode assumir que o candidato parcial c e todos os seus ancestrais na árvore passaram o teste de rejeição.
o pseudo-código geral acima não assume que as soluções válidas são sempre folhas da árvore de pesquisa potencial. Por outras palavras, admite a possibilidade de uma solução válida para P poder ser alargada de forma a 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 uma única etapa de extensão. A chamada em primeiro lugar(P, C) deve render o primeiro filho de c, em alguma ordem; e a chamada seguinte (P,S) deve retornar o próximo irmão do nó s, nessa ordem. Ambas as funções devem devolver um candidato distinto “nulo”, se a criança solicitada não existir.
em conjunto, as funções raiz, primeira e próxima definem o conjunto de candidatos parciais e a árvore de busca potencial. Eles devem ser escolhidos para que cada solução de P ocorra em algum lugar da árvore, e nenhum candidato parcial ocorre mais de uma vez. Além disso, devem admitir um predicado de rejeição eficiente e eficaz.
os Primeiros a parar variantsEdit
O pseudo-código acima será chamada de saída para todos os candidatos que são a solução para a instância dada P. O algoritmo pode ser modificado para parar depois de encontrar a primeira solução, ou um número especificado de soluções; ou, após testes com um número especificado de parcial de candidatos, ou depois de gastar uma determinada quantidade de tempo de CPU.