FT 024 - Teoria dos Grafos e Aplicaçõesmagic/ft024/busca_transp.pdf · Introduc¸ao˜ Grafos × M´etodos de Busca Busca em Profundidade Busca em Largura Exerc´ıcios Busca Heur´ıstica

Introduc aoGrafos × Metodos de Busca

Busca em ProfundidadeBusca em Largura

ExercıciosBusca Heurıstica

FT 024 - Teoria dos Grafos e Aplicac oes

Profa. Dra. Elaine Cristina Catapani PolettiAula 05

DMBC/FT/UNICAMP

12 de abril de 2010

Elaine Catapani Disciplina FT 024




Introduc ao





Grafos × Metodos de BuscaTipos de Algoritmos

Grafos × Metodos de Busca


Compreendendo o que sao grafos e arvores como podemosexplorar essas estruturas a fim de buscar uma solucao?

Metodos de Busca

Existem procedimentos para se caminhar pelos nos e arestasde um dado grafo?








Compreendendo o que sao grafos e arvores como podemosexplorar essas estruturas a fim de buscar uma solucao?

Metodos de Busca

Existem procedimentos para se caminhar pelos nos e arestasde um dado grafo?






Algorıtmos de Busca

Tipos de Busca

1 Busca em profundidade (Depth-First Search DFS)2 Busca em largura (Breadth-First Search BFS)3 Busca A∗

4...





Definic aoO Metodo DFSExemplosPropriedadesAplicac oes

Busca em Profundidade

Depth-First Search

O algoritmo DFS realiza uma busca que progride atraves daexpansao do primeiro no (o no raiz) e se aprofunda cada vez mais,ate que o alvo seja encontrado, ou ate que se depare com um nofolha, daı a busca retrocede (backtrack) e recomeca no proximo no.






Figura: Representacao grafica de uma busca DFS







O Metodo DFS

O algoritmo para busca em profundidade marca v (raiz) como visitado;

A seguir toma o vertice w conectado a v, verifica se w e solucao:

se sim, encerra a busca (e indica a solucao que pode sersomente este no ou todo o percurso do no-raiz ate este no),se nao, continua a DFS em w;

Terminando busca em w, o algoritmo toma outro vertice z conectado av ainda nao visitado e executa a busca, se o no for a solucao, encerra oalgoritmo e devolve a solucao, caso contrario prossegue, desta forma,sucessivamente.







Exemplo DFS

Considere o seguinte grafo. Qual a ordem de visitacao dosvertices?







Figura: Ordem de visitacao de verticesElaine Catapani Disciplina FT 024






Exemplo 1

Aplique a busca DFS no grafo partindo de l:







Exemplo 2

Aplique a busca DFS no grafo partindo de l:







Exemplo 3

Aplique a busca DFS no grafo partindo de a:







Propriedades da busca DFS

Efeito backtrack.

Formacao de uma pilha.

A complexidade temporal e O(V + E).

Busca infinita.








Efeito backtrack.



Busca infinita.








Efeito backtrack.



Busca infinita.








Efeito backtrack.



Busca infinita.






Aplicacoes DFS

Aplicacoes da busca DFS

Busca de articulacao

Ordenacao topologica

Identificacao de componentes fortemente conexos






Busca de articulacao - Aplicacoes DFS

Um vertice em um grafo nao direcionado simples e conexo e umaarticulacao se sua remocao torna o grafo resultante desconexo.

Figura: Exemplo de articulacao

Importante, por exemplo, para identificar os pontos frageis de umarede de computadores.






Ordenacao topologica - Aplicacoes DFS

Se um grafo direcionado G = (V,E) nao contem ciclos, ele induzum conjunto parcialmente ordenado tal que para todos osvertices v e w, v < w ⇐⇒ existe um caminho de v ate w em G.

Os vertices de tal grafo podem ser ordenados para obter umasequencia de vertices v1, v2, · · · , vn , onde v i < v j , para i < j .

Importante, por exemplo, para se conhecer a sequencia derequisitos para determinada acao.






Identificacao de componentes fortemente conexos -Aplicacoes DFS

Um grafo direcionado e fortemente conexo se existe um caminho deu ate v e de v ate u para qualquer par distinto de vertices u e v.

Figura: Exemplo de componentes fortemente conexos






Identificacao de componentes fortemente conexos -Aplicacoes DFS





Definic aoO Metodo BFSExemplosPropriedades

Busca em Largura

Breadth-First Search

O algoritmo BFS expande e examina sistematicamente todos os nosde uma arvore atraves de nıveis, em busca de uma solucao.






Figura: Representacao grafica de uma busca BFS






Busca em Largura

O Metodo BFS

O algoritmo para busca em largura marca v (raiz) como visitado;

A seguir toma todos os vertices (filhos) conectados a v,verificando se cada um deles e solucao - se sim, encerra abusca no respectivo no e indica a solucao, se nao, continua aBFS nos filhos dos filhos;

Terminando busca nos filhos dos filhos, o algoritmo toma osfilhos dos filhos dos filhos e executa a busca ate que encerra oalgoritmo ou devolva a solucao.






Busca em Largura

Figura: Ordem de visitacao de verticesElaine Catapani Disciplina FT 024





Busca em Largura

Exemplo 1

Aplique a busca BFS no grafo:






Busca em Largura

Exemplo 2







Busca em Largura

Exemplo 3







Busca em Largura

Propriedades da busca BFS

A busca BFS e completa apenas em arvores com numero finito deramos.

Os nos sao adicionados a uma fila.

A complexidade temporal tambem e proporcional ao numero devertices somado ao numero de arestas do grafo O(V + E).

A complexidade espacial de um algoritmo de busca BFS e maior que ode busca DFS.

O algoritmo BFS encontra a solucao mais rasa em uma arvore (naonecessariamente a melhor).






Busca BFS × Busca DFS

Busca BFS × Busca DFSA diferenca mais marcante entre a BFS e a DFS esta naestrutura de dados auxiliar empregada por uma e pela outra. Abusca BFS usa uma fila (de vertices), e a busca DFS usa umapilha.

A busca DFS visita, tipicamente, todos os vertices do digrafo,enquanto a busca BFS visita apenas os vertices que podem seratingidos a partir do vertice inicial.

A busca DFS e descrita, usualmente, em estilo recursivo,enquanto a busca BFS e descrita em estilo iterativo.

























Busca BFS × Busca DFSComputabilidade - dependendo de como a estrutura de dados eorganizada, um caminho percorrido por busca DFS pode tertamanho infinito, ja a busca BFS encontrara a solucao em umnumero finito de passos se esta existir.

Espaco de memoria e tempo: a busca DFS armazena todos osnos visitados a partir da raiz, ou seja, no maximo o tamanho daarvore, a busca BFS armazena todos os possıveis nosprocessados, desta forma, em termos de espaco e tempo, abusca DFS pode ser mais eficiente.

A busca BFS e completa apenas em arvores com numero finitode ramos.























Exercıcios





Busca HeurısticaBest-First SearchGreedy SearchExemploBusca A ∗

Exemplo

Busca Heurıstica

Busca heurıstica

Estrategias de busca heurıstica utilizam conhecimento especıfico(previo) do problema na escolha do proximo no a ser espandido eaplicam uma funcao de avaliacao a cada no na froneira do espaco deestados.

Classes de Algorıtmos para busca heurıstica

Best-First Search (Busca pela melhor escolha)

Busca com limite de memoria

Busca com melhora iterativa...






Exemplo

Best-First Search

Best-First Search

Busca generica, onde o no de menor custo aparente eexpandido primeiro. Conhecimento provido por uma funcao deavaliacao que retorna um numero que indica qual no deve serexpandido na busca.

Dentre as abordagens basicas temos:

Greedy Search

Algorıtmo A∗






Exemplo

Greedy Search

Greedy Search

Conhecido tambem por busca gulosa e o processo semelhante aquelerealizado pela busca em profundidade com efeito backtracking.

Tenta expandir o no mais proximo do no final com base na estimativafeita pela funcao heurıstica h(n), que e o custo estimado do menorcaminho de um ponto n ate o objetivo;

Custo de busca e minimizado, nao exandindo nos fora do caminho;

Escolhe o caminho mais economico a primeira vista, portanto nao eotima.






Exemplo

Greedy Search

Greedy Search










Exemplo

Greedy Search

Greedy Search










Exemplo

Greedy Search

Greedy Search










Exemplo

Exemplo

De Arad a Bucharest






Exemplo

De Arad a Bucharest






Exemplo

Rota - Busca Gulosa






Exemplo

Busca A∗

O Algoritmo A∗

O algoritmo A∗ desenvolve uma busca que vai de um vertice inicial ate outro,empregando ”heuristica de estimativa”que classifica cada no por umaestimativa da melhor rota. A base do algoritmo e a equacao:

f (n) = g(n) + h(n)

onde:

g(n) distancia do no inicial ate o no n,

h(n) distancia estimada do no n ate o objetivo.






Exemplo

Exemplo

De Arad a Bucharest






Exemplo

De Arad a Bucharest






Exemplo

Rota - Busca A∗


Documents

FT 024 - Teoria dos Grafos e Aplicaçõesmagic/ft024/busca_transp.pdf · Introduc¸ao˜ Grafos × M´etodos de Busca Busca em Profundidade Busca em Largura Exerc´ıcios Busca Heur´ıstica