sexta-feira, 21 de novembro de 2014

[TUTORIAL] Simulando reconhecimento de padrões através de caminhos ótimos em grafos

Nesse tutorial vamos simular o reconhecimento de padrões através de caminhos mínimos em grafos. O problema do caminho mínimo consiste em encontrar uma travessia em um grafo considerando origem e destino vértices, que seja a mínima possível. O custo se encontra nas arestas desse grafo. Para poder simular a detecção de caminhos mínimos, utilizaremos um dos algoritmos mais eficientes na busca de caminhos mínimos em Grafos: o algoritmo de Dijkstra.  Primeiramente, é encontrado o menor caminho entre os vértices mais próximos a ele (seus vizinhos), depois, aos segundos mais próximos, e depois quando todas as iterações ocorrem, o algoritmo já identificou o menor caminho para todos os vértices do grafo dada uma fonte.



  • Algoritmo de Dijkstra - Funcionamento: 
A seguir demonstraremos a partir de um exemplo o funcionamento do algoritmo de Dijkstra:



Considerando:



u => representa o vértice atual que está sendo analisado;

v' => representa os vizinhos que ainda estão na fila do vértice analisado na iteração;
λ(v) => representa o custo de entrada do vértice atualmente, que será o mínimo possível, a análise é feita comparando o custo de entrada anterior devido a um caminho e o custo de entrada pelo u, que é outro caminho;
π(v) => representa o predecessor de v


Consideraremos também, uma fila de prioridades, estará indicado o valor de λ(v) atual de cada vértice que ainda faz parte das iterações. Inicialmente, todos os vértices, excetuando a fonte, possuem peso de entrada inicial igual a ∞. A fonte tem peso 0.


Seja o grafo exemplo:

O vértice s será considerado nesse exemplo o vértice inicial, do qual será encontrado os menores caminhos para os demais vérices.

Primeira Iteração:

s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞

A fila de prioridades se comporta dessa maneira primeiramente. Todos os vértices são inicializados com custo de entrada infinito, excetuando-se a fonte, que, como será o primeiro vértice do caminho, terá custo 0.


u
Vizinhos de u que ainda estão na fila
Menor caminho até v
Predecessor de v
s
{a,c}
λ(a) = 18
λ(c) = 15
π(a) = s
π(c) = s
 

Primeiramente são analisados os vizinhos da fonte, que são os vértices mais próximos. Os valores de seus caminhos e de seus predecessores são atualizados. Após isso, é selecionado na fila de prioridades aquele vértice com menor caminho até agora, que é o c.

O Caminho ficará da seguinte maneira:


Segunda Iteração:
 
s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞
λ (v)
18
∞
15
∞
∞

Nessa iteração, o vértice fonte já foi analisado e retirado da fila de prioridades. O vértice que possui caminho com menor custo passa a ser analisado e nesse caso é o c. Todos os vértices tiveram seus valores de caminho em relação a fonte atualizados.

 
u
Vizinhos de u que ainda estão na fila
Menor caminho até v
Predecessor de v
s
{a,c}
λ(a) = 18
λ(c) = 15
π(a) = s
π(c) = s
c
{a,b,d}
λ(a) = 18
λ(b) = 29
λ(d) = 22
π(a) = s
π(b) = c
π(d) = c

Os vizinhos de c que ainda estão na fila são analisados. No caso do vértice a, é feita a comparação se o caminho de entrada por c é menor que o caminho anterior. Como o caminho de entrada por c é dado por 15 + 6 = 21 (15 é o custo de ir da fonte até c, e depois ir de c até a custa mais 6), o vértice a continua com o caminho anterior, que é o mínimo possível. Os outros dois vértices têm seus valores atualizados. O vértice c, então, é eliminado da fila. 

O Caminho ficará assim:

Terceira Iteração:

s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞
λ (v)
18
∞
15
∞
∞
λ (v)
18
29
22
∞

O próximo vértice a ser analisado será o a, que tem menor caminho entre os vértices remanescentes na fila.

u
Vizinhos de u que ainda estão na fila
Menor caminho até v
Predecessor de v
s
{a,c}
λ(a) = 18
λ(c) = 15
π(a) = s
π(c) = s
c
{a,b,d}
λ(a) = 18
λ(b) = 29
λ(d) = 22
π(a) = s
π(b) = c
π(d) = c
a
{b}
λ(b) = 27
π(b) = a

O único vizinho de a que ainda está na fila é o b. Seu custo de entrada anterior era dado pelo caminho passando pelo vértice c, ou seja, da fonte até c  - 15 -  e de c até b - 14 - totalizando anteriormente, 29. Como o caminho passando por a tem um custo menor, 18 - da fonte até a, e 9 de a até b, que dá um total de 27, seu custo e predecessor são atualizados. Ao fim dessa iteração o a é eliminado da fila de prioridades.

O Caminho ficará assim:
Quarta Iteração:
 
s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞
λ (v)
18
∞
15
∞
∞
λ (v)
18
29
22
∞
λ (v)
27
22
∞

O vértice d é o que possui o menor caminho dentre os vértices que ainda estão na fila, e será analisado nessa iteração.
 
u
Vizinhos de u que ainda estão na fila
Menor caminho até v
Predecessor de v
s
{a,c}
λ(a) = 18
λ(c) = 15
π(a) = s
π(c) = s
c
{a,b,d}
λ(a) = 18
λ(b) = 29
λ(d) = 22
π(a) = s
π(b) = c
π(d) = c
a
{b}
λ(b) = 27
π(b) = a
d
{b,t}
λ(b) = 27
λ(t) = 58
π(b) = a
π(t) = d

Os vizinhos de d que ainda estão na fila são b e t. Ao analisar o caminho para b, passando por d, percebe-se que não resultará em um caminho mínimo. O caminho até b passando por a tem custo 27, enquanto que passando por d, teríamos o custo do caminho para chegar até d, que é 22, somado com o custo de ir de d até b, que é 10. Como 32 é  superior a 27, b continua tendo como predecessor o a. O vértice t, que ainda possui infinito como custo, é atualizado nessa iteração, de modo que passará a ter custo de entrada 58, que é dado pela soma do custo de entrada de d (o menor caminho de s até d) e o custo de entrada de d até t. O d é eliminado da fila de prioridades e o processo continua.

O Caminho ficará assim:

Quinta Iteração:

 
s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞
λ (v)
18
∞
15
∞
∞
λ (v)
18
29
22
∞
λ (v)
27
22
∞
λ (v)
27
58

O vértice b é o que possui menor custo de caminho na fila. Ele será analisado nessa etapa.

 
u
Vizinhos de u que ainda estão na fila
Menor caminho até v
Predecessor de v
s
{a,c}
λ(a) = 18
λ(c) = 15
π(a) = s
π(c) = s
c
{a,b,d}
λ(a) = 18
λ(b) = 29
λ(d) = 22
π(a) = s
π(b) = c
π(d) = c
a
{b}
λ(b) = 27
π(b) = a
d
{b,t}
λ(b) = 27
λ(t) = 58
π(b) = a
π(t) = d
b
{t}
λ(t) = 55
π(a) = b

O único vizinho de b que ainda está na fila é o t. Passando por b, o caminho para t assume o valor 55 (soma do valor do caminho de s até b - 27 - com o valor do caminho de b até t - 28) que é inferior ao caminho até t passando por d (58). Assim, o valor de caminho mínimo para t é atualizado, com b assumindo a posição de predecessor.

O Caminho ficará assim:


E a fila:
 
s
a
b
c
d
t
λ (v)
0
∞
∞
∞
∞
∞
λ (v)
18
∞
15
∞
∞
λ (v)
18
29
22
∞
λ (v)
27
22
∞
λ (v)
27
58
λ (v)
55

O único vértice ainda na fila é o t, como ele não possui nenhum vizinho que ainda esteja na fila, o processo terminou e todos os vértices possuem um valor de caminho mínimo em relação a fonte s.


  • Implementação do Algoritmo de Dijkstra:




O algoritmo implementado em Python tem duas funções, sendo que uma é a implementação do Algoritmo de Dijkstra e a outra desenha os caminhos encontrados nesse algoritmo.

Como já explicado o funcionamento, o Algoritmo de Dijkstra consiste em encontrar caminhos mínimos. Para permitir que essa implementação realizada sirva para as diversas aplicações desse algoritmo foi feito na função colocado na função principal a opção do usuário digitar quantas raízes (ou sementes,ou seja o começo do caminho) ele deseja e logo depois digitar os números das raízes.

Passando como parâmetro o grafo G, os nomes dos vértices V (que é utilizado para retornar a quantidade de vértices desse grafo), as raízes iniciais em S e a quantidade de caminhos necessários em k, o algoritmo consiste em definir os predecessores e os menores custos de cada vértice, pois assim será definido os melhores caminhos.

Foi inicializado um vetor de custo com todos os elementos valendo infinito e um vetor de predecessor (pred) com os elementos valendo -1, já que não vai existir nenhum vértice chamado -1 escolhemos este valor como padrão para inicialização. O Q que recebe todos os vértices é a fila de prioridade contendo os vértices que ainda não foram encontrados os menores custos. Fazemos nas linhas 29 o começo do algoritmo que consiste em colocar o custo de todas as raízes sendo 0.

O algoritmo de Dijkstra em si está dentro do 'while' das linhas 37 a 55, o primeiro passo é definir qual o menor custo dos vértices existentes em Q e escolher este para relaxar os vizinhos. O processo de relaxar os vizinhos está dentro do 'for' da linha 50, que percorrer todos os vizinhos comparando os custos e selecionando o mínimo, definindo assim o custo e predecessor de cada vértice.

Essa função então retorna os vetores de custo e dos predecessores.

A função apresentada nas linhas 58 a 85 segue o modelo de plotar um grafo utilizado no tutorial anterior, qual quer dúvida consultem. Ele vai gerar os caminhos mínimos definido pelo Algoritmo de Dijkstra.

  • Alguns exemplos de execuções:





 Utilizando o grafo (cidades da Inglaterra) abaixo como modelo, foram feitas duas execuções.

- Usando k = 2 em grafo das cidades da Inglaterra:

A primeira consiste em duas raízes, ou seja definir k=2, e essas sementes são os vértices 4 e 9, sendo este com distância entre si pequena, logo são próximos. Observe abaixo os caminhos resultados:
O segundo trata de duas raízes distantes são elas 0 e 11:


Mais duas execuções serão feitas com o grafo (grafo das cidades da Alemanha) abaixo.

- Usando k=3 em grafo das cidades da Alemanha:


Executando o Algoritmo para as raízes próximas de números 15, 20 e 17.


E por último executando o Algoritmo para as raízes afastadas 0, 3 e 5:




  • Conclusão:




Ao observarmos os resultados obtidos a partir da aplicação do algortimo de Dijkstra considerando duas e três raízes, percebemos que quando essas raízes se encontram próximas, a troca da origem do caminho dos vértices tem uma probabilidade de ocorrer com maior frequência nas primeiras iterações do algoritmo, nas últimas iterações, quando os caminhos já estão quase totalmente formados, é difícil que se ache um caminho mais curto até um vértice que tenha como origem o outro vértice. Quando se analisa com os vértices origem mais afastados, percebe-se que as trocas costumam ocorrer mais nas últimas iterações, caso se encontre algum caminho menor para um vértice vindo de outra raíz.

Nenhum comentário:

Postar um comentário