Blog de Helton Duarte

Olá pessoal, estou de volta!!!

Para quem estava com saudades das aulas do “Programando melhor”, venho anunciar a volta com tudo do curso! Estive parado durante um tempo para resolver a migração do blog, além de estabelecer a parceria com a Hostnet, empresa a qual hospeda esse site. No entanto, tenho a alegria de informá-los que mais uma aula está pronta!

Aula 5 – Backtracking

Conteúdo: Explicação a respeito de algoritmos de Backtracking, técnica facilitadora em casos de problemas pesados.

A força bruta pode ser eficiente na resolução de problemas simples na área de computação, devido ao grande poder já presente nos computadores atuais, com média de 2GHz de clock do processador, ou seja, realizando 2 bilhões de operações por segundo! Contudo, existem casos em que a complexidade da situação exige técnicas mais sofisticadas, sendo uma delas o Backtracking!

Backtracking é um método para iterar (percorrer) todas as possíveis configurações em um espaço qualquer. É um algoritmo geral que poderá ser personalizado para cada tipo de aplicação. De modo geral, a solução será um vetor a = (a1, a2, …, a-n), sendo cada elemento a-i selecionado de um conjunto Si. Os exemplos mais comuns, os quais serão mostrados posteriormente, são a criação de permutações e de subconjuntos.

A cada passo do algoritmo, começa-se com uma solução parcial, diga-se a = (a1, a2, …, a-k), e tenta-se aumentá-la, adicionando outro elemento ao seu fim. Após adicioná-lo, é preciso testar se há uma solução completa – se sim, deve-se imprimí-la, contá-la ou qualquer ação necessária. Se não é necessário checar se essa solução parcial é ainda expansível para alguma completa. Se for, continue testando, se não então apague o último elemento de a e teste outra possibilidade para aquela posição. O código é mostrado abaixo:

bool finished = FALSE;          /* Já encontrou todas as soluções? */

backtrack (int a[], int k, data input)

{

int c[MAXCANDIDATES];       /* Candidatos para a próxima posição */

int ncandidates;                         /* Número de candidatos para a próxima posição */

int i;            /* Contador */

if (is_a_solution(a, k, input))

process_solution(a, k, input);

else {

k = k + 1;

construct_candidates (a, k, input, c, &ncandidates);

for (i = 0; i<ncandidates; i++) {

a[k] = c[i];

backtrack(a, k, input);

if (finished) return;             /* Terminar mais cedo */

}

}

}

As sub-rotinas utilizadas no algoritmo serão especificadas abaixo:

• is_a_solution(a, k, input) – Esse função booleana testa se os primeiros k elementos do vetor a são uma solução completa. O último argumento, input, permite-o utilizar informações proveitosas para essa rotina.
• construct_candidates(a, k, input, c, &ncandidates) – Preenche um vetor c com todos os candidatos possíveis para a k-ésima posição de a, dado o conteúdo das primeiras k-1 posições. O número de candidatos retornado é ncandidates e a variável input é novamente para alguma função auxiliar necessária.
• process_solution(a,k) – Esse método apenas imprime, conta ou faz algo necessário para o determinado problema, quando uma solução completa está pronta. A variável auxiliar, input, é desnecessária nessa situação.

Backtracking assegura o acerto por enumerar todas as possilidades sem visitar nunca o mesmo estado, sendo também eficiente. A recursividade promove a elegância e a fácil implementação desse algoritmo, porque o vetor de novos candidatos, c, é alocado com um procedimento recursivo.

As principais aplicações do backtracking são da criação de todos os subconjuntos de um conjunto S e na criação de todas as suas permutações. Os links foram colocados para o Wikipédia para que o post não fique muito grande, ok?

Abaixo seguem os exercícios para o treinamento do assunto (confesso que estão difíceis dessa vez):

• Little Bishops – Nível 2
• 15-Puzzle Problem – Nível 3
• Queue – Nível 2
• Servicing Stations – Nível 3
• Tug of War – Nível 2
• Garden of Eden – Nível 2
• Color Hash – Nível 3
• Bigger Square Please… – Nível 3

PS: Todo o conteúdo desse post e de todo o curso “Programando melhor” é baseado no livro Programming Challenges, de autoria de Miguel Revilla e Steve Skiena e foi permitido o “resumo” e tradução do mesmo pelos próprios autores para a criação desse curso. Além disso os exercícios estão todos disponibilizados no site UVa Online Judge.

Posts interessantes:

• Programando melhor: Revisão
• Programando melhor: Aula 4 – Ordenação
• OBI vem aí!
• Programando melhor: Aula 3 – Strings

Vamos lá, pessoal! Não desistam porque estamos em preparação para a segunda fase da OBI, agora é pra valer! Comentem sobre o que vocês acharam do post e tirem suas dúvidas!

Helton de Melo Duarte

“O SENHOR prova o justo, mas a sua alma aborree o ímpio e o que ama a violência.” Salmos 11.5

This entry was posted on quinta-feira, abril 9th, 2009 at 14:46 and is filed under Programando Melhor. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.