Backtracking: Algoritmo de busca de soluções

Prévia do material em texto

Backtracking 
1
Definição
Backtracking é um algoritmo genérico para encontrar todas(ou algumas) soluções para alguns problemas computacionais, que incrementalmente cria candidatos para a solução, e abandona um candidato assim que determina que o candidato não possibilita a validação da solução.
Tem por característica:
Utiliza o conceito de “solução candidata parcial” (partial candidate solution)
Os passo em direção à solução final são tentados e registrados.
Tem por base algoritmos de tentativa e erro.
Vamos falar sobre o backtracking. 
Backtracking é um algoritmo genérico para encontrar todas ou algumas soluções par alguns problemas computacionais, que incrementalmente cria candidatos para a solução, e abandona um candidato assim que determina que o candidato não possibilita a validação da solução, ou seja, ele trabalha com o conceito de tentativa e erro na busca do melhor candidato para uma solução.
Em que normalmente, o melhor candidato encontrado substituído pelo próximo candidato caso este seja a melhor solução.
2
Problemas mais conhecidos 
Backtracking é aplicável na solução de vários problemas conhecidos, dentre os quais podem-se destacar.
Caixeiro Viajante
Passeio do Cavalo 
8 Rainhas
Os problemas mais conhecidos em que backtracking é aplicado são:
O caixeiro viajante – que consiste em percorrer todas cidades na menor distância possível(menor caminho) e retornando para o ponto de partida.
Passeio do Cavalo – em que você utilizando movimentos do cavalo no xadrez, você deve passar por todas as casas no tabuleiro, sem repetir casa e retornando para casa inicial.
8 rainhas – que é um problema para você posicionar 8 rainhas em um tabuleiro de xadrez de forma que nenhuma esteja alcançável pela outra, ou seja, nenhuma rainha pode estar na mesma linha, coluna ou diagonal de outra.
3
Exemplo - Busca O
Aqui temos um exemplo do backtracking para buscar a letra O na nossa árvore.
4
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Exemplo - Busca O
Pontos positivos
Simplificação de problemas, uma vez que um problema grande é diluído em problemas menores que são resolvidos facilmente.
Sempre irá encontrar uma solução para o problema caso essa solução exista.
Os pontos do uso do backtraking é a simplificação de problemas, pois, uma vez que um problema é diluído em problemas menores estes são resolvidos mais facilmente do que trabalhar com um problema grande como um todo.
E outro ponto positivo, é que ele sempre tenta encontrar uma solução para o problema caso este solução exista na nossa árvore ou conjunto de dados de busca desde que os mesmos estejam ordenados.
25
Pontos negativos
Programas de backtracking , caso não sejam criadas condições de restrição executam sempre uma busca exaustiva e tenderão à exploração combinatória, ou seja, são por natureza combinatórios.
Uma vez que trabalham com o empilhamento de combinações necessitam de uma quantidade grande de memória para serem executados.
Podem crescer exponencialmente de acordo com o tamanho do problema.
Os pontos negativos do backtracking.
Como ele utiliza essa múltipla busca ele acaba trabalhando com exploração combinatória, ou seja, realiza múltiplas combinações para tentar encontrar a melhor solução.
E uma vez que ele trabalha com essa quantidade grande de empilhamentos das combinações, isso acaba exigindo uma grande quantidade de memória para que se possa executar o algoritmo, o que pode fazer com que nossos problemas possa crescer exponencialmente.
26
Referências
Referências
https://pt.stackoverflow.com/questions/103184/o-que-%C3%A9-um-algoritmo-backtracking
http://www.each.usp.br/digiampietri/SIN5013/12-tentativaEErro.pdf
https://pt.slideshare.net/Saymowan/backtracking-14359660
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.3 - Charles Ornelas, Leonardo Rocha, Leonardo Mata e Nivio Ziviani
http://www3.decom.ufop.br/toffolo/site_media/uploads/2011-1/bcc402/slides/10._backtracking.pdf
https://en.wikipedia.org/wiki/Backtracking