Backtracking:uma técnica sistemática de solução de problemas

A troca de retorno é uma poderosa técnica algorítmica usada para resolver problemas que envolvem a busca de uma solução entre um grande número de possibilidades. Funciona construindo incrementalmente soluções candidatas e abandonando ("retrocesso") um candidato assim que determinar que o candidato não pode levar a uma solução válida. Pense nisso como uma maneira inteligente e estruturada de realizar uma pesquisa de profundidade em uma árvore de decisão.

Idéias -chave:

* Edifício incremental: A troca de trilhas constrói soluções passo a passo, adicionando uma peça de cada vez.
* poda (satisfação da restrição): A cada etapa, ele verifica se a solução parcial atual satisfaz as restrições do problema. Caso contrário, abandona imediatamente esse caminho e remonta ao ponto de decisão anterior. Esse passo de poda reduz drasticamente o espaço de pesquisa.
* Recursão (frequentemente): O backtracking é frequentemente implementado usando funções recursivas, onde cada chamada recursiva representa uma escolha ou etapa no processo de construção de soluções.
* Árvore de decisão: Você pode visualizar o processo de pesquisa como uma árvore de decisão, onde cada nó representa um estado (solução parcial) e as bordas representam opções ou ações. A trilha de volta explora esta árvore de uma maneira mais aprofundada.

como funciona (algoritmo geral):

1. comece com uma solução vazia (ou parcialmente inicializada).
2. Faça uma escolha (explore um ramo): Selecione um possível valor ou ação para estender a solução atual.
3. Verifique a validade:
* Se a solução for válida (satisfaz restrições):
* A solução está completa?
* Sim: Devolver a solução.
* Não: Chame recursivamente a função de retrocesso para fazer outra escolha e continuar construindo a solução.
* Se a solução for inválida (viola restrições):
* backtrack: Descanse a última escolha e tente uma diferente. Se todas as opções tiverem sido tentadas nesse nível, volte para o nível anterior.
4. Nenhuma solução: Se todas as opções possíveis foram esgotadas sem encontrar uma solução válida, indique que nenhuma solução existe.

Analogia:resolvendo um labirinto

Imagine que você está resolvendo um labirinto. Você começa na entrada e experimenta caminhos diferentes.

* Avançar: Você faz uma "escolha" movendo um caminho.
* bom caminho (válido): Se o caminho parece estar levando à saída, você continua.
* beco sem saída (inválido): Se você chegar a um beco sem saída, você "volta" refazendo suas etapas para o último cruzamento (ponto de decisão) e tenta um caminho diferente.
* Resolvido: Se você chegar à saída, encontrou uma solução.

casos de uso comum na programação:

* Problemas de satisfação de restrição (CSPs): Problemas em que o objetivo é encontrar um conjunto de valores para variáveis ​​que satisfazem um conjunto de restrições.
* N-Queens Problema: Colocando N Chess Queens em um tabuleiro de xadrez NXN para que não haja duas rainhas.
* SUDOKU SOLVER: O preenchimento de uma grade 9x9 com dígitos para que cada linha, coluna e subgrade 3x3 contenha todos os dígitos de 1 a 9.
* Coloração de mapa: Atribuir cores às regiões em um mapa para que não haja duas regiões adjacentes a mesma cor.
* Problemas de otimização combinatória: Encontrar a melhor solução de um grande conjunto de possíveis combinações.
* Problema de vendedor viajante (TSP): Encontrar a rota mais curta possível que visita cada cidade em uma lista e retorna à cidade inicial (o retorno pode ser usado para pequenas instâncias, mas outros algoritmos são mais eficientes para instâncias maiores).
* Problema de mochila: Determinando o subconjunto mais valioso de itens que podem se encaixar em uma mochila com uma capacidade de peso limitada.
* Soma do subconjunto Problema: Encontrar um subconjunto de um conjunto de números que resumem um determinado valor de destino.
* Análise de análise e sintaxe:
* gramáticas sem contexto: O retorno pode ser usado em analisadores para experimentar diferentes derivações de uma frase até que uma árvore de análise válida seja encontrada.

Exemplo:N-Queens Problem (simplificado)

Vamos ilustrar o problema N-Queens com n =4 (uma placa 4x4).

`` `Python
def is_safe (placa, linha, col):
"" "" Verifica se colocar uma rainha no quadro [linha] [col] está segura. "" "
# Verifique a mesma coluna
para eu em alcance (linha):
Se a placa [i] [col] ==1:
retornar falso

# Verifique a diagonal superior esquerda
para i, j em zip (alcance (linha -1, -1, -1), alcance (col -1, -1, -1)):
Se a placa [i] [j] ==1:
retornar falso

# Verifique a diagonal superior direita
para i, j em zip (alcance (linha -1, -1, -1), intervalo (col + 1, 4)):
Se a placa [i] [j] ==1:
retornar falso

retornar verdadeiro


def resolve_n_queens_util (placa, linha):
"" "" Função auxiliar recursiva para resolver o problema da n-Queens. "" ""
Se linha ==4:# todas as rainhas forem colocadas com sucesso
retornar verdadeiro

Para Col em Range (4):
se is_safe (placa, linha, col):
Board [Linha] [col] =1 # Coloque a rainha

Se resolver_n_queens_util (placa, linha + 1):# coloque recursivamente a próxima rainha
retornar verdadeiro

placa [linha] [col] =0 # backtrack:remova a rainha se não levar a uma solução

retornar false # nenhuma solução encontrada para esta linha


def resolve_n_queens ():
"" "Resolve o problema n-reque para n =4." ""
placa =[[0 para _ no intervalo (4)] para _ em intervalo (4)] # inicialize uma placa vazia

Se não for resolvido_n_queens_util (placa, 0):
print ("Solução não existe")
retornar

# Imprima a solução
para linha no quadro:
Imprimir (linha)


SOLVE_N_QUEENS ()
`` `

Explicação do Código:

1. `is_safe (placa, linha, col)`: Verifica se é seguro colocar uma rainha em `Board [Row] [col]`. Ele verifica conflitos na mesma coluna e diagonais.
2. `solve_n_queens_util (placa, linha)`:
* Caso base: `Se linha ==4:` Se atingimos a última linha (todas as rainhas colocadas), temos uma solução, então retorne 'true`.
* iteração: Faça um loop através de cada coluna na linha atual (`para colas no intervalo (4)`).
* Verifique a segurança: `Se is_safe (placa, linha, col):` Se for seguro colocar uma rainha nesta coluna:
* Coloque a rainha: `placa [linha] [col] =1`
* CHAMADA RECURSIVA: `Se resolver_n_queens_util (placa, linha + 1):` Tente recursivamente colocar a próxima rainha na próxima linha. Se essa chamada recursiva retornar `True`, significa que uma solução foi encontrada a partir deste ponto, por isso retornamos também.
* backtrack: `placa [linha] [col] =0` se a chamada recursiva retornar` falsa` (nenhuma solução foi encontrada), nós * desfazemos * a colocação da rainha (backtrack) e tentamos a próxima coluna na linha atual.
* Nenhuma solução nesta linha: `Return false` se tentamos todas as colunas na linha atual sem encontrar uma solução, significa que não há posicionamento válido das rainhas, então retornamos 'false`.
3. `solve_n_queens ()`:
* Inicializa a placa.
* Chama `solve_n_queens_util` para iniciar o processo de backtracking.
* Imprime a solução se for encontrado.

Vantagens do retorno:

* Pesquisa sistemática: Garantem encontrar uma solução se existir (pesquisa exaustiva).
* poda: Evita explorar ramos desnecessários do espaço de pesquisa, tornando-o mais eficiente do que uma abordagem de força bruta.
* Simplicidade conceitual: A idéia principal é relativamente fácil de entender.

Desvantagens do retorno:

* complexidade do tempo: Ainda pode ter complexidade de tempo (exponencial no pior caso) para grandes instâncias de problemas, pois pode explorar muitos becos sem saída.
* Complexidade do espaço: Pode exigir memória significativa, especialmente para recursão profunda.

Considerações importantes para aplicar backtracking:

* Restrições: Defina claramente as restrições do problema.
* Escolha da ação: Considere cuidadosamente como fazer escolhas em cada etapa.
* Estratégia de poda: Desenvolva uma estratégia de poda eficiente para eliminar os candidatos inválidos o mais cedo possível. Isso é crucial para o desempenho.
* Estrutura do problema: O backtracking funciona melhor para problemas, onde as soluções parciais podem ser facilmente avaliadas quanto à validade.

Em resumo, o retrocesso é uma técnica versátil de solução de problemas que pode ser aplicada a uma ampla gama de problemas. Ao explorar sistematicamente soluções possíveis e podando o espaço de pesquisa, ele oferece uma abordagem poderosa para encontrar soluções que atendam a restrições específicas. Embora possa ter complexidade de tempo no pior dos casos, a satisfação cuidadosa da restrição e a poda eficiente podem melhorar significativamente seu desempenho.