PAA Aula 8

Prévia do material em texto

bruno.conceicao@ufop.edu.br
Prof. Bruno César Cota Conceição
Projeto e análise de Algoritmos
 Aula 8
Projeto de algoritmos por Backtracking
Projeto de algoritmos: Backtracking
Projeto de algoritmos: Backtracking
Projeto de algoritmos: Backtracking
Projeto de algoritmos: Backtracking
Me dê a primeira solução que você
encontrar
Projeto de algoritmos: Backtracking
Projeto de algoritmos: Backtracking
Nosso ganho está em não testar toda a árvore. 
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Não é uma solução
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
Estudo de caso: Problema das N rainhas
No backtraking, a ideia é posicionar uma rainha por
linha, e uma linha por vez.
Pseudocódigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Solução inválida, backtracking
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
quando vou expandir pra linha não pode, entao backtracing
Pseudocodigo: Problema das N rainhas
Já testei para todas as linhas e colunas, não encontrando
uma solução, volto para a raiz, e testo para o lado direito, já
que não encontrei nenhuma solução do lado esquerdo...
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Pseudocodigo: Problema das N rainhas
Temos então a nossa solução, e nenhuma das rainhas se atacam.
Nosso ganho está nas outras soluções que não precisamos testar com o backtracking.
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
n é a ordem de grandeza do tabuleiro e também o número de rainhas.
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
n é a ordem de grandeza do tabuleiro e também o número de rainhas.
i é o número de linhas que falta preencher.
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
n é a ordem de grandeza do tabuleiro e também o número de rainhas.
i é o número de linhas que falta preencher.
n-i é as rainhas que já foram posicionadas.
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
n é a ordem de grandeza do tabuleiro e também o número de rainhas.
i é o número de linhas que falta preencher.
n-i é as rainhas que já foram posicionadas.
Queremos contar quantas vezes uma posição é válida e levam uma posição
válida no futuro.
Complexidade: Problema das N rainhas
Como o algoritmo é recursivo, vamos considerar:
n é a ordem de grandeza do tabuleiro e também o número de rainhas.
i é o número de linhas que falta preencher.
n-i é as rainhas que já foram posicionadas.
Queremos contar quantas vezes uma posição é válida e levam uma posição
válida no futuro.
No pior caso, ele vai considerar colocar a rainha em todas as colunas e então
verificar se as outras rainhas atacam a colocada.
Pseudocodigo: Problema das N rainhas
Custo de uma chamada recursiva
Pseudocodigo: Problema das N rainhas
Custo de uma chamada recursiva
Se essa posição é válida, chamamos o algoritmo para resollver o problema considerando
uma rainha a menos:
Pseudocodigo: Problema das N rainhas
Exercício: Verificar que
Pseudocodigo: Problema das N rainhas
Uma dica é:
Pseudocodigo: Problema das N rainhas
Uma dica é:
Desenvolver a recorrência usando alguma estratégia que já vimos...
expansão ou substituição ou teorema mestre ou árvore de recursão para provar.
Pseudocodigo: Problema das N rainhas
Outa coisa é, pensar que é possível melhorar esse
algoritmo, então reflitam sobre isso por favor:
Pensando na complexidade no pior caso, já que ambos
são exponenciais, porém o primeiro é pior.
Referências:
Créditos ao professor Vinícius Dias pelo material disponibilizado.
 LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora
Addison Wesley;
2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.
Introduction to Algorithms. 3a edition. Editora The MIT Press;
3. ERICKSON, Jeffe. Algorithms. 1st edition. June 2019.
Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
4. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.
5. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Editora
McGraw-Hill.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/pageid/0
6. MANBER, Udi. Introduction to Algorithms: A Creative Approach. 1st edition. Editora
AddisonWesley
7. DE, A. et al. [s.l: s.n.]. Disponível em: <http://waltenomartins.com.br/ap_aa_v1.pdf>. Acesso em: 4 out. 2023.