Núcleo de um GPS
Alana R. Santos, Augusto M. Pinto, Guilherme A. da Silva, Guilherme N. Costa
Faculdade de Computação – Universidade Federal de Uberlândia (UFU)
Caixa Postal 593 – 38.408-100 – Uberlândia – MG – Brasil
{alanarocha,augusto_massini,guilhermealves,guilhermenunes}@comp.ufu.br
Resumo. O estudo de técnicas e algoritmos eficientes que modelam e
manipulam grafos é de extrema importância para o desenvolvimento de
inúmeras aplicações atualmente. Podemos citar neste contexto o uso do grafo
para modelar um mapa e construir uma aplicação que faça o controle de
funcionalidades básicas de um GPS. Este documento apresenta de forma
geral, os algoritmos usados para a implementação de um núcleo de um GPS,
bem como a análise de complexidade de cada algoritmo.
1. Introdução
A principal base de dados que um GPS manipula é o mapa. Um mapa é basicamente
composto por um conjunto de pontos geográficos interligados por meio de um conjunto
de ruas e estradas. Neste trabalho utiliza-se o grafo para modelar um mapa qualquer.
Grafo. Um grafo consiste em um conjunto de vértices e um conjunto de arestas
. Cada aresta é um par ordenado de vértices, ou seja, um conjunto com exatamente
dois vértices.
Para implementar um mapa em um programa de computador por meio de um
grafo deve-se considerar os pontos geográficos como os vértices do grafo e as
interligações como as arestas. Note que neste contexto, faz-se necessário utilizar um
grafo dirigido ou digrafo, desta forma é possível simular com fidelidade os diferentes
sentidos que cada estrada do mapa possui.
Neste contexto é primordial definirmos algumas medidas que nos auxiliarão na
análise de complexidade dos algoritmos que manipulam o digrafo.
Digrafo denso. Um grafo dirigido é considerado denso quando
, logo
.
,
Particularidade do digrafo que implementa um mapa. Note que em um digrafo
que modela um mapa, um vértice qualquer pode possuir duas arestas
e
que
chegam a um mesmo vértice . Logo concluímos que a quantidade máxima de arestas
pode ultrapassar o número
, i. e.,
.
1.1 Metodologia
O grafo foi implementado utilizando lista de adjacência, i. e., existe um array de listas
com
posições, onde para cada posição deste array há uma lista dos vértices
adjacentes a . Esta abordagem é considerada eficiente no que se refere a consumo de
espaço.
Em alguns algoritmos fez-se necessário a utilização de estruturas de dados
auxiliares. A seguir listamos tais estruturas e como foram implementadas: (a) estrutura
do tipo fila com implementação utilizando a abordagem dinâmica com encadeamento
circular (a fila aponta para o último elemento, este por sua vez aponta para o primeiro
elemento da fila) e (b) uma estrutura do tipo pilha com implementação utilizando a
abordagem dinâmica/encadeada.
A seguir é apresentado as estruturas em linguagem C que modelam o grafo/mapa
para uso nas operações do núcleo do GPS.
int visited[maxV]; // nodos visitados
typedef struct road
{
char name[30]; // nome da estrada
float distance; // distância entre as cidades que a estrada faz a
// ligação
} Road; // dados da estrada
typedef struct node
{
char name[STRING_MAX_SIZE]; // nome da cidade
int people;
// população
struct edge *adj;
} City; // dados da cidade
typedef struct edge // nodo do grafo
{
int v;
// id da cidade de destino (nodo do grafo)
int w;
// id da cidade de origem (nodo do grafo)
Road data; // metadados da aresta (informações da estrada)
struct edge *next; // ponteiro para próximo nodo
} Edge;
typedef Edge *link;
typedef struct graph
{
int V; // quantidade de nodos
int E; // quantidade de arestas
City *cities; // lista de adjacência, um vetor de links
} *Graph;
Figura 5. Definições das estruturas que modelam o digrafo/mapa em linguagem C
2. Complexidade de Tempo
2.1 Quantidade de cidades e estradas
ALGORITMO: CONTAGEM DE VÉRTICES E ARESTAS EM UM GRAFO
Entrada: : grafo
Saída: : quantidade de vértices; : quantidade de arestas
Custo
1
1
valor do campo de número vértices de
2
1
valor do campo de número de arestas de
Vezes
1
1
3
devolva
1
e
1
Claramente este algoritmo tem complexidade de tempo
, pois se somarmos o
consumo de tempo de execução de todas as linhas, expresso pela coluna ‘Vezes’
obtemos
, que no pior caso é
, i. e., tempo constante.
2.2 Cidades isoladas
ALGORITMO: DESCOBERTA DE VÉRTICES ISOLADOS EM UM GRAFO
Entrada: : grafo,
: acumulador
Saída: Um vetor com o nome dos vértices isolados
Custo
1 acc 0
1
2 aloque espaço para vetor
1
3 para
0 até
faça
1
4
aloque espaço para posição do vetor
1
5 aloque espaço para um vetor
1
6 para
0 até
faça
1
7
[] 0
1
8 para i ← 0, j ← 0 até
faça
1
9
10
11
se nodo possui somente uma aresta de entrada
então
[] 1
para cada vértice adjacente a i faça
[ ]
12
13
14
15
16
17
18
para i ← 0, j ← 0 até
se
acc
1
1
1
1
1
1
∑
∑
1
faça
[ ] = então
[ ] nome de
acc + 1
+1
Vezes
1
1
1
1
1
1
1
[]
devolva
0
0
0
1
Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela
coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado
abaixo.
∑
Sabemos que ∑
, logo temos
Claramente
, onde
é a quantidade de vértices do grafo.
O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em
grafos de tamanhos variados. Os testes foram realizados em uma máquina de
processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2.
0,012
milissegundos
0,01
0,008
0,006
0,004
0,002
0
5
10
20
40
80
|V|
Figura 2. Tempo médio gasto para execução do algoritmo de descoberta de
vértices isolados em um grafo
2.3 Caminhamento em largura a partir de uma cidade
A execução do algoritmo a seguir exige um array para armazenar os vértices (nodos)
que foram ou não visitados. Ele é implementado usando uma abordagem estática e seu
tamanho é
ALGORITMO: CAMINHAMENTO EM LARGURA EM UM GRAFO
Entrada: : grafo; : nodo raiz do caminhamento
Saída: O caminhamento realizado
1
2
3
4
5
6
7
8
inicialize uma fila
insira o nodo raiz em
enquanto não for vazia faça
se primeiro elemento de não foi visitado então
visite o nodo
para cada vértice adjacente a faça
se não foi visitado então
insira
em
Custo
1
1
1
1
1
1
1
1
Vezes
1
1
Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela
coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado
abaixo.
Claramente
, onde
é a quantidade de vértices e
a quantidade de arestas do grafo.
O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em
grafos de tamanhos variados. Os testes foram realizados em uma máquina de
processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2.
0,002
0,0018
milisegundos
0,0016
0,0014
0,0012
0,001
0,0008
0,0006
0,0004
0,0002
0
5
10
20
40
80
|V|
Figura 3. Tempo médio gasto para execução do algoritmo de caminhamento em largura
2.4 Caminhamento em profundidade a partir de uma cidade
A execução do algoritmo a seguir exige um array para armazenar os vértices (nodos)
que foram ou não visitados. Ele é implementado usando uma abordagem estática e seu
tamanho é
ALGORITMO: CAMINHAMENTO EM PROFUNDIDADE EM UM GRAFO
Entrada: : grafo; : nodo raiz do caminhamento
Saída: O caminhamento realizado
Custo
1 visite o nodo raiz
1
2 para cada vértice adjacente a k faça
1
3
se não foi visitado então
1
4
1
execute o algoritmo partindo do nodo
Vezes
Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela
coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado
abaixo.
Claramente
vértices e
a quantidade de arestas do grafo.
, onde
é a quantidade de
Note que no pior caso, i. e., em um grafo denso temos que
2.5 Caminho entre as cidades
e
ALGORITMO: CAMINHO ENTRE DOIS NODOS DE UM GRAFO
Entrada: : grafo;
vetor de Strings onde será armazenado as estradas do
caminho;
inteiro auxiliar para índice do vetor vet; um ponteiro para a primeira
aresta da origem; : inteiro que armazena a posição da cidade destino no vetor do
grafo.
Saída: Inteiro, onde 1 significa que foi encontrado um caminho e 0 se não for
encontrado.
Custo
Vezes
1 se = nulo então
1
2
retorna 0
1
1
3 se (destino de A) = B então
1
1
4
[ ]
1
1
[
]
5
1
1
6 para
ate
,
proxima aresta faça
1
7
se destino de A for visitado então
1
1
8
[ ]
1
1
9
incrementa
1
1
10
visita a cidade de destino de i
1
1
se chama recursivamente a função mudando A
para primeira aresta da cidade destino apontada
por i então
devolva
senão
decrementa ind
11
12
13
14
15
16
fim para
devolva
1
1
1
1
1
1
Para cada aresta de um vértice a função pode ser chamada, recursivamente, no
máximo
vezes, portanto, no pior caso o algoritmo tem complexidade,
.
O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo em
grafos de tamanhos variados. Os testes foram realizados em uma máquina de
processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2.
0,12
milisegundos
0,1
0,08
0,06
0,04
0,02
0
5
10
20
40
80
|V|
Figura 4. Tempo médio gasto para execução do algoritmo de descoberta de
caminho entre dois vértices quaisquer.
2.6 Caminho entre as cidades
e
que não passe pela cidade
Esse algoritmo é similar ao de encontrar um caminho entre duas cidades quaisquer,
entretanto adicionando uma atribuição de visita a cidade a qual se deseja não passar.
Logo, a complexidade é de
.
2.7 Menor caminho entre as cidades
e
ALGORITMO: CUSTO MÍNIMO ENTRE VÉRTICES DE UM DIGRAFO (ALG. DIJKSTRA)
Entrada: : grafo; : nodo raiz do caminho;
Saída: : um vetor com o custo mínimo de sair de até qualquer nodo de
Custo
Vezes
1 aloque espaço para vetor de custos dos vértices
1
1
2 para cada posição
até
de faça
1
3
custo de
1
4
ID da cidade de origem até
1
5 custo de k
1
1
6 nome da estrada para chegar em
1
1
7 inicialize a fila
1
1
8 insira em
1
1
9 enquanto não estiver vazia faça
1
10
retire primeiro elemento de
1
11
para cada nodo v adjacente a faça
1
∑
12
se custo de
então
1
∑
13
custo de
peso da aresta + custo de
1
14
15
16
17
insira em
senão
se peso da aresta + custo de
custo de
custo faça
peso da aresta + custo de
1
1
∑
∑
18
1
devolva
1
Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela
coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado
abaixo.
∑
Sabemos que ∑
Mas no pior caso, grafo denso,
, logo temos
,
. Logo temos.
Claramente
, onde
é a quantidade de vértices do grafo.
ALGORITMO: COMPOSIÇÃO DO MENOR CAMINHO APÓS O CÁLCULO DE CUSTO MÍNIMO
Entrada: : um vetor com o custo mínimo de até todos os outros nodos de
: nodo raiz do caminho; : nodo de destino
Saída: : string com menor caminho entre e
Custo
Vezes
1 se custo de
então
1
1
2
devolva
1
1
3 inicialize a pilha
1
1
4
1
1
5
6
7
8
9
10
11
12
13
14
label de
label da aresta de custo mínimo de entrada
de
enquanto
faça
empilhe posição em
label de
label da aresta de custo mínimo de
entrada de
empilhe em
enquanto não for vazia faça
desempilhe S
concatene com o label de
devolva
1
1
1
1
1
1
1
1
1
1
1
1
1
Se somarmos o consumo de tempo de execução de todas as linhas, expresso pela
coluna ‘Vezes’, obteremos o tempo gasto pelo algoritmo no pior caso, como mostrado
abaixo.
Claramente
quantidade de vértices do grafo.
, onde
é a
A complexidade total da funcionalidade de obter-se o caminho mais curto entre
duas cidades quaisquer é dado pela agregação da complexidade dos dois algoritmos
apresentados acima. Logo a complexidade total de tempo é
{
}
.
O gráfico abaixo expressa o tempo médio gasto para a execução do algoritmo
em grafos de tamanhos variados. Os testes foram realizados em uma máquina de
processador dual-core de clock 2.2 GHz e 4 Gb de memória RAM DDR2.
0,0006
milisegundos
0,0005
0,0004
0,0003
0,0002
0,0001
0
5
10
20
40
80
|V|
Figura 5. Tempo médio gasto para execução da funcionalidade de encontrar o
menor caminho entre dois vértices quaisquer
3. Complexidade de Espaço
3.1 Quantidade de cidades e estradas
A complexidade de espaço do algoritmo é constante, ou seja, é representada por
.
Isto só é possível porque o número de vértices e arestas no grafo é conhecido. O grafo é
implementado usando lista de adjacência e a estrutura que modela o grafo possui dois
campos destinados para armazenar a quantidade de vértices
e de arestas
.
Portanto o algoritmo só precisa acessar esses valores e retorná-los.
3.2 Cidades isoladas
O espaço utilizado pelo algoritmo é determinado pelo tamanho do vetor de strings
e pelo vetor
. O primeiro vetor armazena o label dos vértices (nome das
cidades) isolados,
é estático, logo seu tamanho é
para todos os casos,
onde é uma constante que define o tamanho máximo de uma string. O vetor
armazena a informação se um vértice é ou não isolado, é um vetor estático e seu
tamanho é
.
A complexidade de espaço é portanto
.
3.3 Caminhamento em largura a partir de uma cidade
A complexidade de espaço do algoritmo é determinada pelo tamanho da fila e pelo
array
. Para a realização do caminhamento é necessário adicionar os vértices
do grafo na fila , logo, no pior caso, teremos com no máximo
elementos. Ao
visitar os vértices que estão em
é necessário atualizar o seu respectivo valor em
, como não é possível saber a priori, quais vértices terão seus valores em
alterado, faz-se necessário o armazenamento de um array de
posições. Portanto a
complexidade de espaço pode ser representada por
.
3.4 Caminhamento em profundidade a partir de uma cidade
A complexidade de espaço do algoritmo é determinado pela quantidade de chamadas
recursivas na pilha do sistema e pelo tamanho do array
. No pior caso o
algoritmo terá que fazer
chamadas recursivas, pois o grafo é denso e nas
primeiras vezes a condição se da linha 3 será satisfeita e ele fará as referidas chamadas.
Ao visitar os vértices é necessário atualizar o seu respectivo valor em
, como não
é possível saber a priori, quais vértices terão seus valores em
alterado, faz-se
necessário o armazenamento de um array de
posições. Portanto a complexidade de
espaço pode ser representada por
3.5 Caminho entre as cidades
e
Este algoritmo possui complexidade de espaço representado pelo tamanho gasto pelo
array de strings que armazena os labels das arestas (nomes das estradas). O array é
estático e deve ser capaz de armazenar no máximo
, ou seja, a complexidade de
espaço é dado por
.
3.6 Caminho entre as cidades
e
que não passe pela cidade
Este é similar ao algoritmo de encontrar um caminho entre duas cidades quaisquer,
entretanto adicionando uma atribuição de visita a cidade a qual se deseja não passar.
Logo sua complexidade de espaço é a mesma do algoritmo sem a restrição, ou seja,
.
3.7 Menor caminho entre as cidades
e
A complexidade de espaço é determinada pelo tamanho das seguintes estruturas usadas
no algoritmo: a fila , o vetor de etiquetas (custos de cada vértice) e a pilha . O vetor
tem tamanho constante em todos os casos, logo é necessário alocar
espaços na
memória para armazenar o custo de cada vértice. A fila e a pilha tem tamanhos variáveis
no decorrer da execução do programa, ambas são dinamicamente encadeadas, porém, no
pior caso, onde o grafo é denso, tanto quanto terão no máximo
elementos. Logo
a complexidade total de espaço é dado por
.