Implementação do algoritimo tentativa e erro

Tentativa e Erro (Backtracking)
Norton T. Roman

Apostila baseada no trabalho de Delano M. Beder, David Matuszek e Nivio Ziviani

Tentativa e Erro


Suponha que você tem que tomar uma série de decisões dentre várias possibilidades, onde


Você não tem informação suficiente para saber o que escolher Cada decisão leva a um novo conjunto de escolhas Alguma seqüência de escolhas (possivelmente mais que uma) pode ser a solução para o problema







Tentativa e erro é um modo metódico de tentar várias seqüências de decisões, até encontrar uma que funcione

Tentativa e Erro


Técnica de solução de problemas


Usada quando se quer achar soluções para problemas para os que não se conhece uma regra fixa de computação Escolher uma operação plausível; Executar a operação com os dados; Se a meta não foi alcançada, repita o processo até que se atinja a meta ou se evidencie a insolubilidade do problema.



Passos
 



Tentativa e Erro


Tentativa e erro é uma técnica que utiliza recursividade


A recursividade pode ser usada para resolver problemas cuja solução é do tipo tentar todas as alternativas possíveis.



Idéia para algoritmos tentativa e erro é decompor o processo em um número finito de sub­tarefas parciais (expressas de forma recursiva).


Explorá­las exaustivamente A construção de uma solução é obtida através de tentativas (ou pesquisas) da árvore de sub­tarefas.



Tentativa e Erro


O processo de tentativa gradualmente constrói e percorre uma árvore de sub­tarefas.

Tentativa e Erro


Funcionamento:


Passos em direção à solução final são tentados e registrados em uma estrutura de dados; Caso esses passos tomados não levem à solução final, eles podem ser retirados e apagados do registro.





A busca na árvore de soluções pode crescer rapidamente (exponencialmente)


Necessário usar algoritmos aproximados ou heurísticas que não garantem a solução