Algoritmo de Backtracking

O que é o algoritmo de retrocesso?

Backtracking é um algoritmo que busca combinações possíveis para resolver problemas computacionais. Ela constrói candidatos incrementalmente e remove aqueles que não satisfazem as restrições dadas. Essa técnica é muito útil em situações em que você tem que escolher uma solução viável entre múltiplos resultados possíveis.

Este algoritmo é considerado melhor e mais eficiente do que a abordagem Brute Force. Ao contrário do Bruteforce, que tenta todas as soluções possíveis, o Backtracking foca em encontrar apenas uma solução final de acordo com o dado restrições. Também economiza tempo e memória desfazendo o último passo (backtrack) e tentando outra opção após chegar a um beco sem saída. Além disso, ele para assim que uma solução válida é encontrada.

Backtracking é uma técnica amplamente usada porque pode resolver problemas complexos sem consumo exaustivo de recursos. É particularmente útil para problemas em que inúmeras restrições devem ser satisfeitas, como Sudoku, problema n queen e agendamento. Ao navegar de forma inteligente por soluções potenciais, o backtracking pode encontrar uma resposta que satisfaça todas as condições. Isso o torna inestimável para tarefas que exigem precisão e eficiência.

Como funciona o algoritmo de retrocesso?

Algoritmos de backtracking são uma técnica de resolução de problemas que envolve encontrar soluções válidas passo a passo. Se as restrições de um passo não satisfazem certas condições, o algoritmo retorna ao passo anterior.

Em seguida, ele continua com outras combinações possíveis que satisfazem as restrições dadas. Como existem inúmeras combinações possíveis, ele seleciona uma das opções mais satisfatórias e resolve o problema sequencialmente. Essa técnica algorítmica é útil quando você precisa resolver uma ou mais opções possíveis. Retirada significa cancelar sua escolha sempre que surgir uma situação que não produza uma solução válida.

O algoritmo de retrocesso tem as seguintes etapas em geral para resolver um problema:

Etapa 1) Inicialização: Comece com uma solução inicial vazia/parcial.

Etapa 2) Seleção: Com base em critérios e restrições específicos, selecione uma opção para estender a solução atual.

Etapa 3) Exploração: Resolva recursivamente considerando o candidato escolhido e avançando no processo de resolução de problemas.

Etapa 4) Verificação de restrição: Verifique se a solução parcial atual viola alguma restrição em cada etapa. Se isso acontecer, volte para a etapa anterior e tente um candidato diferente.

Etapa 5) Rescisão:O processo de retrocesso para quando uma solução válida é encontrada ou todas as combinações são esgotadas.

Etapa 6) Retrocesso: Se a opção atual não resolver o problema dado, ele retorna ao estado anterior. Ele então considera a nova opção para resolver o problema dado.

Etapa 7) Repita: Continue com estas etapas até que o problema seja resolvido ou todas as opções sejam exploradas.

Natureza recursiva do algoritmo de retrocesso

Algoritmos de backtracking são recursivos por natureza. Isso significa que o algoritmo chama a si mesmo com parâmetros diferentes até encontrar uma solução ou testar todas as possibilidades:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Termos comuns relacionados a problemas de retrocesso

Aqui estão alguns termos básicos relacionados à técnica de Backtracking:

Vetor de solução: Representa soluções como n-tuplas, como (X1, X2, …, Xn).
restrições: Regras que limitam valores X, implícitos e explícitos.
Espaço de solução: Todos os valores X válidos que satisfazem restrições explícitas.
Árvore do Espaço de Estado: Representa o espaço da solução como uma árvore.
Espaço de Estado: Descreve caminhos em uma árvore de espaço de estado.
Estado do Problema: Nós na árvore de busca que representam soluções parciais.
Estados de solução: Estados que formam tuplas de soluções válidas em S.
Estados de resposta: Satisfazer restrições implícitas e produzir soluções desejadas.
Nó Promissor: Leva às soluções desejadas e permanece viável.
Nó Não Promissor: Leva a estados inviáveis, não explorados mais profundamente.
Nó ao vivo:Gerado com crianças inexploradas.
E-nó: Nó ativo com geração contínua de filhos.
Nó morto: Nenhuma expansão adicional de todos os filhos gerados.
Geração de nó em profundidade: Usa o último nó ativo como o próximo nó E.
Função de delimitação: Maximiza ou minimiza B(x1, x2, …, Xa) para otimização.
Árvores estáticas: Formulação de árvore independente da instância do problema.
Árvores dinâmicas: A formulação da árvore varia de acordo com a instância do problema.

Quando usar um algoritmo de retrocesso?

Podemos escolher a técnica de Backtracking para resolver um problema complexo quando:

Existem muitas opções: Backtracking é adequado se muitas opções existirem em cada etapa do processo de resolução de problemas. Essas opções podem estar relacionadas à seleção de itens e movimentos.
Nenhuma escolha melhor clara:Quando não há informações suficientes para determinar a melhor escolha entre as opções disponíveis, um algoritmo de Backtracking pode ser utilizado.
A decisão leva a mais escolhas: Você pode escolher o técnica de retrocesso para rever escolhas sistematicamente.
É preciso explorar todas as soluções possíveis: O retrocesso explora sistematicamente todas as soluções tomando uma série de decisões baseadas umas nas outras.

Tipos de problemas de retrocesso

Há três tipos de problemas em algoritmos de backtracking: problemas de decisão, problemas de otimização e problemas de enumeração. Vamos aprender sobre eles abaixo.

Problema de decisão: Neste tipo de problema, o objetivo é determinar se existe uma solução viável. Verificamos as respostas “sim” e “não”. Por exemplo, o problema das n-rainhas. É um problema de decisão que examina a probabilidade de colocar n rainhas em um tabuleiro de xadrez n × n sem atacar umas às outras.
Problema de otimização: Em problemas de otimização, o objetivo é encontrar a melhor solução possível entre muitas opções. Isso pode envolver determinar os valores máximo e mínimo de uma determinada função ou variável. Por exemplo, considere o problema da mochila, onde o objetivo é maximizar o valor total dos itens na bolsa, respeitando seu limite de peso.
Problema de enumeração: Seu objetivo é encontrar todas as soluções possíveis para um dado problema. Listamos todas as opções válidas sem nenhuma omissão. Um exemplo seria gerar todas as combinações de letras possíveis de um dado conjunto de caracteres.

Aplicações de Backtracking e Exemplos

Existem várias aplicações de Backtracking. Algumas delas são explicadas abaixo com seu pseudocódigo.

Sudoku Solver: Este problema contém uma subgrade 3×3 com números duplicados. A técnica de backtracking mostrará que a solução retorna falso, indicando a necessidade de um posicionamento de número diferente.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

Problema N-Rainha:A abordagem de retrocesso determina como apresentar as rainhas em um tabuleiro de xadrez N × N para que nenhuma delas ameace uma à outra.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

Problema de soma de subconjunto:É usado para encontrar o subconjunto de números de um determinado conjunto que soma uma determinada soma alvo.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

Problema do Ciclo Hamiltoniano: O retrocesso pode ser aplicado para encontrar um passeio fechado em um gráfico que visita cada vértice exatamente uma vez.
Problema do Rato no Labirinto:A técnica de retrocesso é usada para encontrar o caminho de um rato do ponto inicial do labirinto até a saída.

Vantagens e desvantagens do algoritmo de retrocesso

Vantagens do Algoritmo de Backtracking

Técnicas de backtracking são usadas para resolver problemas complexos. Elas têm muitas vantagens, como:

A técnica de retrocesso é eficiente para lidar com restrições.
Este método é bom para resolver problemas de otimização.
A técnica funciona para vários tipos de problemas.
Este procedimento pode ajudar a revisar todas as soluções possíveis.
Como ele retrocede, ele economiza mais memória do que a técnica de força bruta.

Desvantagens do Algoritmo de Backtracking

Técnicas de backtracking também têm algumas limitações, como complexidade de tempo. Essa técnica tem as seguintes desvantagens:

Não há solução garantida.
É mais lento por causa de muitas combinações.
Possui alta complexidade de tempo devido às muitas possibilidades.
Não é adequado para restrições de tempo real, pois encontrar a melhor solução pode levar muito tempo.
A eficiência depende do nível de complexidade do problema.

Diferença entre Backtracking e Recursão

Recursão	Retrocedendo
Chama a si mesmo até que o caso base seja alcançado.	Usa recursão para revisar todas as possibilidades até que o melhor resultado viável seja encontrado.
Abordagem de baixo para cima.	Abordagem de cima para baixo.
Nenhum valor é descartado.	Soluções inviáveis são rejeitadas.

Conclusão

Backtracking é uma estratégia algorítmica útil para resolver problemas complexos explorando sistematicamente soluções viáveis e retrocedendo quando necessário. Podemos esperar que as técnicas de retrocesso melhorem com melhorias no poder computacional e na eficiência algorítmica. Esses avanços permitirão que eles enfrentem problemas maiores e mais complexos de forma eficiente.

Além disso, modelos de aprendizado de máquina podem orientar decisões de retrocesso com base em padrões aprendidos anteriormente.

Todas essas inovações tecnológicas revolucionarão os algoritmos de retrocesso, tornando-os uma ferramenta poderosa e versátil para abordar problemas complicados em vários domínios.