Algoritmos de Caminhamento

Prévia do material em texto

�
�PAGE �
�PAGE �19�
�
INTRODUÇÃO
	Este trabalho tem como objetivo apresentar os Algoritmos de Caminhamento, descrevendo suas características e particularidades, discutindo os processos que os englobam, mostrar com representações gráficas o seu funcionamento e estudar os códigos.
�
1 ALGORÍTMO DE KRUSKAL
Este algoritmo utiliza três conjuntos e, t e vs. T é usado para guardar as arestas da árvore expandida. O algoritmo trabalha transformando uma floresta expandida de g em uma única árvore. O conjunto vs contém os conjuntos das árvores da floresta expandida. Inicialmente vs contém todos os vértices de g, onde cada vértice é um conjunto unitário. 
As arestas são escolhidas por ordem crescente de custo. Quando uma aresta une duas sub-árvores da floresta expandida, estas são unidas em vs, quando não, ela é descartada, pois forma ciclo.
1.1 Árvore Mínima de Suporte (Mst)
Mst (minimum spannig tree) ou msct - árvore geradora de peso mínimo (minimum cost spanning tree) - uma árvore mínima de suporte (mst) de um grafo ponderado é o conjunto de arestas ligando todos os vértices, tais que a soma dos pesos das arestas é, pelo menos, tão baixa quanto a soma dos pesos de qualquer outro conjunto de arestas ligando todos os vértices.
Exemplo:
1.2 Utilizando o Mst
Dado um grafo conexo não orientado g, com peso positivo nas arestas (e ( r+), encontrar uma árvore geradora de g de peso mínimo. Para resolver este problema acima o algoritmo de Kruskal é uma das opções, temos outras opções como o Prim e o Boruvka.
	O algoritmo de Kruskal é guloso. Como o nome sugere, estratégia usada por esse algoritmo consiste na escolha da melhor solução em determinados instantes. Isto é, ele faz uma escolha ótima localmente esperando que esta escolha leve a uma solução ótima global. Por vezes conduz a uma solução ótima, mas nem sempre isso ocorre.
1.3 Problema da Árvore de Ligações Mínimas
- Descrição do Problema:
encontrar a árvore de comprimento total mínimo sobre uma rede orientada ou não de distância, tempos, etc.
- Algorítmos de Kruskal:
.construir uma lista das arestas da rede e ordená-las por ordem crescente de distâncias.
.começar por escolher a 1ª aresta da lista;
.repetir 2 até todos os vértices fazerem parte da árvore identificada;
.a árvore de ligações mínimas é constituídas pelas arestas escolhidas e tem comprimento total igual a soma dos comprimentos das arestas;
- Casos Especiais:
- se, no ponto 3, temos arcos alternativos com igual comprimento e ao escolher ambos formam-se ciclos, então existem soluções degeneradas;
- se existirem n conjunto de m arcos nas condições anteriores então existirão mxn soluções
 ótimas;
1.4 Algoritmo
Função Kruskal (G=(V,E): grafo; Comprimento: E->R): conjunto de arestas
{inicialização}
Ordenar E por ordem crescente do comprimento
N |V|
T Ǿ {arestas da árvore geradora mínima}
Inicializar n conjuntos, cada um com nó de V
{laço guloso}
repita
e {u,v}// a menor aresta não considerada
ucomp achar(u)
vcomp achar(v)
se ucomp ≠ vcomp então
	juntar (ucomp,vcomp)
	T T U {e}
até |T| = n-1
retornar T
A complexidade do algoritmo pode ser analisada:
- Ordenação das arestas;
- Inicialização dos conjuntos disjuntos;
- Gasto para achar as arestas;
- Gasto para junção.
1.5 Melhoras no Algoritmo
Pode-se colocar uma busca e ordenação mais eficientes, nas buscas de união pode-se utilizar “halving”, 	“mergesort” é outra dica para se utilizar na ordenação.
2 ALGORITMO DE DIJKSTRA 
O algoritmo de Dijkstra é o mais famoso dos algoritmos para cálculo de caminho de custo mínimo entre vértices de um grafo e, na prática, o mais empregado.
Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. O algoritmo pode ser usado sobre grafos orientados (dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo é possível). Esta restrição é perfeitamente possível no contexto de redes de transportes, onde as arestas representam normalmente distâncias ou tempos médios de percurso; poderão existir, no entanto, aplicações onde as arestas apresentam pesos negativos, nestes casos o algoritmo não funcionará corretamente. 
2.1 Funcionamento do Algoritmo
Assumiremos um conjunto, Chama-lo-emos PERM, que contém inicialmente apenas o vértice fonte (raiz da busca) s. A qualquer momento PERM contém todos os vértices para os quais já foram determinados os menores caminhos usando apenas vértices em PERM a partir de s. Para cada vértice z fora de PERM matemos a menor distância dist[z] de s a z usando caminhos onde o único vértice que não está em PERM seja z. É necesssário também armazenar o vértice adjacente (precedente) a z neste caminho em path[z]. 
Como fazer com que PERM cresça, ou seja, qual vértice deve ser incluído em PERM a seguir? Tomamos o vértice, entre todos os que ainda não pertencem a PERM, com menor distância dist. Acrescentamos então este vértice chamemo-lo de current, a PERM, e recalculamos as distâncias (dist) para todos os vértices adjacentes a ele que não estejam em PERM, pois pode haver um caminho menor a partir de s, passando por current, do que aquele que havia antes de current ser agregado a PERM. Se houver um caminho mais curto precisamos também atualizar path[z] de forma a indicar que current é o vértice adjacente a z pelo novo caminho mínimo. 
Vejamos o funcionamento do algoritmo sob uma outra representação:
Defini-se inicialmente o nó de origem (raiz), neste caso s, e inclui-se este nó em PERM (Figura 1). 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").
Fig. 4: Representação do Algoritmo de Dijkstra
A partir de s consulta-se os vértices adjacentes a ele, que no grafo G são u e x (Figura 2). 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
 �� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj234q.gif" \* MERGEFORMATINET 
Fig. 5: Representação do Algoritmo de Dijkstra
Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância (Figura 3). Neste caso é o vértice x, pois dist[x] = 5. 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj235q.gif" \* MERGEFORMATINET 
Fig. 6: Representação do Algoritmo de Dijkstra
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 (Figura 4). 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
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj236q.gif" \* MERGEFORMATINET 
Fig. 7: Representação do Algoritmo de Dijkstra
Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância (Figura 5). Neste caso é o vértice y, pois dist[y] = 7. 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj237q.gif" \* MERGEFORMATINET 
Fig. 8: Representação do Algoritmo de Dijkstra
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 (Figura 6).
Se dist[v] > dist[y] + peso(y, v)
   dist[v] = dist[y] + peso(y, v)
   path[v] = y
Fim Se 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj238q.gif" \* MERGEFORMATINET 
Fig. 9: Representação do Algoritmo de Dijkstra
Dentre todos os vértices não pertencentes a PERM escolhe-se aquelecom a menor distância (Figura 7). Neste caso é o vértice u, pois dist[u] = 8. 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj239q.gif" \* MERGEFORMATINET 
Fig. 10: Representação do Algoritmo de Dijkstra
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 (Figura 8). 
  Se dist[v] > dist[u] + peso(u, v)
    dist[v] = dist[u] + peso(u, v)
    path[v] = u
  Fim Se 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj240q.gif" \* MERGEFORMATINET 
Fig. 11: Representação do Algoritmo de Dijkstra
Dentre todos os vértices não pertencentes a PERM escolhe-se aquele com a menor distância (Figura 9). Neste caso é o único vértice restante v e dist[v] = 9. 
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj241q.gif" \* MERGEFORMATINET 
Fig. 12: Representação do Algoritmo de Dijkstra
Por fim faz-se v pertencer a PERM. Neste ponto, todos os vértices já estão em PERM e a busca é finalizada (Figura 13).
�� INCLUDEPICTURE "http://www.lcad.icmc.usp.br/~nonato/ED/Dijkstra/imgj242q.gif" \* MERGEFORMATINET 
Fig. 13: Representação do Algoritmo de Dijkstra
3 ALGORITMO DE PRIM
A característica principal do algoritmo de Kruskal é que ele seleciona a melhor arestas sem se preocupar da conexão com as arestas selecionadas antes. O resultado é uma proliferação de árvores que eventualmente se juntam para formar uma árvore. 
Já que sabemos que no final temos que produzir uma árvore só, por que não tentar fazer com que uma árvore cresça naturalmente até a obtenção da árvore geradora mínima? Assim, a próxima aresta selecionada seria sempre uma que se conecta à arvore que já existe. Isso é a idéia do algoritmo de Prim: 
No início o conjunto B contém um vértice arbitrário. A cada passo, o algoritmo considere todas as arestas que tocam B e seleciona a de menor peso. Depois, o algoritmo acrescenta em B o vértice ligada por essa aresta que não estava em B. O processo continua até que B contenha todos os vértices de G. 
3.1 Algoritmo
função Prim(G = (N,A): grafo): conjunto de arestas 
T := {} 
B := Um vértice de G 
Enquanto B não contém todos os vértices
(u,v) :=   aresta de menor peso tal que u V - B e v B 
T :=   T U {(u,v)}
B :=   B U {u}
Retornar T 
Para ilustrar, consideremos o grafo da figura 14, começando arbitrariamente pelo vértice a: 
	Passo 
	Aresta considerada 
	Conjunto B 
	Início 
	- 
	{a} 
	1 
	(b,a) 
	{a,b} 
	2 
	(c,b) 
	{a,b,c} 
	3 
	(d,a) 
	{a,b,c,d} 
	4 
	(e,d) 
	{a,b,c,d,e} 
	5 
	(g,d) 
	{a,b,c,d,e,g} 
	6 
	(f,g) 
	{a,b,c,d,e,f,g} 
A figura a seguir ilustra a progressão na composição da árvore geradora:
Para implementar eficientemente esse algoritmo, utiliza-se uma matriz de adjacência A[1..n, 1..n], onde cada elemento indica a distância entre dois vértices. Caso dois vértices não forem ligados por uma aresta o valor será . Para representar o conjunto B, podemos utilizar duas tabelas de n elementos, uma indicando para cada vértice o vértice de B que é mais perto, uma outra que dá a distância até o vértice de B que é mais perto. 
Seja mais_perto[1..n] e dist_mais_perto[1..n] essas duas tabelas, respectivamente. Para um vértice que já pertence a B, colocamos (-1) na entrada correspondente na tabela. 
3.2 Outro Algoritmo
função Prim(L = [1..n, 1..n]: grafo): conjunto de arestas 
{Inicialmente consideramos que o vértice 1 é o único elemento de B} 
T := {} 
Para i := 2 até n:
mais_perto[i] := 1 
dist_mais_perto[i] := L[i,1] 
Repetir n-1 vezes:
min := 
Para j := 2 até n:
Se 0 dist_mais_perto[j] < min então 
min := dist_mais_perto[j] 
k := j 
T :=   T U ((k,mais_perto[k])}
dist_mais_perto[k] := -1 
Para j := 2 até n:
Se L[k,j] < dist_mais_perto[j] então 
dist_mais_perto[j] := L[k,j] 
mais_perto[j] := k 
Retornar T 
Analisando esse algoritmo, conclui-se que ele tem um tempo de execução em O(n2). Qual é o melhor entre esse algoritmo e o algoritmo de Kruskal? Se o grafo tem muitas arestas, isto é, ele tem um número de arestas que se aproxima de n(n-1), o tempo de execução com o algoritmo de Kruskal é em O(n2 lg n), portanto pior que o algoritmo de Prim. Mas se o grafo é esparso, o número de arestas se aproxima de n. Nesse caso, o algoritmo de Kruskal está em O(n lg n) e é o melhor. Na verdade, existem outros algoritmos melhores no caso de grafo esparso. 
4 ALGORITMO DE BELLMAN-FORD
O algoritmo de Bellman-Ford faz uso da mesma técnica utilizada pelo algoritmo
de Dijkstra. Este algoritmo computa os caminhos mais curtos de um vértice inicial de origem a todos os demais, inclusive em grafos com pesos negativos. A única restrição é que o grafo não possua nenhum circuito de peso negativo.
4.1 Algoritmo
Entrada: (1) Grafo G com pesos nas arestas; (2) Vértice s de origem; (3) Matriz w de
pesos das arestas;
Saída: Caminho mais curto de s até todos os demais vértices de G
para cada vértice v Є V f aça
d[v] ∞ 
fim para
d[s] 0
para i 1 até |V | - 1 faça
para cada aresta (u, v) Є E faça
se d[v] > d[u] + w(u, v) então
d[v] d[u] + w(u, v)
fim se
fim para
fim para
para cada aresta (u, v) Є E faça
se d[v] > d[u] + w(u, v) então
retorne FALSO
fim se
fim para
retorne VERDADEIRO
Como já foi dito, se existir um circuito negativo, não poderemos garantir que os caminhos encontrados nos grafos correspondem aos caminhos mais curtos. Ou seja, se existirem arestas (u, v) tais que w(u, v) + d[u] < d[v], o algoritmo retorna FALSO. Esse teste é realizado pelo passo 12 do algoritmo. A complexidade de tempo do algoritmo de Bellman-Ford é O(|E| |V|). Dessa forma, se você precisa resolver o problema dos caminhos mais curtos para um grafo com arestas com peso positivo, o algoritmo de Dijkstra nos dá uma solução mais eficiente. Se todas as arestas do grafo possuem peso igual a 1, um algoritmo de busca em largura, que será discutido mais adiante, é o mais indicado. Por fim, para encontrar os caminhos mais curtos entre todos os vértices de um grafo com pesos nas arestas, vamos apresentar o algoritmo de Floyd-Warshall.
5 ALGORITMO DE FLOYD-WARSHALL 
Se todas as arestas de G são não negativas, podemos usar o algoritmo de Dijkstra, o que nos dá um algoritmo de complexidade O(|V |3). Se o algoritmo contém arestas de peso negativo, mas sem circuitos de peso negativo, podemos usar o algoritmo de Bellman-Ford, que nos dá um algoritmo com complexidade de tempo O(|V |2|E|) ou O(|V |4), no caso de
grafos densos. 
Para o algoritmo de Floyd-Warshall, vamos supor que temos uma matriz de pesos wn×n, tal que a posição w(i, j) da matriz de adjacências armazena o peso da aresta i j. 
Caso esta aresta não exista, w(i, j) = ∞. O algoritmo de Floyd-Warshall considera os vértices intermediários de um caminho mais curto P, ou seja, os vértices de P que não são os extremos e consiste de n iterações, onde n é o total de vértices do grafo. Na primeira iteração, trocamos a aresta i . j, para 1 = i, j = n, pelo caminho mais curto de i a j, exceto i e j, que passe somente pelo vértice 1. Esta operação é executada pela comparação entre w(i, 1) + w(1, j) e w(i, j) e selecionando o menor valor, onde w(i, j) = w0(i, j) corresponde ao peso da aresta i . j. O resultado desta comparação é chamado w1(i, j). Na segunda iteração, trocamos o caminho de i a j calculado durante a primeira iteração pelo caminho de menor peso de i a j que, desta vez, pode passar pelos vértices 1 e 2. Este caminho é determinado pela comparação entre w1(i, 2) + w1(2, j) e w1(i, j). O menor entre esses dois valores será w2(i, j). Durante a k-ésima iteração, computamos:
wk(i, j) = min(wk-1(i, j), wk-1(i, k) + wk-1(k, j)) (2.1)
para determinaro caminho mais curto entre i e j que passa somente pelos vértices 1, 2,..., k. 
O caminho mais curto entre cada par de vértices será encontrado após a n-ésima iteração. As posições w(k) ij em cada matriz indicam o peso de caminho mais curto de i a j que atravessa somente os vértices {1, 2, . . . , k}. Para simplificar, o grafo da figura não inclui os caminhos calculados a cada estágio dos algoritmos, mas estes não são difíceis de serem encontrados.
5.1 Algoritmo
Entrada: Matriz de adjacências An×n do grafo G, contendo os pesos das arestas
Saída: Na matriz A, a distância entre todos os pares de vértices de G
para k 1 até n faça
para i 1 até n faça
para j 1 até n faça
w(i, j) min(w(i, j), w(i, k) + w(k, j))
fim para
fim para
fim para
Ao final da execução, o algoritmo encontrará os caminhos mais curtos entre todos os pares de vértices do grafo de entrada. Este algoritmo possui complexidade de O(|V |3).
�
CONCLUSÃO
	De acordo com o assunto abordado, tornou-se possível entender um pouco melhor o funcionamento dos algoritmos de caminhamento, suas funções e a as diferenças de um método pra outro.
�
REFERÊNCIAS BIBLIOGRÁFICAS
Michel. Árvores
http://www.inf.ufpr.br/~andre/Disciplinas/BSc/CI065/michel/ - Acessado em: 30/05/04
Silva, Leonardo. Analise de Algoritmos (UCDB)
http://www.ec.ucdb.br/~marco/courses03a/aa/seminars/ - Acessado em: 30/05/04
Castro Junior, Amaury A. Implementação e Avaliação de Algoritmos BSP/CGM para o Fecho Transitivo de Problemas Relacionados
www.dct.ufms.br/mestrado/dissertacoes/ - Acessado em: 30/05/04
Santos, Clesio S. Grafos
www.inf.ufrgs.br/~nedel/inf01203/ - Acessado em: 30/05/04
Oliveira, Denise. Teoria dos Grafos e Análise Combinatória (UFRGS)
www.inf.ufrgs.br/~edenise/inf05512/ - Acessado em: 30/05/04
Universidade Federal da Bahia (UFBA)
http://www.im.ufba.br/mat156/ - Acessado em: 30/05/2004
Fig. 1: Grafo Original
Fig. 3: Árvore Geradora
do Grafo Original
Fig. 2: Árvore Mínima de Suporte
Fig. 14: Grafo
Fig. 15: Progressão na composição da árvore geradora.
SUMÁRIO
INTRODUÇÃO	2
1 ALGORITMO DE KRUSKAL	3
1.1 Árvore Mínima de Suporte (MST)	3
1.2 Utilizando o MST	4
1.3 Problema da Árvore de Ligações Mínimas	4
1.4 Algoritmo	5
1.5 Melhorias no Algoritmo	6
2 ALGORITMO DE DIJKSTRA	6
2.1 Funcionamento do Algoritmo	6
3 ALGORITMO DE PRIM	11
3.1 Algoritmo	12
3.2 Outro Algoritmo	14
4 ALGORITMO DE BELLMAN-FORD	15
4.1 Algoritmo	15
5 ALGORITMO DE FLOYD-WARSHALL	16
5.1 Algoritmo	17
CONCLUSÃO	18
REFERÊNCIAS BIBLIOGRÁFICAS	19