Análise de Algoritmos - Aula 16 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Roteiro da Aula 16
1 Busca em Largura
2 Caminho Mı´nimo em Grafos
Algoritmo de Dijkstra
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Busca em Largura
...
ordemBfs = 0;
bfs( s );
...
bfs( int s ){
enfilere(Q,s);
marca[s] = 1;
ordem[v] = ++ordemBfs;
nivel[s] = 0;
while ( !Q.empty() ){
u = desenfilere(Q);
--> Para todo vizinho v de u {
if ( marca[v] == 0 ){
enfilere(Q,v);
marca[v] = 1;
ordem[v] = ++ordemBfs;
nivel[v] = nivel[u] + 1;
}
}
}
}
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Busca em Largura
...
ordemBfs = 0;
bfs( s );
...
bfs( int s ){
enfilere(Q,s);
marca[s] = 1;
ordem[v] = ++ordemBfs;
nivel[s] = 0;
while ( !Q.empty() ){
u = desenfilere(Q);
--> Para todo vizinho v de u {
if ( marca[v] == 0 ){
enfilere(Q,v);
marca[v] = 1;
ordem[v] = ++ordemBfs;
nivel[v] = nivel[u] + 1;
}
}
}
}
Qual e´ a complexidade?
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo em Grafos
• Entrada: Dado um grafo G = (V, E), com pesos positivos
nas arestas, e dois ve´rtices s e t;
• Sa´ıda: O custo do menor caminho entre s e t. O custo de
um caminho e´ a soma dos pesos das arestas;
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
t
Como resolver isso eficientemente?
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
5
1
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
5
1
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
5
1
2
5
3
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
5
1
2
5
3
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
4
1
2
5
3
3
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
4
1
2
5
3
3
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
5
2
9
2
1
3
4
7 8
54
2 8
3
1
2
5
1
4
2
1
1 7
4
9
6
s
4
1
2
4
3
3
6
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Estruturas para Grafos
• Usaremos um Heap para guardar ve´rtices de um Grafo
durante o algoritmo Dijkstra, portanto um ve´rtice sera´:
typedef struct {
int d; /* cota superior para dijkstra */
int h; /* h == 0, vertice fora do heap
h > 0, vertice no heap
h < 0, vertice ja´ calculado */
} vertex;
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Fila de Prioridades e Heap
Operac¸o˜es:
• Inserir elemento no conjunto H;
• Extrair o menor elemento de H;
• Atualizar o valor de um elemento de H.
• insertUpdate( H, i );
• i = extractMin( H ).
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
5
3
8 11 10
10
18
4521 11
Propriedade do Heap:
O valor de todo no´ e´ maior ou igual
que o valor de seu pai
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
5
3
8 11 10
10
18
4521 11
• Vetor H[MAXVERTICES];
• int heapSize; /* # de elementos no heap */
• H: [−1, 3, 5, 10, 8, 18, 11, 10, 21, 11, 45, · · · ];
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
5
3
8 11 10
10
18
4521 11
• H: [−1, 3, 5, 10, 8, 18, 11, 10, 21, 11, 45, · · · ];
#define LEFT(i) ((i)<<1) /* filho esquerdo */
#define RIGHT(i) (((i)<<1)|1) /* filho direito */
#define PAI(i) ((i)>>1) /* pai */
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
vertex vert[MAXVERTICES];
...
void insertUpdate( int* H, int v ){
int i = vert[v].h; /* update */
if ( i == 0 ) i = heapSize++; /* insert */
while ( i > 1 && vert[H[PAI(i)]].d > vert[v].d ){
H[i] = H[PAI(i)];
vert[H[PAI(i)]].h = i;
i = PAI(i);
}
H[i] = v;
vert[v].h = i;
}
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
int extractMin( int* H ){ /* assume heapSize > 0 */
int l,r;
int ret = H[1]; /* coloca u´ltimo na raiz */
H[1] = H[heapSize];
vert[H[1]].h = 1;
heapify( H, 1 ); /* heapify corrige o heap */
return ret;
}
Func¸a˜o heapify recursiva, no pro´ximo slide
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementando Heaps usando Vetor
void heapify( int* H, int i ){
int smallest,aux;
int l = LEFT(i), r = RIGHT(i);
if ( l <= heapSize && vert[H[l]].d < vert[H[i]].d )
smallest = l; else smallest = i;
if ( r <= heapSize && vert[H[r]].d < vert[H[smallest]].d )
smallest = r;
if ( smallest != i ){
aux = H[i];
H[i] = H[smallest]; vert[H[smallest]].h = i;
H[smallest] = aux; vert[aux].h = smallest;
heapify( H, smallest );
}
}
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Caminho M´ınimo – Dijkstra
typedef struct { int d,h; } vertex;
vertex vert[MAXVERTICES];
int H[MAXVERTICES];
...
void dijkstra( int s ){
int i; heapSize = 0;
for( i = 0; i < numVert; i++ ){
vert[i].d = MAXINT; vert[i].h = 0; }
vert[s].d = 0; /* vertice fonte */
insertUpdate(H, s );
while ( heapSize > 0 ){
i = extractMin( H ); vert[i].h = -1; /* ja´ calculado */
para cada vizinho v de i {
if ( vert[v].h >= 0 ) /* ainda n~ao calculado */
if ( vert[v].d > vert[i].d + peso(u,v) ){
vert[v].d = vert[i].d + peso(u,v);
insertUpdate( H, v );
}
}
}
}
Quanto custa?
Ana´lise de
Algoritmos
113859
Aula 16
Roteiro
Busca em
Largura
Caminho
Mı´nimo em
Grafos
Algoritmo de
Dijkstra
Implementac¸o˜es para Dijkstra
Estrutura extractMin insertUpdate Dijkstra
de |V | × extractMin+
Dados (|V |+ |E|)× insertUpdate
Array O(|V |) O(1) O(|V |2 + |E|) → O(|V |2)
Heap O(log |V |) O(log |V |) O((|V |+ |E|) log |V |)
Heap de O(log |V |) O(1) (amortizado) O(|V | log |V |+ |E|)
Fibonacci
	Roteiro
	Busca em Largura
	Caminho Mínimo em Grafos
	Algoritmo de Dijkstra