0% acharam este documento útil (0 voto)
11 visualizações7 páginasPesquisa IA Trabalho
psquisa em ia
Enviado por
Bringala JoséDireitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF ou leia on-line no Scribd
0% acharam este documento útil (0 voto)
11 visualizações7 páginasPesquisa IA Trabalho
psquisa em ia
Enviado por
Bringala JoséDireitos autorais
© © All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF ou leia on-line no Scribd
Algoritmos para Grafos_| Indice
Busca em largura
Um algoritmo de busca é um algoritmo que percorre um grafo andando pelos arcos de um
vértice a outro, Depois de visitar a ponta inicial de um arco, 0 algoritmo percorre 0 arco €
visita sua ponta final. Cada arco é percorrido no maximo uma vez.
Ha muitas maneiras de organizar uma busca. Cada estratégia de busca é caracterizada
pela ordem em que os vértices sao visitados. Este capitulo introduz a busca em largura
(= breadth-first search), ou busca BFS, Essa estratégia esta intimamente relacionada com os
conceitos de distancia e caminho minimo.
+ Algoritmo de busca em largura
+ Implementacdo do algoritmo
+ Arvore de busca em largura
+ Desempenho
+ BES versus DES
Algoritmo de busca em largura
‘A busca em largura comeca por um vértice, digamos s, especificado pelo usuario.
O algoritmo visita s, depois visita todos os vizinhos de s, depois todos os vizinhos dos vi-
zinhos, e assim por diante.
O algoritmo numera os vértices, em sequéncia, na ordem em que eles so descobertos (ou
seja, visitados pela primeira vez). Para fazer isso, o algoritmo usa uma fila (= queue) de
vértices. No comeso de cada iteragao, a fila contém vértices que j4 foram numerados mas
tém vizinhos ainda ndo numerados. O proceso iterativo consiste no seguinte:
enquanto a fila nao estiver vazia
retire um vértice v da fila
para cada vizinho w de v
se w nao esté numerado
entao numere w
ponha w na fila
No comeco da primeira iteracao, a fila contém o vértice s, com numero 0, e nada mais.
Exercicios 1 1. & Como comega cada iteragao do algoritmo de busca em largura? (Cuidado! Nao se trata de
descrever as agdes que ocorrem no comeco da iteragao. Trata-se de saber quais as informacoes
dispontveis no inicio de uma iteragdo genérica, antes que a execucdo da iteragdo comece.)
o-
2. & BES em drvore radicada, Faca um rastreamento da busca em largura a partir do vértice
Srvore radicada definida pelos arcos 0-1 0-2 1-3 1-9 1-10 976 5-7 5-8 10~
12 12-13 12-14, Observe que a busca em largura percorre a arvore “por niveis”.
Implementagao do algoritmo
A fila de vértices é manipulada pelas fungées auxiliares QUEUEinit (), QUBUEput (),
QURUFget (), QUEUFempty () e QUEURfree(). A primeira cria uma fila vazia, a segunda co-
loca um vértice na fila, a terceira tira um vértice da fila, a quarta verifica se a fila esta va-
zia, e a Gltima libera 0 espago ocupado pela fila.
A numeragio dos vértices é registrada num vetor num{] indexado pelos vertices. Se v 6 0
k-ésimo vértice descoberto entao num[v} recebe o valor k
static int num(1
© algoritmo de busca em largura. Bla vi
/* A fungao GRAPH!
vetor num[] ordem em que os vértices sdo descobertos. Esta versao
0 impremen
do grafo G que esto ao aleance do v.
da fungao supée que ©
digo inspirado no programa 18.9 de Sedgewick.) */
rafo G 6 representade por listas de adjacéncia. (C6~
void GRAPHbfs( Graph G, vertex s)
4
int ent = 0;
for (vertex v = 0; v < G->V; +)
pum[v] = -1
QUEUEinit( G->v);
num[s] = cntt+;
QUEUEput( 5);
while ('QUEUEempty( )) {
vertex v = QUEUEget( );
for (link a = G->adj[v]; a != NULL; a = a->next)
if (num[a->w] == -1) (
num[a->w] = ent++;
QUEUEpUt ( a->w) ;
)
)
QUEUEfree( );
d
No inicio de cada iteracao valem as seguinte propriedades:
1. todo vértice que esta na fila j4 foi numerado;
2. se um vértice v j4 foi numerado mas algum de seus vizinhos ainda nao foi numerado,
entdo v esta na fila
Observe que a fila foi dimensionada corretamente na linha “QuzvEinit ( G->v)": cada vér-
tice de ¢ entra na fila no maximo uma vez e portanto a fila ndo precisa de mais do que
G->v posicées. Exemplo A. Considere o grafo c definido pelos arcos 0-2 0-3 0-4 1-2 1-
4 2-4 3-4 3-5 4-5 5-1, Suponha que os vértices estio em ordem crescente
de nomes em cada lista de adjacéncia. Submeta A fungdo CRAPHbfs() com
segundo argumento 0. Eis o estado da fila (coluna esquerda) e 0 estado do
vetor num{] (coluna direita) no inicio de cada iteracao
234 o-123-
34 o-123-
45 o-1234
5 o-1234
051234
051234
Basta examinar o vetor num{] para deduzir que os vértices foram descobertos (e portanto
numerados) na ordem 0 23 451
Exemplo B. Neste exemplo, c ¢ 0 grafo ndo-dirigido definido pelas arestas
1 0-2 0-5 2-1 2-3 2-4 3-4 3-5. Suponha que os vértices estio em ordem
crescente de nomes em todas as listas de adjacéncia e submeta o grafo a fun-
G20 GRAPHb£s() com segundo argumento 0. Eis o estado da fila e 0 estado do
vetor num{] no inicio de cada iteracao:
° o----
a oi2--
o12--3
534 012453
34 012453
4 012453
012453
Os vértices foram descobertos (e portanto numerados) na ordem 0
Exercicios 2
1. Faca uma busca em largura a partir do vértice 0 no grafo ndo-dirigido definido pelas are:
O-1 1-2 1-4 2-3 2-4 2-9 3-4 4-5 4-6 4-7 5-6 7-8 7-4. Imagine que o grafo é representado
por sua matriz de adjacéncias e portanto os vizinhos de cada vértice estao em ordem cres-
cente de nomes. Exiba o vetor num[) calculado pela busca. Diga em que ordem os vértices fo-
ram descobertos.
2. Faca uma busca em largura a partir do vértice 0 do grafo nao-dirigido definido — @_
pelas arestas 0-2 2-6 6-4 4-5 5-0 0-7 7-1 T-4 3-4 3-5. Suponha que o grafo ©
6 representado por sua matriz. de adjacéncias. Repita a busca comecando pelo ee
vértice 4 by
3. Cédigo de manipulagao da fila, Escreva o cédigo das fungGes QUBUBinit (), QUEUEput (),
QuEvzyet (), QUBUEenpty () € QUEUELree () de manipulacdo da fila de vértices. Coloque essas
> e prepare um arquivo-interface QuevE.h. [Solucdo]
funcées num mé
4, & [Sedgewick 18.52] Cédigo de manipulagdo da fila incorporado. Reescreva a func&o GRAPAbEs ()
substituindo as invocacées de init (), QUEUEput (), OU
QUBURFree() pelo cédigo apropriado.
get (), QUEVEempty () €
5. Mostre um exemplo em que a fila de vértices chega a conter quase todos os vértices do grafo. 6
7.
& Depois de executar a funcdo Gaartbfs() com argumentos Ge s, seja X 0 conjunto dos
vértices v para os quais num{v) é diferente de -1. Descreva os leques de entrada e de saida
de X.
Escreva uma versio da fungdo GRaPibfs () para grafos representados por matriz de
adjacéncias
Arvore de busca em largura
‘A busca em largura a partir de um vértice s constréi uma Arvor
cada arco v-w percorrido até um vértice w nado numerado é acrescentado a arvore. Essa ar-
vore radicada é conhecida como drvore de busca em largura, ou drvore BFS
demos representar essa arvore explicitamente por um vetor de pais pai]. Basta acrescentar
algumas linhas ao cédigo de GRAPHD£s ():
radicada com raiz s:
BES tree). Po-
static int num[100
static vertex pa[1000];
void GRAPHefs( Graph G, vertex s}
(vertex v = 0; v <
nun(s} =
pals]
QUBUEput (s)5
while (!QUEUemp
NULL? a =
O subgrafo de ¢ representado pelo vetor pal) ¢, de fato, uma drvore radicada pois (1) 0
vetor num{] € uma numeracao topolégica do subgrafo ¢ (2) no maximo um arco do sub-
grafo entra em cada vértice. (Veja abaixo o exercicio Numeragao topoldgica da arvore BFS.)
No inicio de cada iteragao, cada vértice na fila ¢é uma folha da drvore radicada represen-
Exemplo C. Aplique a funcado GRAPHbfs() ao grafo do exemplo A. No fim
da execugao da funcdo, o vetor pat) estard no seguinte estado: &
tada por pat).
O-O-8
vo 0123
paly) 05000 Exemplo D. Aplique a funcdo crapabfs() ao grafo ndo-dirigido do
exemplo B. No fim da execugao da fungao, o vetor pa[] estard no seguinte &
estado: ®
Exercicios 3
10.
. [Sedgewick 18.50, modificado] Faga uma busca em largura a partir do
Estude a figura ao lado (copiada do livro de Sedgwewick e Wayne). Ela *
mostra a construgdo de uma arvore de busca em largura num grafo nao-diri
gido aleatério com 250 vertices. Note como a arvore radicada cresce “em
largura”, atingindo gradualmente vértices cada vez mais distantes da raiz.
vértice 0 no grafo ndo-dirigido definido pelas arestas 8-9 3-7 1-4 7-8 0-5
5-2 3-8 2-9 0-6 4-9 2-6 6-4, Suponha que o grafo é representado por sua
matriz de adjacéncias. Faca uma figura da arvore de busca. Repita o exerci-
cio depois de representar o grafo por listas de adjacéncia e inserir as arestas,
na ordem dada, num grafo inicialmente vazio.
Uma 4rvore de busca em largura é sempre um subgrafo gerador do grafo
submetido a busca?
& Numeragio topolégica da drvore BFS. Mostre que no fim da execugao de
GRAP#bfs () 0 vetor num{] ¢ uma numeracao topolgica da arvore BES repre-
sentada pelo vetor pai]. Para fazer isso, prove os seguintes invariantes: no
inicio de cada iteracdo (1) num‘q} #-1 para cada vértice q da fila e
(2) sun {pat} < num[w) para cada vértice w tal que paiw
Propriedades da fila. No inicio de uma iteragéo qualquer de GRaPitbfs (), seja
apr dys + + a a Sequéncia dos vértices que esto na fila, Mostre que existe
um ndmero positive L tal que rumia,] =Lri para cada i, Agora considere
a Arvore radicada T representada pelo vetor pat] e mostre que
num(u] $ sun[q] para cada u em T que ndo est na fila. Deduza dat que, nO sysmsunpanosene
ag a
inicio de cada iteracdo, num{v]
