Algoritmos de Caminhamento
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:
1)
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
2)
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
Fig. 5: Representação do
Algoritmo de Dijkstra
3)
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.
Fig. 6: Representação do
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 (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
Fig. 7: Representação do
Algoritmo de Dijkstra
5)
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.
Fig. 8: Representação do 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
(Figura 6).
Se dist[v] > dist[y] +
peso(y, v)
dist[v] = dist[y] +
peso(y, v)
path[v]
= y
Fim Se
Fig. 9: Representação do
Algoritmo de Dijkstra
7)
Dentre todos os vértices não
pertencentes a PERM escolhe-se aquele com a menor distância (Figura
7). Neste caso é o vértice u, pois dist[u] = 8.
Fig. 10: Representação do
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
(Figura 8).
Se dist[v] >
dist[u] + peso(u, v)
dist[v] = dist[u] +
peso(u, v)
path[v]
= u
Fim Se
Fig. 11: Representação do
Algoritmo de Dijkstra
9)
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.
Fig. 12: Representação do
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 (Figura 13).
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
determinar o 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
-
-
Contato
Matérias :: Matemática