Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking - Coggle Diagram
Backtracking
Problemas
N Rainhas
colocar N rainhas em um tabuleiro de xadrez NxN sem que elas se ataquem mutuamente, ou seja, nenhuma rainha pode estar na mesma linha, diagonal ou coluna de uma outra
-
tem aplicações em áreas como a teoria da computação, a inteligência artificial e a otimização combinatória.
Circuito Hamiltoniano
-
problema NP-completo, o que significa que não se conhece nenhum algoritmo eficiente que possa resolvê-lo em todos os casos. Porém ele é resolvido utilizado um algoritmo de busca exaustiva como o backtracking, que verifica todas as possiveis permutaçoes de vertices até encpntrar um que satisfaça
Uma das aplicações práticas do problema do circuito Hamiltoniano é na otimização de rotas em sistemas de transporte.
Subset-Sum Problem
busca determinar se existe um subconjunto de um conjunto de números cuja soma é igual a um determinado valor.
dada uma lista de números inteiros, o problema é encontrar um subconjunto desses números cuja soma seja igual a um valor pré-determinado.
A abordagem de programação dinâmica começa criando uma tabela de dimensão (n+1)x(W+1), onde n é o número de elementos na lista e W é a soma desejada. O valor na célula (i, j) da tabela representa a soma dos subconjuntos possíveis dos primeiros i elementos da lista que têm soma igual a j. O valor na célula (n, W) é a solução para o problema, que é 1 se existir um subconjunto com soma igual a W e 0 caso contrário.
exemplo de um problema NP-completo, o que significa que não há algoritmos conhecidos que possam resolvê-lo em tempo polinomial para todas as instâncias do problema.
No entanto, existem algoritmos heurísticos que podem fornecer soluções aproximadas ou sub-ótimas para o problema em um tempo razoável, tornando o problema útil em aplicações práticas como a criptografia e a segurança de informações.
Algoritmo utilizado em problemas de decisão para encontrar uma solução que satisfaça um conjunto de restrições
Busca encontrar todas as soluções possiveis para um problema a partir da construção de uma arvore de possibilidades até encontrar a solução ou descobrir que ela não existe
Cada etapa do backtracking envolve uma escolha, que é seguida por uma verificação se essa escolha leva a uma solução viável ou não.
O backtracking é uma técnica poderosa e versátil, mas pode ser extremamente lenta em problemas de grande escala, uma vez que a árvore de possibilidades pode crescer exponencialmente com o tamanho do problema.