pré-Requisitos :
- a Recursividade
- Complexidade de Análise
Backtracking é um algorítmico-técnica para solução de problemas recursivamente por tentar construir uma solução de forma incremental, uma peça de cada vez, retirando as soluções que não satisfaçam as restrições do problema em qualquer ponto do tempo (por tempo, aqui, é o que se refere a tempo decorrido até chegar a qualquer nível da árvore de busca).
de acordo com a definição wiki,
o Backtracking pode ser definido como uma técnica algorítmica geral que considera pesquisar cada combinação possível a fim de resolver um problema computacional.
há três tipos de problemas no backtracking–
- problema de decisão-neste, procuramos uma solução viável.Problema de otimização-neste, procuramos a melhor solução.
- problema de enumeração – nisto, encontramos todas as soluções viáveis.
como determinar se um problema pode ser resolvido usando o Backtracking?
Geralmente, cada restrição de satisfação problema que tem claras e bem definidas restrições em qualquer objectivo solução, que constrói incrementalmente candidato para a solução e deixa um candidato (“backtracks”) logo que determina que o candidato não pode, possivelmente, ser concluído para uma solução válida, pode ser resolvido através de Backtracking. No entanto, a maioria dos problemas que são discutidos, pode ser resolvido usando outros conhecidos algoritmos de como a Programação Dinâmica ou Ganancioso Algoritmos em logarítmica, linear, linear, logarítmica do tempo de complexidade, a fim de tamanho de entrada, e, portanto, ofuscar o algoritmo de backtracking em todos os aspectos (desde retrocesso algoritmos são geralmente exponencial no tempo e no espaço). No entanto, ainda restam alguns problemas, que só têm algoritmos de backtracking para resolvê-los até agora. Considere uma situação em que você tem três caixas à sua frente e apenas uma delas tem uma moeda de ouro, mas você não sabe qual. Então, para obter a moeda, você terá que abrir todas as caixas uma a uma. Você vai primeiro marcar a primeira caixa, se ela não contém a moeda, você terá que fechá-la e marcar a segunda caixa e assim por diante até que você encontrar a moeda. Isto é o que backtracking é, que está resolvendo todos os sub-problemas um a um, a fim de alcançar a melhor solução possível.
Considere o exemplo abaixo para entender o Retrocesso abordagem mais formalmente,
Dada uma instância de qualquer problema computacional 
e dados 
correspondente à instância, todas as restrições que devem ser satisfeitas a fim de resolver o problema são representadas por 
. Um algoritmo de backtracking irá então funcionar da seguinte forma:
o algoritmo começa a construir uma solução, começando com um conjunto de solução vazio 
. S = {}
- adicionar a o primeiro movimento que ainda resta (todos os movimentos possíveis são adicionados a um por um). Isso agora cria uma nova sub-árvore
na árvore de busca do algoritmo. - verificar se
satisfaz cada uma das restrições em . Em caso afirmativo, a sub-árvore é ” elegível “para acrescentar mais”crianças”. - Else, the entire sub-tree is useless, so recurss back to step 1 using argument .
- In the event of “eligibility” of the newly formed sub-tree , recurss back to step 1, using argument .
- se a verificação de devolve que é uma solução para a totalidade dos dados . Sair e terminar o programa.
se não, então retornar que nenhuma solução é possível com a corrente e, portanto, rejeitá-la.
diferença entre recursão e retrocesso:
na recursão, a função chama-se até atingir um caso base. No backtracking, usamos a recursão para explorar todas as possibilidades até que obtenhamos o melhor resultado para o problema.
Pseudo-código para retrocesso :
1. Solução de retroacção recursiva.
void findSolutions(n, other params) : if (found a solution) : solutionsFound = solutionsFound + 1; displaySolution(); if (solutionsFound >= solutionTarget) : System.exit(0); return for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); findSolutions(n+1, other params); removeValue(val, n);
2. Encontrando se uma solução existe ou não
boolean findSolutions(n, other params) : if (found a solution) : displaySolution(); return true; for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); if (findSolutions(n+1, other params)) return true; removeValue(val, n); return false;
vamos tentar resolver um problema de Backtracking padrão, problema n-Queen.
A Rainha N é o problema de colocar n rainhas de xadrez em um tabuleiro de xadrez n×n de modo que nenhuma duas rainhas atacam uma à outra. Por exemplo, seguir é uma solução para o problema de 4 Queen.
a saída esperada é uma matriz binária que tem 1s para os blocos onde as rainhas são colocadas. Por exemplo, a seguir está a matriz de saída para a solução de 4 queen acima. Algoritmo de Backtracking :a ideia é colocar rainhas uma a uma em colunas diferentes, começando a partir da coluna mais à esquerda. Quando colocamos uma rainha numa coluna, verificamos se há confrontos com rainhas já colocadas. Na coluna atual, se encontrarmos uma linha para a qual não haja conflito, marcamos esta linha e coluna como parte da solução. Se não encontrarmos essa linha devido a confrontos, voltamos atrás e voltamos falsos.
1) Start in the leftmost column2) If all queens are placed return true3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this (Backtrack) and go to step (a) to try other rows.3) If all rows have been tried and nothing worked, return false to trigger backtracking.
pode referir-se ao artigo sobre o retrocesso | Conjunto 3 (Problema da dama) para a implementação completa da abordagem acima.
Mais Backtracking Problemas:
- Retrocesso | Set 1 (O Cavaleiro de turismo do problema)
- Retrocesso | Set 2 (Ratos em um Labirinto)
- Retrocesso | Set 4 (Subconjunto Soma)
- Retrocesso | Set 5 (m Colorir Problema)
- –> Clique Aqui para Mais