Projeto e Análise de Algoritmos - Algoritmos em Grafos (parte 3)

Prévia do material em texto

CAMINHO MAIS CURTO
�PRINCIPAIS ALGORITMOS:
�Algoritmo de Dijkstra
�Algoritmo de Bellman-Ford 
�Algoritmo A* 
�Algoritmo de Floyd-Warshall 
�Algoritmo de Johnson 
CAMINHO MAIS CURTO
Caminho mais curto de um nó a outro
Edsger Dijkstra
Maio de 1930 – agosto de 2012
CAMINHO MAIS CURTO
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
1) Define-se inicialmente o nó de origem (raiz), neste caso s, e inclui-se este nó em 
PERM (permanente). Atribui-se zero a sua distância (dist[s]) porque o custo de ir 
de s a s é obviamente 0. Todos os outros nós i tem suas distâncias (dist[i]) 
inicializadas com um valor bastante grande ("infinito").
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
2) A partir de s consulta-se os vértices adjacentes a ele, que no grafo G são u e x. Para 
todos os vértices adjacentes, que chamaremos z, calcula-se:
Se dist[z] > dist[s] + peso(s, z)
dist[z] = dist[s] + peso(s, z)
path[z] = s
Fim Se
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
3) Dentre todos os vértices não pertencentes a PERM escolhe-se 
aquele com a menor distância. Neste caso é o vértice x, pois 
dist[x] = 5. 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
4) Então, inclui-se x em PERM e a partir de x consulta-se os vértices adjacentes a ele que 
não estão em PERM, que no grafo G são u, v e y. Para todos os vértices adjacentes, que 
chamaremos z, calcula-se:
Se dist[z] > dist[x] + peso(x, z)
dist[z] = dist[x] + peso(x, z)
path[z] = x
Fim Se 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
5) Dentre todos os vértices não pertencentes a PERM escolhe-se aquele 
com a menor distância. Neste caso é o vértice y, pois dist[y] = 7.
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
6) Inclui-se então y em PERM e a partir de y consulta-se os vértices adjacentes a ele que 
não estão em PERM, que no grafo G é apenas o vértice v.
Se dist[v] > dist[y] + peso(y, v)
dist[v] = dist[y] + peso(y, v)
path[v] = y
Fim Se 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
7) Dentre todos os vértices não pertencentes a PERM escolhe-se 
aquele com a menor distância. Neste caso é o vértice u, pois 
dist[u] = 8. 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
8) Inclui-se então u em PERM e a partir de u consulta-se os vértices adjacentes a 
ele que não estão em PERM, que no grafo G é apenas o vértice v. 
Se dist[v] > dist[u] + peso(u, v)
dist[v] = dist[u] + peso(u, v)
path[v] = u
Fim Se 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
9) Dentre todos os vértices não pertencentes a PERM escolhe-se 
aquele com a menor distância. Neste caso é o único vértice 
restante v e dist[v] = 9. 
EXEMPLO DE EXECUÇÃO (Algoritmo de Dijkstra)
10) Por fim faz-se v pertencer a PERM. Neste ponto, todos os 
vértices já estão em PERM e a busca é finalizada. 
EXEMPLO DE APLICAÇÃO PRÁTICA (Algoritmo de Dijkstra)
s
a
x d
b
c
4
5
5
7
6
2-3
s
a
x d
b
c
4
5
5
7
6
2-3
Complexidade de performance: O(V×E)
Complexidade de espaço: O(V)
� Dados: 
Grafo G=(V, A) orientado, |V | = n.
Não há circuitos negativos.
c = {cij}, j = 1,...,n, i = 1,...,n
cij ≥ 0
cii = 0
cij = +, (i, j )  A
Ak(i, j ) = valor do caminho mais curto de i a j
podendo usar apenas nós numerados 
de 1 a k como nós intermediários.
3) Algoritmo de Floyd-Warshall (1962):
Finalidade: encontrar o caminho mais curto entre todos os
pares de nós de um grafo.
1 2
3
3
6
4
11 2
A2(1,3)
A0(i, j ) = cij : caminho mais curto de i a j usando no máximo o nó 
“0” (que não existe) como nó intermediário 
(caminho mais curto de i a j sem nós 
intermediários)
Ak(i, j ) : pode usar o nó k ou não.
Ak+1(i, j ) : pode usar o nó k+1 ou não.
A0  A1
A1  A2
...
An-1  An
An(i, j ) = valor do caminho mais curto de i
a j podendo usar qualquer nó de 
1 a n como nó intermediário.
� Se Ak+1(i, j ) não usa o nó k+1 como intermediário, então: 
Ak+1(i, j ) = Ak(i, j ) 
Ak+1(i, j ) = min { Ak(i, j ), Ak(i, k+1) + Ak(k+1, j ) }
• Se Ak+1(i, j ) usa o nó k+1 como intermediário, então: 
Ak+1(i, j ) = Ak(i, k+1) + Ak(k+1, j )
073
206
1140
A1 = 
Exemplo:
1 2
3
3
6
4
11 2 0+∞3
206
1140
C = 
0+∞3
20
1140
A0 = 6
073
206
640
A2 = 
073
20
640
A3 = 5
Algoritmo de Dijkstra: número de operações (tempo) ~ n2 
n-1 iterações, cada iteração busca o mínimo em uma lista com 
até n-1 elementos.
Algoritmo de Floyd: número de operações (tempo) ~ n3 
Três comandos for de 1 até n, um dentro do outro.
Ou seja, o problema de calcular os caminhos mais curtos 
entre todos os pares de nós pode ser resolvido com a 
mesma eficiência aplicando-se n vezes o algoritmo de 
Dijkstra, uma vez a partir de cada nó inicial.
EXERCÍCIO:
 Programar os algoritmos vistos para obter o 
caminho mais curto de Chicago a Grand Canyon 
(como no exemplo visto);
 O programa deve visualizar o mapa no 
computador e traçar o caminho mais curto (dica: 
coordenadas google).
� Definição: um matching em um grafo G é um conjunto de 
arestas que não formam laços e que não compartilham vértices 
entre si.
� Um vértice incidente às arestas de um matching M é dito 
saturado por M.
� Um matching perfeito de G satura todos os vértices de G.
� Exemplo:
Matching ou emparelhamento
� FUNDAMENTAÇÃO TEÓRICA
� Seja N(S) a vizinhança de S em G, ou seja, o conjunto de todos os vértices adjacentes a 
vértices de S.
� Teorema 1 (Berge, 1957): um emparelhamento M tem cardinalidade máxima em G se e 
somente se G não possui caminho M-aumentante.
� Teorema 2 (Hall, 1956): seja G um grafo bipartido com bipartição X, Y. Então, G admite 
emparelhamento que satura todo vértice de X se e somente se |N(S)| |S|,  S  X.
� Corolário 1: seja G um grafo bipartido com bipartição X, Y. Assim, G admite 
emparelhamento perfeito se e somente se |X| = |Y| e |N(S)|  |S|, para todo S  X.
� Corolário 2: um grafo bipartido tem um emparelhamento perfeito se e somente se 
|N(S)|  |S|, para todo S  V.
Observação: a prova de ambos os teoremas pode ser encontrada em http://www.cos.ufrj.br/~celina/cos742/jai99.pdf
Matching ou emparelhamento
� O tamanho de um matching M é igual a quantidade de arestas de M.
� Um matching M de um grafo G é maximal se toda aresta que não participa de M é
incidente a alguma aresta em M.
� Se M for o matching de maior cardinalidade de G então ele é chamado matching
máximo.
Matching Máximo X Matching Maximal
 Um matching M é máximo se não existe um 
matching M' tal que |M'| > |M|.
 Um matching M é maximal se não existe um 
matching M' do qual M faça parte própria 
(portanto, M é maximal se não existe aresta 
a fora de M tal que M+{a} também é um 
matching). 
Matching ou emparelhamento
� Um caminho alternante em um matching M é um caminho cujas arestas
alternam entre aquelas que estão em M e aquelas que não estão em M.
� Um caminho alternante, cujos vértices extremos não são saturados por M, é
um caminho de aumento de M.
� Quando M possuir um caminho de aumento P podemos trocar as arestas deste
caminho, substituindo aquelas que não estão M pelas que estão. Isto irá
aumentar em uma (1) unidade o tamanho do matching.
Observação: o matching máximo é caracterizado pela ausência de caminhos de 
aumento.
� Matching Perfeito
Dado um grafo G= (V,E), o problema de matching é encontrar o matching máximo
de G. Quando a cardinalidade do matching é  V   2, afirmamos que o matching
é completo ou perfeito. Isto é, todos os vértices estão casados. Em grafos
bipartidos G=(U,V,E), devemos ter V = U para que um matching perfeito possa
existir.
Ref.: Christos H. Papadimitriouand Kenneth Steiglitz Combinatorial Optimization: Algorithms and Complexity, Publisher: Dover Publications; 
Unabridged edition ,1998.
� APLICAÇÕES:
Problema de atribuição de pessoal
� Dados n funcionários e n posições numa empresa, cada funcionário está
qualificado para uma ou mais posições. É possível atribuir uma posição a cada
funcionário, de modo que cada funcionário ocupe exatamente uma posição na
empresa? O objetivo é encontrar uma atribuição ou uma alocação que maximize a
eficiência total dos funcionários.
Problema dos casamentos
� Dada uma matriz onde cada entrada é 0 ou 1, um conjunto de entradas é
independente se não temos duas entradas na mesma linha ou na mesma coluna,
pede-se encontrar um conjunto independente de entradas de valor 1 que tem
cardinalidade máxima. Podemos interpretar as linhas da matriz como sendo
rapazes e as colunas como sendo moças. Uma entrada i, j com valor 1 seria o caso
de rapaz e moça compatíveis. O objetivo é casar um número máximo de casais
compatíveis.
� APLICAÇÕES:
Problema de construção de amostras
� Um vendedor de brinquedos educativos possui em estoque 
brinquedos de várias formas geométricas (cubos, pirâmides, 
etc.), cada qual fabricado em várias cores. O vendedor quer 
carregar consigo o menor número de objetos tal que cada cor e 
cada forma estejam representadas pelo menos uma vez.
� Observação: com base nesta aplicação pode-se prova a 
equivalência entre o problema de cobertura de cardinalidade 
mínima e o problema de emparelhamento de cardinalidade 
máxima.
� PRINCIPAIS ALGORITMOS:
� Algoritmo Húngaro (Grafos bipartidos sem pesos)
� Algoritmo de Kuhn (Grafos bipartidos com pesos)
� Algoritmo de Edmonds (Caso geral sem pesos)
Observação: Maiores detalhes sobre os algoritmos pode ser encontrada em:
http://www.cos.ufrj.br/~celina/cos742/jai99.pdf
Matching ou emparelhamento
Algoritmo Húngaro
� O algoritmo húngaro ou método húngaro (ou mesmo algoritmo de Kuhn-
Munkres) é um algoritmo que resolve o problema de atribuição em tempo
polinomial.
� Foi desenvolvido pelo matemático estadunidense Harold Kuhn, que deu o
nome de dois matemáticos húngaros cujos trabalhos foram fundamentais para
o método: Dénes König e Jenö Egerváry.
� Ele permite achar um casamento de peso máximo (ou um casamento perfeito
de peso mínimo) em um grafo bipartido valorado.
Algoritmo Húngaro
� Teorema: se um número é somado ou subtraído de 
todas as entradas de uma linha ou coluna da matriz-
custo, então uma alocação de tarefas ótima para a 
matriz resultante é também uma alocação de tarefas 
ótima para a matriz-custo original.
Fonte: 
http://sbemparana.com.br/arquivos/anais/epremxii/ARQUIVOS/
MINICURSOS/autores/MCA016.pdf
Algoritmo Húngaro
� Aplicando o teorema em uma matriz-custo dada, temos o 
algoritmo (ou método) húngaro:
� 1 – subtraia a menor entrada de cada linha de todas as entradas da mesma linha, 
de forma que cada linha tenha pelo menos uma entrada zero e as demais 
positivas;
� 2 – subtraia a menor entrada de cada coluna de todas as entradas da mesma 
coluna, de forma que cada coluna tenha pelo menos uma entrada zero e as 
demais positivas;
Algoritmo Húngaro
� 3 – marque todas as linhas e/ou colunas que possuam zeros com uma linha. Minimize o 
número de traços;
� 4 – teste a otimalidade:
� Se o mínimo de linhas necessárias para cobrir os zeros é n, então uma alocação ótima 
de zeros é possível para encerrar o procedimento;
� Se o mínimo de linhas necessárias para cobrir os zeros for menor que n, então não é 
possível uma alocação ótima de zeros. Assim, vá para o passo 5.
� 5 – Determine a menor entrada não riscada por nenhuma linha. Subtraia esta entrada 
de todas as outras não riscadas e depois some-a a todas as entradas riscadas tanto em 
horizontais quanto em verticais. Volte para o passo 3.
Aplicação do Método Húngaro
� Consideremos o seguinte problema:
� Uma construtora tem quatro escavadeiras guardadas em quatro garagens 
diferentes.
� As escavadeiras devem ser transportadas a quatro diferentes locais de 
construção.
� As distâncias entre as escavadeiras e os locais de construção são dadas, em 
quilômetros, na tabela abaixo:
Local 1 Local 2 Local 3 Local 4
Escavadeira 1 90 75 75 80
Escavadeira 2 35 85 55 65
Escavadeira 3 125 95 90 105
Escavadeira 4 45 110 95 115
Aplicação do Método Húngaro
� Pergunta-se: como devem ser transportadas as escavadeiras 
para os locais de construção para minimizar a distância total 
percorrida?
� Inicialmente, escrevemos a matriz-custo:
90 75 75 80
35 85 55 65
125 95 90 105
45 110 95 115
Aplicação do Método Húngaro
� Passo 1: subtraímos 75 da primeira linha, 35 da segunda, 90 da terceira, 
45 da quarta, obtendo:
15 0 0 5
0 50 20 30
35 5 0 15
0 65 50 70
90 75 75 80
35 85 55 65
125 95 90 105
45 110 95 115
Aplicação do Método Húngaro
� Passo 2: as três primeiras colunas já têm entradas zero; portanto, basta 
subtrair 5 da quarta coluna:
15 0 0 0
0 50 20 25
35 5 0 10
0 65 50 65
15 0 0 5
0 50 20 30
35 5 0 15
0 65 50 70
Aplicação do Método Húngaro
� Passo 3: riscamos as entradas zero da matriz com um número mínimo de 
traços horizontais e verticais:
� Passo 4: como o número mínimo de traços é três, ainda não é possível 
uma alocação ótima de zeros.
15 0 0 0
0 50 20 25
35 5 0 10
0 65 50 65
15 0 0 0
0 50 20 25
35 5 0 10
0 65 50 65
Aplicação do Método Húngaro
� Passo 5: subtraímos 20, que é a menor entrada não riscada, de cada uma das entradas 
não riscadas e somamos 20 às duas entradas riscadas por dois traços:
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
Aplicação do Método Húngaro
� Passo 6: riscamos as entradas zero com um número mínimo de traços 
horizontais e verticais. Riscamos a primeira linha e a primeira e terceira 
colunas.
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
Aplicação do Método Húngaro
� Passo 7: o número mínimo de traços é três e, portanto, ainda não é possível 
uma alocação ótima de zeros.
� Passo 8: subtraímos 5, que é a menor entrada não riscada, de cada uma das 
entradas não riscadas e somamos 5 às duas entradas riscadas por dois traços:
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
Aplicação do Método Húngaro
� Passo 9: riscamos as entradas zero com um número mínimo de traços 
horizontais e verticais. Riscamos as quatro primeiras linhas:
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
Aplicação do Método Húngaro
� Passo 10: como as entradas zero não podem ser riscadas com menos do que 
quatro traços, a matriz deve conter uma alocação ótima de zeros
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
ou
Aplicação do Método Húngaro
� Esse resultado permite concluir que a otimização ocorre 
em 2 situações, alocando:
� Em qualquer dos casos, a soma das distâncias é 275 km, 
que corresponde à menor distância percorrida. 
Escavadeira 1 na construção 2 (75 km)
Escavadeira 2 na construção 4 (65 km)
Escavadeira 3 na construção 3 (90 km)
Escavadeira 4 na construção 1 (45 km) 
Escavadeira 1 na construção 4 (80 km)
Escavadeira 2 na construção 3 (55 km)
Escavadeira 3 na construção 2 (95 km)
Escavadeira 4 na construção 1 (45 km) 
ou
Algoritmo Húngaro
� Observações:
� A matriz-custo precisa ser quadrada. Quando isso não ocorrer, deve-se introduzir 
uma linha ou coluna fictícia de zeros.
� As entradas da matriz-custo devem ser números inteiros. Quando isso não ocorrer, 
deve-se multiplicar a matriz-custo por uma potência conveniente de dez.
� O problema deve ser de minimização. O problema de maximizar a somadas 
entradas de uma matriz-custo é facilmente convertido em um problema de 
minimizar a soma das entradas multiplicando cada uma por –1.