Universidade regional de blumenau



Baixar 1,07 Mb.
Página12/12
Encontro01.07.2018
Tamanho1,07 Mb.
1   ...   4   5   6   7   8   9   10   11   12

RESULTADOS E DISCUSSÃO


Nesta seção são apresentadas as comparações realizadas entre diversos algoritmos implementados no FGA e também uma breve discussão sobre os trabalhos correlatos.

Inicialmente são mostrados os resultados das comparações feitas com os algoritmos de grafos. As comparações foram efetuadas subdividindo os algoritmos em grupos. Cada grupo de algoritmos é utilizado para resolver o mesmo problema proposto. Todos os testes foram feitos em um camputador com processador Intel com velocidade de 2.0 GigaHertz (GHz) e 2 GBytes (GB) de memória.

A seguir são mostradas as semelhanças, diferenças, vantagens e desvantagens encontradas no presente trabalho em relação aos trabalhos correlatos. Por fim é descrita, de forma breve, a implementação de parte do FGA na linguagem Objective-C.

      1. Comparação entre algoritmos de fluxo


Utilizar o algoritmo certo para o problema em questão é fundamental para não comprometer o desempenho da aplicação. Um exemplo é mostrado na Tabela 1, onde a execução do algoritmo de Ford-Fulkerson é utilizada para encontrar o fluxo máximo em uma rede de fluxo.

Se houver a necessidade de escolher o fluxo máximo de custo mínimo, o tempo de execução do algoritmo é muito maior. Para um problema onde o tempo de processamento é crítico e não há necessidade de encontrar o custo mínimo do fluxo, não é viável a utilização do algoritmo de Dijkstra para distribuir o fluxo pelas rotas. Para este caso convém manter o algoritmo de busca em profundidade.



Tabela 1 – Comparação entre o algoritmo de Dijkstra e busca em profundidade

Vértices

Busca em profundidade

Dijkstra

Fluxo

Custo

Tempo(ms)

Fluxo

Custo

Tempo(ms)

10

63,78

8464,72

2

63,78

8330,53

7

30

248,64

58934,58

20

248,64

33229,07

62

60

1811,04

294781,04

69

1811,04

185502,11

622

100

1179,41

331843,56

114

1179,41

149274,08

915

200

2451,92

597813,16

245

2451,92

252038,08

19595

500

6594,15

1874917,23

2007

6594,15

685813,41

767539
      1. Comparação entre algoritmos de busca


A Tabela 2 mostra a comparação feita entre os algoritmos de busca em largura e busca em profundidade. Como elemento temporal de comparação foi adotado o tempo de abertura do vértice procurado, ou seja, quando o vértice de destino foi atingido. Observa-se que ambas as buscas tiveram médias semelhantes, o que demonstra que muito do desempenho dos dois algoritmos deve-se a localização do vértice que está sendo procurado. Caso o vértice esteja num nível mais profundo, então a busca em profundidade leva vantagem, enquanto que se o vértice estiver em níveis iniciais, a busca em largura mostra-se muito eficiente.

Para os testes foram gerados dois grafos aleatórios: um grafo dirigido simples e conexo e outro grafo não dirigido simples e conexo.

Tabela 2 – Comparação entre algoritmos de busca


Vértices

Tempo de abertura

Teste 1

Tempo de abertura

Teste 2

BFS

DFS

BFS

DFS

10

7

10

13

6

30

35

13

5

13

60

103

9

37

43

100

161

96

25

45

200

239

128

129

70

500

617

145

127

348
      1. Comparação entre algoritmos de geração de árvore de custo mínimo


A Tabela 3 mostra a comparação entre os algoritmos de Prim e de Kruskal, ambos resolvendo o problema de árvore geradora de custo mínimo. O grafo utilizado para todos os testes é não dirigido simples e conexo, já que o algoritmo de Prim não se aplica em casos de grafos desconexos ou dirigidos.

Observa-se que a implementação do algoritmo de Prim no FGA é relativamente mais rápido que o de Kruskal. Boa parte do custo temporal do algoritmo de Kruskal deve-se a estruturas auxiliares para manter as árvores geradores de custo mínimo.

Tabela 3 – Comparação entre algoritmos de geração de árvore de custo mínimo


Vértices

Prim

Kruskal

Custo

Tempo(ms)

Custo

Tempo(ms)

10

231,15

2

231.15

2

30

330,80

3

330,80

6

60

140,31

8

140,31

52

100

113,87

15

113,87

77

200

384,80

27

384,80

134

500

133,67

105

133,67

1019
      1. Comparação entre algoritmos de menor caminho


Os algoritmos de busca de menor caminho em um grafo utilizados na comparação foram os algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall. Como o propósito de cada algoritmo é diferente foram realizados diversos tipos de teste, sendo que o grafo utilizado para todos os testes foi um grafo dirigido simples.

O primeiro teste realizado foi o de efetuar apenas uma consulta, partindo de um vértice de origem qualquer até outro vértice de destino. A Tabela 4 como resultado o algoritmo de Dijkstra sempre com o melhor desempenho. Nota-se também que o algoritmo de Bellman-Ford executou mais rápido no teste com 100 vértices do que com 60 vértices. Isso se deve ao fato do algoritmo de Bellman-Ford depender do número de arestas do grafo. Evidentemente, pelo tempo de execução, o grafo com 60 vértices possuía mais arestas que o grafo com 100 vértices.



Tabela 4 – Comparação entre algoritmos de menor caminho em uma consulta

Vértices

Dijkstra

Bellman-Ford

Floyd-Warshall

Custo

Tempo(ms)

Custo

Tempo(ms)

Custo

Tempo(ms)

10

35,17

3

35,17

2

35,17

11

30

56,46

9

56,46

15

56,46

53

60

17,25

42

17,25

69

17,25

137

100

58,68

46

58,68

54

58,68

446

200

17,44

80

17,44

94

17,44

3775

500

4,49

1133

4,49

4531

4,49

77766

O segundo teste feito foi com um número maior de consultas, todas partindo de um mesmo vértice inicial. A Tabela 5 mostra o resultado das execuções dos algoritmos.

É possível notar que o algoritmo de Bellman-Ford é mais eficiente, com as novas circunstâncias de avaliação. Já o algoritmo de Dijkstra mostra-se perdendo desempenho à medida que o número de consultas aumenta. Por fim, o algoritmo de Floyd-Warshall manteve-se com tempo de execução praticamente igual nos dois testes.

Tabela 5 – Comparação entre os algoritmos com várias consultas tendo mesma origem



Vértices

Consultas

Dijkstra

Tempo(ms)

Bellman-Ford

Tempo(ms)

Floyd-Warshall

Tempo(ms)

10

5

4

1

6

30

15

107

40

56

60

30

201

47

171

100

50

631

65

439

200

100

6653

233

3882

500

250

158305

2318

75219

O terceiro teste efetuado leva em consideração o mesmo número de consultas anterior, porém o vértice de partida não é o mesmo.

Com esta nova configuração quem se destacou foi o algoritmo de Floyd-Warshall, que manteve o mesmo tempo de execução para os três tipos de teste efetuados. Para este novo problema os algoritmos de Dijkstra e Bellman-Ford mostraram-se pouco eficientes. A Tabela 6 mostra o resultado comparando os três algoritmos.

Tabela 6 – Comparação entre os algoritmos com várias consultas tendo origens diferentes



Vértices

Consultas

Dijkstra

Tempo(ms)

Bellman-Ford

Tempo(ms)

Floyd-Warshall

Tempo(ms)

10

5

8

11

13

30

15

79

77

57

60

30

214

326

151

100

50

1014

1657

436

200

100

13870

36652

4352

500

250

546846

1908240

85741
      1. Comparação entre trabalhos correlatos


Em relação aos trabalhos correlatos, verifica-se que o presente trabalho possui algumas funcionalidades semelhantes aos mesmos, como a disponibilidade de diversos algoritmos, persistência e geração de grafos. Como diferenciais tem-se o maior número de algoritmos implementados, a flexibilidade para a geração de grafos aleatórios e a extração de propriedades.

Quanto aos trabalhos de Braun (2009) e de Hackbarth (2008), observa-se que não são disponibilizadas opções para gerar instâncias aleatórias de grafos com finalidade de realizar testes. Já a JgraphT Team (2005) disponibiliza geração de tipos como grafos roda, estrela, ciclo e hiper cubo, enquanto que o FGA possui geração de grafos regulares, conexos ou desconexos, bipartidos e bipartidos completos, esparsos ou densos e simples ou multigrafos.

Outro ponto a ser destacado é o da checagem de propriedades. Dos três trabalhos apresentados, o de Braun (2009) permite extrair algumas propriedades, como o grafo ser completo, bipartido, cíclico, nulo, simples e regular. A JgraphT Team (2005) também testa propriedades e disponibiliza classes para verificar grafos biconectados, acíclicos ou ciclos, conexos ou desconexos.

Na persistência nota-se a preocupação em relação a outras aplicações. No trabalho de Braun (2009) e na biblioteca da Jgrapht Team (2005) é disponibilizada a exportação de grafos em formatos que podem ser abertos por outros softwares, enquanto que no FGA é disponibilizada uma função para persistir grafos em um formato XML, porém em uma estrutura de arquivo própria.

O Quadro 52 apresenta uma comparação entre os três trabalhos correlatos e o framework desenvolvido.





JgraphT (2005)

HACKBART (2008)

BRAUN (2009)

FGA (2010)

Permite criar grafos

Sim

Sim

Sim

Sim

Permite estender vértices, arestas e grafos

Sim

Não

Não

Sim

Permite gerar grafos

Sim

Não

Não

Sim

Permite persistir grafos

Sim

Não

Sim

Sim

Permite verificar propriedades

Sim

Não

Sim

Sim

Disponibiliza algoritmos

Sim

Sim

Não

Sim

Permite criar novos algoritmos

Sim

Não

Sim

Sim

Permite acompanhar execução de algoritmos

Sim

Sim

Sim

Não

Quadro 52 – Comparação entre trabalhos correlatos e o FGA
      1. O framework em Objective-C


Parte do FGA foi reescrita na linguagem Objective-C. Nesta versão estão disponíveis todas as classes responsáveis pela estrutura do grafo, com a verificação das mesmas propriedades desenvolvidas em Java. Além disso, todos os algoritmos também tiveram uma versão implementada em Objective-C.

Cada classe é composta por dois arquivos: um arquivo para a interface (.h) e outro arquivo para a implementação (.m).

Como exemplo é mostrada parte da implementação do algoritmo de Prim. O Quadro 53 detalha o conteúdo do arquivo AlgoritmoPrim.h, enquanto que o Quadro 54 mostra um trecho do arquivo AlgoritmoPrim.m.


#ifndef _ALGORITMOPRIM_

#define _ALGORITMOPRIM_

#import

#import

#import "AlgoritmoPrimResultado.h"

#import "GrafoNaoDirigido.h"

#import "PriorityQueue.h"
@interface AlgoritmoPrim: NSObject {

@private


AlgoritmoPrimResultado* resultado;

NSMapTable* naArvore;

PriorityQueue* fila;

}

-(AlgoritmoPrimResultado*) getResultado;



-(void) executar: (GrafoNaoDirigido*) g;

@end
#endif



Quadro 53 – Arquivo AlgoritmoPrim.h

#import "AlgoritmoPrim.h"

#import "Constante.h"


@implementation AlgoritmoPrim

-(AlgoritmoPrimResultado*) getResultado {

return resultado;

}
-(void) executar: (GrafoNaoDirigido*) g {

int tamanhoGrafo = [g getTamanho];

resultado = [[AlgoritmoPrimResultado alloc] init];

naArvore = [NSMapTable mapTableWithStrongToStrongObjects];

fila = [[PriorityQueue alloc] init: tamanhoGrafo];


NSMapTable* pares = [NSMapTable mapTableWithStrongToStrongObjects];
int i;

for (i = 0; i < tamanhoGrafo; i++) {

Vertice* v = [g getVertice: i];

[naArvore setObject:[NSNumber numberWithInt: 0] forKey: v];

[resultado setCusto: v andCusto: INF];

[resultado setPredecessor: v andPai: nil];


PairPriority* par = [[PairPriority alloc] init: v andCusto: 0.0];

[pares setObject: par forKey: v];

}
Vertice* x = [g getUmVertice];
PairPriority* par = [pares objectForKey: x];

[par setCusto: 0.0];

[fila push: par];
while ([fila count] > 0) {

PairPriority* p = [fila pop];


Vertice* u = (Vertice*) [p getDado];

{...}


Quadro 54 – Arquivo AlgoritmoPrim.m

Para armazenar os resultados obtidos foi utilizada a mesma idéia da versão desenvolvida em Java, onde para cada algoritmo existe uma classe correspondente responsável por manter o resultado. Como exemplo é apresentada a classe AlgoritmoPrimResultado e seus respectivos arquivos AlgoritmoPrimResultado.h (Quadro 55) e AlgoritmoPrimResultado.m (Quadro 56).



#ifndef _ALGORITMOPRIMRESULTADO_

#define _ALGORITMOPRIMRESULTADO_

#import

#import

#import "Vertice.h"

@interface AlgoritmoPrimResultado: NSObject {

@private

NSMapTable* predecessor;

NSMapTable* descendentes;

NSMapTable* custo;

NSMutableArray* arestas;

double custoTotal;

}

-(void) setPredecessor: (Vertice*) v andPai: (Vertice*) pai;



-(Vertice*) getPredecessor: (Vertice*) v;

-(void) addCustoTotal: (double) valor;

-(double) getCustoTotal;

-(void) addDescendente: (Vertice*) v andFilho: (Vertice*) filho;

-(NSMutableArray*) getDescendentes: (Vertice*) v;

-(void) addAresta: (Aresta*) a;

-(NSMutableArray*) getArestas;

-(void) setCusto: (Vertice*) v andCusto: (double) pCusto;

-(double) getCusto: (Vertice*) v;

@end


#endif

Quadro 55 – Arquivo AlgoritmoPrimResultado.h

#import "AlgoritmoPrimResultado.h"

#import "Constante.h"


@implementation AlgoritmoPrimResultado

-(id) init {

self = [super init];
predecessor = [NSMapTable mapTableWithStrongToStrongObjects];

descendentes = [NSMapTable mapTableWithStrongToStrongObjects];

custo = [NSMapTable mapTableWithStrongToStrongObjects];

arestas = [[NSMutableArray alloc] init];

custoTotal = 0.0;
return self;

}
-(void) setPredecessor: (Vertice*) v andPai: (Vertice*) pai {

[predecessor setObject: pai forKey: v];

}
-(Vertice*) getPredecessor: (Vertice*) v {

return [predecessor objectForKey: v];

}

{...}



Quadro 56 – Arquivo AlgoritmoPrimResultado.m

De forma similar a versão implementada em Java, a chamada dos métodos para criação dos grafos e execução de algoritmos é explanada no Quadro 57. Para o exemplo é utilizada a execução do algoritmo de Prim.



GrafoNaoDirigido* g = [[GrafoNaoDirigido alloc] init];
Vertice* v1 = [[Vertice alloc] init: 1];

Vertice* v2 = [[Vertice alloc] init: 2];

Vertice* v3 = [[Vertice alloc] init: 3];

Vertice* v4 = [[Vertice alloc] init: 4];


[v1 setDado: @"1"];

[v2 setDado: @"2"];

[v3 setDado: @"3"];

[v4 setDado: @"4"];


[g addVertice: v1];

[g addVertice: v2];

[g addVertice: v3];

[g addVertice: v4];


ArestaNaoDirigida* a1 = [[ArestaNaoDirigida alloc] init: 1 andVi: v1 andVj: v2];

[a1 setValor: 10923.0];

ArestaNaoDirigida* a2 = [[ArestaNaoDirigida alloc] init: 2 andVi: v1 andVj: v3];

[a2 setValor: 1235.0];

ArestaNaoDirigida* a3 = [[ArestaNaoDirigida alloc] init: 3 andVi: v2 andVj: v3];

[a3 setValor: 1200.0];

ArestaNaoDirigida* a4 = [[ArestaNaoDirigida alloc] init: 4 andVi: v1 andVj: v4];

[a4 setValor: 1000.0];


[g addAresta: a1];

[g addAresta: a2];

[g addAresta: a3];

[g addAresta: a4];


AlgoritmoPrim* alg = [[AlgoritmoPrim alloc] init];

[alg executar: g];

AlgoritmoPrimResultado* res = [alg getResultado];
printf("Resultado: %lf\n", [res getCustoTotal]);


Quadro 57 – Execução do algoritmo de Prim

  1. CONCLUSÕES


Os resultados obtidos com o desenvolvimento do FGA foram considerados satisfatório, pois os requisitos propostos foram cumpridos, e, além disso, o FGA conta com uma série de outros recursos não mencionados inicialmente na proposta. O objetivo final do trabalho foi atingido, que é a disponibilização de um framework de algoritmos de grafos que contivesse desde algoritmos clássicos, funções de geração de grafos com base em restrições e por fim, verificação de propriedades.

Com a utilização do FGA foi possível comparar o desempenho dos algoritmos implementados. Foram feitas diversas baterias de testes com diferentes tipos de problemas a fim de verificar qual é a melhor situação para utilizar cada algoritmo.

Com o recurso de gerar grafos aleatórios foi possível criar instâncias de grafos com mais vértices e arestas. As instâncias geradas puderam ser facilmente verificadas se estão corretas utilizando o recurso de testar propriedades dos grafos.

Além disso, a persistência permite ao usuário salvar o grafo em que está trabalhando. Tal recurso facilita o transporte do grafo de um lugar para outro. Por ser um framework, é possível que o grafo possa ser persistido em outros formatos, já que para isso basta implementar a função de persistência para acessar os atributos de vértices e arestas. A biblioteca DOM apresentou grande importância na persistência do grafo, sendo que a partir dela é feito todo o controle de geração e recuperação de dados no modelo XML.

Como principal limitação do trabalho tem-se o fato de não haver uma maneira de ver a representação de um grafo na forma gráfica. No entanto, a aplicação de teste mostra de maneira simples o conjunto de vértices e arestas, tendo disponíveis funções para adicionar e remover os mesmos.

Outra limitação encontrada é o baixo desempenho da linguagem Java. Para instâncias grandes de grafos há uma demora demasiada tanto na geração de grafos como na execução de algum algoritmo sobre o grafo em questão. Cabe uma investigação mais profunda sobre este problema, podendo ser feita a comparação entre as implementações em Java e em Objective-C.

O grande consumo de memória também foi outro fator crítico enfrentado principalmente nos algoritmos de geração de grafos. Um exemplo é na geração de grafos densos de mais de 1000 vértices. Para que ele seja considerado denso é necessário que ele contivesse no mínimo 1000000 arestas. Tanto para arestas como vértices há atributos em questão, portanto este grafo pode consumir mais de 100Mb de memória.

Por fim, está aberto um horizonte para trabalhos futuros, desde implementação de novos algoritmos, verificação de outras propriedades, além de gerar um novo módulo para visualização gráfica dos grafos criados.


    1. EXTENSÕES


Como extensão para este trabalho sugere-se verificar outras propriedades de grafos, tais como o grafo cordal, hipercubo, perfeito, cactos, planar, isomorfo a outro grafo, entre outras. Além disso, disponibilizar funções para que sejam gerados estes tipos de grafos.

Sugere-se também a implementação de recursos que permitam ao usuário trabalhar com o grafo em uma forma visual.

Outra sugestão é a possibilidade de exportar o grafo para outros formatos, facilitando assim a integração com outras aplicações.

Por fim, sugere-se a implementação de outros algoritmos clássicos de grafos, tais como emparelhamento perfeito, clique máximo, ciclo hamiltoniano, ciclo euleriano, relabel-to-front, Boruvka, entre outros.

Referências bibliográficas

ALSUWAIYEL, Muhammad H. Algorithms: design techniques and analysis. Singapore: World Scientific Publishing, 2003.

BRAUN, Susan. Ferramenta visual para criação e execução de algoritmos aplicados sobre teoria dos grafos. 2009. 74 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Centro de Ciências Exatas e Naturais, Universidade Regional de Blumenau, Blumenau.

CORMEN, Thomas H. et al. Introduction to algorithms. 2nd ed. Cambridge: MIT, 2001.

EPPSTEIN, David. Strong connectivity. [California], 2001. Disponível em: . Acesso em: 30 ago. 2010.

FEOFILOFF, Paulo; KOHAYAKAWA, Yoshiharu; WAKABAYASHI, Yoshiko. Teoria dos grafos: uma introdução sucinta. [São Paulo], 2009. Disponível em: . Acesso em: 27 fev. 2010.

FLEMING, Kermin; CRUTCHFIELD, Chris. Minimum cost maximum flow, minimum cost circulation, cost/capacity scaling. [Cambridge], 2006. Disponível em: . Acesso em: 10 ago. 2010.

GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos em Java. 4. ed. Porto Alegre: Bookman, 2007.

______. Projeto de algoritmos: fundamentos, análise e exemplos da Internet. Tradução Bernardo Copstein. Porto Alegre: Bookman, 2004.

GROSS, Jonathan L.; YELLEN, Jay. Graph theory and its applications. 2nd ed. Boca Raton: CRC, 2006.

HACKBARTH, Rodrigo. Ferramenta para representação gráfica do funcionamento de algoritmos aplicados em grafos. 2008. 61 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) - Centro de Ciências Exatas e Naturais, Universidade Regional de Blumenau, Blumenau.

JGRAPHT TEAM. JgraphT: a free Java graph library. [S.l.], 2005. Disponível em: . Acesso em: 13 mar. 2010.

KOCAY, William; KREHER, Donald L. Graphs, algorithms, and optimization. Boca Raton: Chapman & Hall/CRC, 2005.

LAU, Hang T. A Java library of graph algorithms and optimization. Boca Raton: Chapman & Hall/CR, 2007.

LIPSCHUTZ, Seymour; LIPSON, Marc. Matemática discreta. 2. ed. Porto Alegre: Bookman, 2004.

ORACLE TEAM. JDK 5.0 Javadoc technology. [S.l.], [2005?]. Disponível em: . Acesso em: 10 ago. 2010.

RABUSKE, Márcia A. Introdução a teoria dos grafos. Florianópolis: Ed. da UFSC, 1992.

SAUVÉ, Jacques P. O que é um framework? [Campina Grande], [2007?]. Disponível em: . Acesso em: 13 mar. 2010.

SCHEINERMAN, Edward R. Matemática discreta: uma introdução. Tradução Alfredo Alves de Farias. São Paulo: Pioneira, 2003.

SKIENA, Steven S.; REVILLA, Miguel. Programming challenges: the programming contest training manual. New York: Springer-Verlag, 2003.



WORLD WIDE WEB CONSORTIUM. XML DOM introduction. [S.l.], [2010?]. Disponível em: . Acesso em: 10 ago. 2010.

1 Sauvé (2007) define framework como sendo um conjunto de classes e interfaces que provê soluções para uma família de problemas semelhantes.



1   ...   4   5   6   7   8   9   10   11   12


©livred.info 2017
enviar mensagem

    Página principal