Análise de Algoritmos - Aula 17 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Roteiro da Aula 17
1 A´rvore Espalhada Mı´nima
Algoritmo de Prim
Algoritmo de Kruskal e Union-Find
2 Algoritmos Gulosos
3 Algoritmo de Floyd-Warshal
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmo de
Prim
Algoritmo de
Kruskal e
Union-Find
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
A´rvore Espalhada M´ınima
Algoritmo de Prim
...
void prim( int s ){
int i; heapSize = 0;
for( i = 0; i < numVert; i++ ){
vert[i].d = MAXINT; vert[i].h = 0; vert[i].pai = -1; }
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 > peso(i,v) ){
vert[v].d = peso(i,v);
vert[v].pai = i;
insertUpdate( H, v );
}
}
}
}
Quanto custa?
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmo de
Prim
Algoritmo de
Kruskal e
Union-Find
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
A´rvore Espalhada M´ınima
Algoritmo de Kruskal
...
void kruskal(){
A = null;
for( i = 0; i < numVert; i++ ) makeSet( v );
Ordene as arestas por peso;
Para cada aresta (u,v) {
if findSet( u ) != findSet( v ) {
A = A + {(u,v)};
union( u , v );
}
}
}
Como implementar makeSet, findSet e union?
Quanto custa?
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Algoritmos Gulosos - Problema do Troco
• Dijkstra, Prim e Kruskal sa˜o bons exemplos de Algoritmos
Gulosos
Problema do Troco
Dado um nu´mero natural n, calcular o nu´mero m´ınimo de
moedas de valores {1, 5, 10, 25, 100} para devolver um troco de
valor n;
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Algoritmos Gulosos - Problema do Troco
• Dijkstra, Prim e Kruskal sa˜o bons exemplos de Algoritmos
Gulosos
Problema do Troco
Dado um nu´mero natural n, calcular o nu´mero m´ınimo de
moedas de valores {1, 5, 10, 25, 100} para devolver um troco de
valor n;
Problema do Troco Generalizado
Dado um nu´mero natural n e um conjunto de valores
{v1, v2, . . . , vk} de moedas, calcular o nu´mero m´ınimo de
moedas para devolver um troco de valor n;
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Todos os Caminhos M´ınimos – Floyd-Warshall
Como calcular todos os cam´ınhos m´ınimos?
• Dada a matriz de adjaceˆncia: M [i, j] = wij e´ o custo da
aresta (i, j), ou ∞ se na˜o ha´ aresta;
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Todos os Caminhos M´ınimos – Floyd-Warshall
Como calcular todos os cam´ınhos m´ınimos?
• Dada a matriz de adjaceˆncia: M [i, j] = wij e´ o custo da
aresta (i, j), ou ∞ se na˜o ha´ aresta;
• Defina d(i, j, k) como o custo do caminho m´ınimo de i
para j passando apenas por ve´rtices do conjunto
{0, 1, 2, . . . , k}.
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Todos os Caminhos M´ınimos – Floyd-Warshall
i
j
i
j
k
• Ou o caminho que tem custo m´ınimo d(i, j, k) passa por
k, ou na˜o:
• Se na˜o passa, veja que d(i, j, k) = d(i, j, k − 1);
• Se passa, veja que d(i, j, k) = d(i, k, k− 1) + d(k, j, k− 1).
Mas a´ı da´ para montar a matriz da PD...
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Todos os Caminhos M´ınimos – Floyd-Warshall
Na˜o ha´ necessidade de manter mais de uma matriz...
int M[N][N];
...
void floyd(){
int k,i,j,d;
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ ){
d = M[i][k]+M[k][j];
if ( d < M[i][j] ) M[i][j] = d;
}
}
Ana´lise de
Algoritmos
113859
Aula 17
Roteiro
A´rvore
Espalhada
Mı´nima
Algoritmos
Gulosos
Algoritmo de
Floyd-Warshal
Todos os Caminhos M´ınimos – Floyd-Warshall
• Para grafos na˜o-direcionados, admite pequena
simplificac¸a˜o:
• Veja que, neste caso, d(i, j, k) = d(j, i, k).
int M[N][N];
...
void floyd(){
int k,i,j,a,b,d;
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = i+1; j < N; j++ ){
a = i < k ? M[i][k] : M[k][i];
b = k < j ? M[k][j] : M[j][k];
d = a + b;
if ( d < M[i][j] ) M[i][j] = d;
}
}
	Roteiro
	Árvore Espalhada Mínima
	Algoritmo de Prim
	Algoritmo de Kruskal e Union-Find
	Algoritmos Gulosos
	Algoritmo de Floyd-Warshal