PAA - Aula9 - Busca Exaustiva (1)
-
Upload
jucimar-oliveira -
Category
Documents
-
view
14 -
download
3
description
Transcript of PAA - Aula9 - Busca Exaustiva (1)
![Page 1: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/1.jpg)
Projeto e Análise de Algoritmos
Força bruta - Busca exaustiva
Prof. Flávio José Mendes Coelho [email protected]
UNIVERSIDADE DO ESTADO DO AMAZONAS�ESCOLA SUPERIOR DE TECNOLOGIA �
NÚCLEO DE COMPUTAÇÃO - NUCOMP
![Page 2: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/2.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca exaustiva
Busca em profundida em grafos (DFS)
Busca em largura em grafos (BFS)
Nesta aula...
2
![Page 3: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/3.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 3
Busca exaustiva
![Page 4: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/4.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Muitos problemas importantes pedem a descoberta de um elemento com uma propriedade especial dentro de um espaço de busca que cresce exponencialmente ou pior com o tamanho da instância.
Em geral, tais elementos são objetos
combinatórios tais como permutações, combinações e subconjuntos de um conjunto.
Busca exaustiva
4
![Page 5: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/5.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Muitos deste problemas são problemas de otimização combinatória: descobrir um elemento que maximiza ou minimiza alguma característica desejável.
Definição. Busca exaustiva (enumeração
explícita) é a aplicação da abordagem de força bruta para problemas de otimização combinatória.
Busca exaustiva
5
![Page 6: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/6.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
A estratégia de busca exaustiva é simples: 1. Construa todos os objetos combinatórios do
espaço de busca E para a instância I do problema P.
2. Escolha o elemento ótimo de E para I.
Como E cresce exponencialmente com o tamanho de P, empregar esta estratégia para instâncias não moderadas de P é computacionalmente inviável.
Busca exaustiva
6
![Page 7: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/7.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Alguns problemas importantes de otimização combinatória:
• PCV – Problema do Caixeiro Viajante (Traveling Salesman Problema – TSP)
• Problema da Mochila (Knapsack Problem) • Problema da alocação
(Assignment Problem)
Busca exaustiva
7
![Page 8: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/8.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Definição. Dadas n cidades com distâncias conhecidas entre cada par de cidades, encontrar o tour mais curto que passe por todas as cidades exatamente uma vez antes de retornar a cidade de origem.
Definição alternativa. Encontrar o circuito Hamiltoniano mais curto em um grafo conectado e ponderado.
PCV
8
![Page 9: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/9.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
PCV
9
2 b
d c
a
7
4 8
5
3
![Page 10: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/10.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Solução exaustiva 1. Construa o conjunto de todas as
permutações (tours) das n–1 cidades. 2. Encontre neste conjunto uma permutação
com o custo mínimo.
PCV
10
![Page 11: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/11.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Tour a – b – c – d – a
a – b – d – c – a
a – c – b – d – a
a – c – d – b – a
a – d – b – c – a
a – d – c – b – a
Custo 2 + 3 + 7 + 5 = 17
2 + 4 + 7 + 8 = 21
8 + 3 + 4 + 5 = 20
8 + 7 + 4 + 2 = 21
5 + 4 + 3 + 8 = 20
5 + 7 + 3 + 2 = 17
PCV
11
2 b
dc
a
7
4 8
5
3
T(n) = (n–1)!
T(n)∈Θ(n!)
![Page 12: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/12.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Definição. Dados n objetos, seus pesos w1, w2, …, wn, seus valores v1, v2, …, vn e uma mochila (knapsack) de capacidade W, encontrar o subconjunto mais valioso de objetos que caibam na mochila.
Problema da mochila
12
![Page 13: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/13.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Problema da mochila
13
mochila
W = 10
w = 3 v = R$12
w = 4 v = R$40
w = 5 v = R$25
w = 7 v = R$42
objeto 1 objeto 2 objeto 3 objeto 4
![Page 14: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/14.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Solução exaustiva 1. Construa todos os subconjuntos do
conjunto de n objetos dados, calculando o peso total de cada subconjunto.
2. Encontre um subconjunto viável com o valor mais elevado entre eles.
Problema da mochila
14
![Page 15: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/15.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
1 ∅ 0 R$0
2 {1} 7 R$42
3 {2} 3 R$12
4 {3} 4 R$40
5 {4} 5 R$25
6 {1, 2} 10 R$36
7 {1, 3} 11 inviável
8 {1, 4} 12 inviável
9 {2, 3} 7 R$52
10 {2, 4} 8 R$37
11 {3, 4} 9 R$65
12 {1, 2, 3} 14 inviável
13 {1, 2, 4} 15 inviável
14 {1, 3, 4} 16 inviável
15 {2, 3, 4} 12 inviável
16 {1, 2, 3, 4} 19 inviável
Problema da mochila
15
# Subconjunto Peso Total Valor Total
mochila
W = 10
w = 4 v = R$40 objeto 3
w = 5 v = R$25 objeto 4
![Page 16: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/16.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Como o número de subconjuntos de um conjunto de n elementos é 2n, a busca exaustiva leva a um algoritmo Ω(2n).
Tanto para o PCV quanto para a mochila, a busca exaustiva leva a algoritmos extremamente ineficientes.
Estes problemas são chamados de problemas NP–difícil.
Problema da mochila
16
![Page 17: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/17.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Definição. Dados m pessoas e n tarefas, cada pessoa executando uma tarefa a um custo cij (1 ≤ i ≤ m, 1 ≤ j ≤ n). Determinar a alocação de pessoas a tarefas de custo mínimo.
Problema da alocação
17
![Page 18: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/18.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Problema da alocação
18
Pessoa 1 9 2 7 8 Pessoa 2 6 4 3 7 Pessoa 3 5 8 1 8
Pessoa 4 7 6 9 4
Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4
![Page 19: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/19.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Solução exaustiva 1. Construa o conjunto de todas as
permutações de pessoas onde a i-ésima pessoa executa a i-ésima tarefa, calculando o custo total de cada permutação.
2. Encontre a permutação de custo mínimo.
Problema da alocação
19
![Page 20: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/20.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Os algoritmos de caminhamento em grafos busca em profundidade (depth-first search - DFS) e busca em largura (breadth-first search - BFS) podem ser admitidos como algoritmos de busca exaustiva.
Busca em profundidade e busca em largura em grafos
20
![Page 21: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/21.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Ideia: o algoritmo caminha no grafo buscando alcançar o seu vértice mais distante (profundo), sempre que possível. Quando alcança, volta para o vértice anteriormente visitado e segue outro caminho, da mesma maneira.
Descobre no grafo uma árvore de busca em profundidade (árvore geradora).
21
Busca em profundidade
![Page 22: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/22.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Cada vértice inicia branco.
22
Busca em profundidade
![Page 23: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/23.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Cada vértice visitado (descoberto) fica cinza.
23
Busca em profundidade
![Page 24: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/24.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 24
Busca em profundidade
![Page 25: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/25.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 25
Busca em profundidade
![Page 26: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/26.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 26
Busca em profundidade
![Page 27: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/27.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 27
Busca em profundidade
![Page 28: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/28.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Vértice com adjacentes já visitados fica preto.
28
Busca em profundidade
![Page 29: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/29.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 29
Busca em profundidade
![Page 30: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/30.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 30
Busca em profundidade
![Page 31: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/31.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 31
Busca em profundidade
![Page 32: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/32.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 32
Busca em profundidade
![Page 33: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/33.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 33
Busca em profundidade
![Page 34: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/34.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 34
Busca em profundidade
![Page 35: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/35.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 35
Busca em profundidade
![Page 36: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/36.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 36
Busca em profundidade
![Page 37: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/37.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 37
Busca em profundidade
![Page 38: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/38.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 38
Busca em profundidade
![Page 39: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/39.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 39
Busca em profundidade
![Page 40: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/40.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 40
Busca em profundidade
![Page 41: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/41.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 41
Busca em profundidade
![Page 42: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/42.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 42
Busca em profundidade
![Page 43: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/43.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 43
Busca em profundidade
![Page 44: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/44.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 44
Busca em profundidade
![Page 45: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/45.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 45
Busca em profundidade
![Page 46: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/46.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 46
Busca em profundidade
![Page 47: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/47.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 47
Busca em profundidade
![Page 48: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/48.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 48
Busca em profundidade
![Page 49: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/49.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho 49
Busca em profundidade
![Page 50: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/50.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Árvore de busca em profundidade.
50
Busca em profundidade
![Page 51: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/51.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Elementos do algoritmo Cada vértice: 1. Inicia BRANCO. 2. Muda para CINZA quando é descoberto. 3. Muda para PRETO quando todos seus
vértices adjacentes já foram visitados.
51
Busca em profundidade
![Page 52: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/52.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Elementos do algoritmo A árvore de busca em profundidade é dada por: Gπ = (V, Eπ ), onde Eπ = {(v.π, v)| : v ∈ V e v.π ≠ NULO} e v.π armazena o vértice predecessor de v.
u.d : guarda o “tempo” em que u é descoberto.
u.f : guarda o “tempo” em que u foi “concluído”.
52
Busca em profundidade
![Page 53: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/53.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
DFS(G)paracadavérticeu∈G.Vu.cor=BRANCOu.π=NULOtempo=0paracadavérticeu∈G.Vseu.cor==BRANCODFS-VISITA(G,u)DFS-VISITA(G,u)tempo=tempo+1//descobrevérticebrancou.d=tempou.cor=CINZAparacadavérticev∈G.adj[u]//exploraarestauvsev.cor==BRANCOu.π=vDFS-VISITA(G,v)u.cor=PRETO//pintaudepreto;uestáconcluídotempo=tempo+1u.f=tempo
53
![Page 54: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/54.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
DFS(G)1paracadavérticeu∈G.V2u.cor=BRANCO3u.π=NULO4tempo=05paracadavérticeu∈G.V6seu.cor==BRANCO7DFS-VISITA(G,u)
54
![Page 55: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/55.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
DFS-VISITA(G,u)1tempo=tempo+1//descobrevérticebranco2u.d=tempo3u.cor=CINZA4paracadavérticev∈G.adj[u]//exploraarestauv5sev.cor==BRANCO6u.π=v7DFS-VISITA(G,v)8u.cor=PRETO//pintaudepreto//uestáconcluído9tempo=tempo+110u.f=tempo
55
![Page 56: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/56.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Eficiência de tempo Matriz de adjacência: Θ(|V|2). Lista de adjacência: Θ(|V| + |E|).
56
Busca em profundidade
![Page 57: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/57.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Propriedades da DFS: Todos os vértices são explorados.
Descobre uma floresta de árvores geradoras (Gπ). (árvores de busca em profundidade)
57
Busca em profundidade
![Page 58: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/58.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Aplicações da DFS Contar componentes conexas de um grafo. Verificar se o grafo é acíclico. Descobrir a saída de labirintos. Verificar estruturas de parênteses (d e f). Utilizada em ordenação topológica.
58
Busca em profundidade
![Page 59: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/59.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Ideia em grafos 1. Partindo de um vértice-origem s do grafo, o
algoritmo visita (descobre) todos os vértices a uma distância k = 1 do vértice s.
2. Depois, visita os vértices a uma distância k + 1 de s, e assim por diante, até os vértices mais distantes de s.
Busca em largura
![Page 60: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/60.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
![Page 61: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/61.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Escolha um vértice s de origem.
Busca em largura
s
![Page 62: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/62.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Visite todos os seus adjacentes.
Busca em largura
s
![Page 63: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/63.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Visite todos os seus adjacentes.
Busca em largura
s
![Page 64: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/64.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Visite todos os seus adjacentes.
Busca em largura
s
![Page 65: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/65.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Visite todos os seus adjacentes.
Busca em largura
s
![Page 66: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/66.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Visite todos os seus adjacentes.
Busca em largura
s
![Page 67: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/67.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Pinte s de preto após visitar seus adjacentes.
Busca em largura
s
![Page 68: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/68.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
1
2
3
4s
![Page 69: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/69.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 70: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/70.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 71: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/71.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 72: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/72.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 73: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/73.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 74: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/74.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 75: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/75.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 76: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/76.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 77: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/77.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 78: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/78.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 79: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/79.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 80: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/80.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 81: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/81.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 82: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/82.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 83: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/83.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 84: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/84.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 85: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/85.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
1
2
3
4
5 6
7
8
![Page 86: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/86.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 87: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/87.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 88: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/88.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 89: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/89.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 90: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/90.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 91: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/91.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 92: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/92.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 93: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/93.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 94: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/94.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Busca em largura
s
![Page 95: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/95.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Descobre uma árvore de busca em largura.
Busca em largura
s
![Page 96: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/96.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Elementos do algoritmo Cada vértice: 1. Inicia BRANCO. 2. Muda para CINZA quando é descoberto. 3. Muda para PRETO quando todos seus
vértices adjacentes já foram visitados.
Busca em largura
![Page 97: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/97.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Elementos do algoritmo A árvore de busca é dada por: Gπ = (V, Eπ ), onde Eπ = {(v.π, v)| : v ∈ V e v.π ≠ NULO} e
v.π armazena o vértice predecessor de v.
u.d : acumula a “distância” da origem s até u.
Busca em largura
![Page 98: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/98.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
BFS(G,s)1paracadavérticeu∈G.V–{s}2u.cor=BRANCO3u.d=∞4u.π=NULO5s.cor=CINZA6s.d=07s.π=NULO8Q=ø9ENFILEIRA(Q,s)10enquantoQ≠øfaça11u=DESENFILEIRA(Q)12paracadavérticev∈G.adj[u]13sev.cor==BRANCO14v.cor=CINZA15v.d=u.d+116v.π=u17ENFILEIRA(Q,v)18u.cor=PRETO
![Page 99: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/99.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
BFS(G,s)1paracadavérticeu∈G.V–{s}2u.cor=BRANCO3u.d=∞4u.π=NULO5s.cor=CINZA6s.d=07s.π=NULO
inicialização
![Page 100: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/100.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
BFS(G,s)...8Q=ø9ENFILEIRA(Q,s)10enquantoQ≠ø11u=DESENFILEIRA(Q)12paracadavérticev∈G.adj[u]13sev.cor==BRANCO14v.cor=CINZA15v.d=u.d+116v.p=u17ENFILEIRA(Q,v)18u.cor=PRETO
principal
![Page 101: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/101.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Eficiência de tempo Matriz de adjacência: Θ(|V|2). Lista de adjacência: Θ(|V| + |E|).
Busca em largura
![Page 102: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/102.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Propriedades da BFS: Todos os vértices são explorados.
A busca em largura obtém o caminho mínimo de um vértice origem s até outro vértice qualquer v.
Procedimento BFS constrói uma árvore de busca em largura armazenada em Gπ.
Busca em largura
![Page 103: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/103.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Aplicações da BFS:
Modelo para o algoritmo de Dijkstra para caminho mínimo de origem única e o algoritmo de Prim para árvore geradora mínima.
Busca em largura
![Page 104: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/104.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Força bruta é simples, mas ineficiente para instâncias de tamanho significativo.
Busca exaustiva é uma estratégia força bruta para problemas de otimização combinatória (ou caminhamento em certas estruturas).
Estratégia de busca exaustiva: gere todos os objetos combinatórios do problema e selecione um que satisfaça as restrições do problema.
Conclusões
104
![Page 105: PAA - Aula9 - Busca Exaustiva (1)](https://reader030.fdocumento.com/reader030/viewer/2022020211/577c7f301a28abe054a39384/html5/thumbnails/105.jpg)
UEA/EST/NUCOMP – Projeto e Análise de Algoritmos – Prof. Flávio José M. Coelho
Bibliografia
• A. Levitin. Introduction to the Design and Analysis of Algorithms. 3rd edition. Addison-Wesley, 2007.
• T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.
105