Análise de Algoritmos - Aula 18 (Guilherme)

Prévia do material em texto

Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
Roteiro da Aula 18
1 Algoritmo de Floyd-Warshal
2 Fluxo em Redes
Ford-Fulkerson e Edmonds-Karp
3 A classe P
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
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 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
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 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
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 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
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 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
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;
}
}
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
Ford-Fulkerson e
Edmonds-Karp
A classe P
Fluxo em Redes
• Dado um d´ıgrafo G = (V, E), uma fonte e um sorvedouro
s, t ∈ V , e capacidades ce > 0 nas arestas;
• Um fluxo e´ uma valorac¸a˜o fe para as arestas, satisfazendo:
• 0 ≤ fe ≤ ce para toda e ∈ E;
• Conservac¸a˜o: para todo ve´rtice u (exceto s e t), a
quantidade de fluxo que entra e´ igual a` que sai:
∑
(w,u)∈E
fwu =
∑
(u,z)∈E
fuz
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
Ford-Fulkerson e
Edmonds-Karp
A classe P
Fluxo em Redes
• O tamanho do fluxo e´ a quantidade total de fluxo indo de
s ate´ t, que e´ igual a:
size(f) =
∑
(s,u)∈E
fsu
Como econtrar o fluxo ma´ximo?
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
Ford-Fulkerson e
Edmonds-Karp
A classe P
Ford-Fulkerson e Edmonds-Karp
Como vimos...
Ford-Fulkerson(G,s,t){
inicialize o fluxo f com 0;
inicialize o grafo residual com G;
Enquanto existir um caminho de acre´scimo p
no grafo residual:
Aumente o fluxo f ao longo do caminho p;
Atualize o grafo residual;
}
Custo: O(|E|f∗), onde f∗ e´ o tamanho do fluxo o´timo
• Algoritmo de Edmonds-Karp:
• No me´todo de Ford-Fulkerson, considere sempre o caminho
de acre´scimo com o menor nu´mero de arestas, usando, por
exemplo, uma busca em largura no grafo residual.
• Custo: O(|V ||E|2)
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
A classe P
Classe P
Um problema pertence a` classe P se ele possui uma cota
superior O(nk), para alguma constante k. Ou seja, se existe
para ele algum algoritmo polinomial.
Se um problema esta´ em P,
enta˜o ele e´ chamado de trata´vel.
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
Relevaˆncia da classe P
• Considere a diferenc¸a entre n3 e 2n:
• 1003 = 1000000: um milha˜o;
• 2100 = 1267650600228229401496703205376: um zilha˜o...
• Um algoritmo polinomial pode na˜o ser u´til na pra´tica; mas
um algoritmo exponencial certamente na˜o e´ u´til na pra´tica!
Ana´lise de
Algoritmos
113859
Aula 18
Roteiro
Algoritmo de
Floyd-Warshal
Fluxo em
Redes
A classe P
Relevaˆncia da classe P
• P e´ invariante, robusta, em relac¸a˜o aos modelos de
computac¸a˜o relevantes: todos sa˜o polinomialmente
equivalentes!
C s operac¸o˜es f(n) = n5
ASSEMBLER s2 operac¸o˜es f ′(n) = (n5)2
Ma´q. Turing (s2)6 operac¸o˜es f ′′(n) = ((n5)2)6
Mas f ′′(n) = ((n5)2)6 = n60, que e´ polinomial!
	Roteiro
	Algoritmo de Floyd-Warshal
	Fluxo em Redes
	Ford-Fulkerson e Edmonds-Karp
	A classe P