Algoritmo Tentativa e Erro

Tentativa e Erro
A ideia para os algoritmos de tentativa e erro consiste em decompor o processo em um número finito de sub tarefas parciais que devem ser exploradas exaustivamente. O processo geral pode ser visto como um processo de pesquisa ou de tentativa que gradualmente constrói e percorre uma árvore de sub tarefas.

Definição
A Tentativa e Erro é uma Técnica de solução de problemas usada quando se quer achar soluções para problemas, que não se conhece uma regra fixa de computação. Deve-se 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. A Tentativa e erro é uma técnica que utiliza recursividade a qual pode ser usada para resolver problemas cuja solução é do tipo tentar todas as alternativas possíveis.

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 exponencialmente, é Necessário usar algoritmos aproximados ou heurísticas que não garantem a solução ótima mas são rápidas.

Um algoritmo de tentativa e erro verifica, se a possibilidade é a resposta, retorne “sucesso” se a possibilidade não for resposta, e não houver outra a ser testada a partir dela, retorne “falha”.

Exemplo
Dada uma mochila com capacidade C, e n objetos com peso pi (i=1…n), o objetivo é preencher a mochila com o maior peso total, respeitando a capacidade C.
Suponha uma mochila com capacidade de 15 kg e objetos de peso 12 kg, 2 kg, 4 kg e 8 kg; Este problema possui mais que uma solução ótima, ou seja, possui soluções ótimas equivalentes: • 12 kg + 2 kg; • 8 kg + 2 kg + 4 kg.
Uma solução inviável seria: • 12 kg + 4 kg.