Visualizar - Polis Educacional

Transcrição

André Carlos de Almeida
R.A: 0409018 – 8º Semestre
ESTUDO DE METODOLOGIAS E FERRAMENTAS PARA
DETERMINAÇÃO DE ROTAS DE MENOR CAMINHO
Jaguariúna
2008
André Carlos de Almeida
R.A: 0409018 – 8º Semestre
ESTUDO DE METODOLOGIAS E FERRAMENTAS PARA
DETERMINAÇÃO DE ROTAS DE MENOR CAMINHO
Monografia apresentada à disciplina Trabalho
de Graduação III, do curso de Ciência da
Computação da Faculdade de Jaguariúna, sob
orientação do Prof. Sílvio Petroli Neto, como
exigência essencial para conclusão do curso de
graduação.
Jaguariúna
2008
2
ALMEIDA, André Carlos de. Estudo de Metodologias e Ferramentas para Determinação
de Rotas de Menor Caminho. Monografia defendida e aprovada na FAJ em 23 de junho de
2008 pela banca examinadora constituída pelos professores:
Prof. Ms. Peter Jandl Junior
Prof. Ademário Araújo Junior
Prof. Silvio Petroli Neto - Orientador
3
A meus pais, amigos e professores
Com sabedoria e paciência, depositaram confiança em mim, e também pelo entusiasmo
com que me motivaram a concluir este trabalho.
4
AGRADECIMENTOS
Meus agradecimentos ao meu orientador, que me deu todo o apoio, incentivo e
conhecimento, compartilhando suas idéias e reflexões.
Agradeço também aos meus amigos de trabalho que contribuíram com discussões
técnicas de grande valia para a elaboração do trabalho.
Aos meus amigos Thiago, Rodrigo, Adriano, Guilherme, Heitor, Gabriel, Marilia, Aline,
Daniela, Fernanda, meu tio Joaquim que sempre me apoiou, e em especial Carlos e Ana
Elisa por suas oportunas e relevantes contribuições.
5
Se você quer acertos, esteja preparado para os erros.
(Carl Yastrzemski)
6
ALMEIDA, André Carlos de. Estudo de Metodologias e Ferramentas para Determinação
de Rotas de Menor Caminho. 2008. Monografia (Bacharelado em Ciência da Computação)
– Curso de Ciência da Computação da Faculdade de Jaguariúna, Jaguariúna.
RESUMO
A necessidade de rapidez e economia de recursos se torna cada vez maior e mais
significativa. Partindo dessa idéia, este trabalho tem como objetivo o auxilio à decisões
cotidianas, como por exemplo, definir a menor rota entre dois municípios, para que o usuário
obtenha um fator de ajuda na referida decisão. São abordados assuntos referentes à
linguagem C#, que faz parte da plataforma .NET criada pela Microsoft ®, teoria de grafos,
algoritmos de menor caminho, fazendo referência a dois algoritmos em especial, que são
Dijkstra e Bellman-Ford, o segundo tendo a opção de calcular rotas em grafos com arcos de
valor negativo, porém, não utilizado no escopo do trabalho. Este trabalho apresenta a
criação de um sistema para definição de caminho mais curto, entre cidades pré-dispostas
em um grafo no próprio sistema, por meio de alimentação via interface gráfica.
Palavras-chave: GRAFO, DIJKSTRA, C#.
7
ALMEIDA, André Carlos de. Study of Methodologies and Tools for Determination of
Routes of Lesser Way. 2008. Monograph (Bachelor in Computer Science) – Computer
Science course at Faculty de Jaguariúna, Jaguariúna.
ABSTRACT
The necessity of rapidity and economy of resources it becomes each bigger and more
significant. Leaving of this idea, this work has as objective I assist it to the daily decisions, as
for example, to define the lesser route between two cities, so that the user gets a factor of aid
in the related decision. They are boarded referring subjects to the C# language, that is part of
the .NET platform, created by Microsoft ®, theory of graphs, algorithms of lesser way,
making reference the two algorithms in special, that they are Dijkstra and Bellman-Ford, and
this last having the option to calculate routes in graphs with arcs of negative value, however,
not used in the scope of work. This work presents the creation of a system for defining the
shortest way, beetween cities pre-arranged in a graph in the own system, throug fed by
graphical interface.
Keywords: GRAPH, DIJKSTRA, C#.
8
SUMÁRIO
1. INTRODUÇÃO ............................................................................................................................................... 12
2. TEORIA DOS GRAFOS ................................................................................................................................ 13
2.1. APLICAÇÕES DE GRAFOS ............................................................................................................................ 13
2.2 CAMINHO DE CUSTO MÍNIMO ...................................................................................................................... 14
3.ALGORITMOS DE MENOR CAMINHO .................................................................................................... 15
3.1. ALGORTIMO DE BELLMAN-FORD ................................................................................................................ 15
3.2. ALGORITMO DE DIJKSTRA .......................................................................................................................... 16
3.2.1. Funcionamento do Dijkstra ............................................................................................................... 17
4. PLATAFORMA DE IMPLEMENTAÇÃO .................................................................................................. 22
4.1. PLATAFORMA .NET.................................................................................................................................... 22
4.1.1. Termos da Plataforma .NET .............................................................................................................. 22
4.1.2. Web Services XML ................................................................................ Erro! Indicador não definido.
4.2. VISUAL STUDIO 2005 EXPRESS E 2008 EXPRESS ........................................................................................ 24
4.2.1. Linguagem de Programação C# ........................................................................................................ 24
5. DETALHAMENTO DO ALGORITMO....................................................................................................... 25
5.1. GRAFO PRÉ-DISPOSTO NO ALGORITMO........................................................................................................ 25
5.1.1. Diagrama de Classes ......................................................................................................................... 25
5.1.2. Fluxograma UML .............................................................................................................................. 26
6. DESENVOLVIMENTO DA APLICAÇÃO.................................................................................................. 28
6.1. IMPLEMENTAÇÃO DO CÓDIGO: ALGORITMO DIJKSTRA EM C#.................................................................... 28
6.2. INTERFACE HOMEM MÁQUINA .................................................................................................................... 31
7. CONCLUSÃO ................................................................................................................................................. 34
8. REFERÊNCIAS BIBLIOGRÁFICAS........................................................................................................... 35
9
Lista de Siglas
ECMA – EUROPEAN COMPUTER MANUFACTURER’S ASSOCIATION
DAG – DIRECTED ACYCLIC GRAPH
CLI – COMMON LANGUAGE INFRASTRUCTURE
CTS – COMMON TYPE SYSTEMS
CIL – COMMON INTERMEDIATE LANGUAGE
FCL – FRAMEWORK CLASS LIBRARY
CLR – COMMON LANGUAGE RUNTIME
CLS – COMMON LANGUAGE SPECIFICATION
XML – EXTENSIBLE MARKUP LANGUAGE
UML – UNIFIED MODELING LANGUAGE
VCL – VISUAL COMPONENT LIBRARY
10
Lista de Figuras
FIGURA 1: GRAFO QUE DEMONSTRA A QUESTÃO-PROBLEMA....................................................... 13
FIGURA 2: FIGURA 2: PSEUDOCÓDIGO BELLMAN-FORD................................................................... 15
FIGURA 3: PSEUDOCÓDIGO BELLMAN-FORD........................................................................................ 16
FIGURA 4: PASSO 1 DA IMPLEMENTAÇÃO DIJKSTRA......................................................................... 17
FIGURA 10: GRAFO PADRÃO DO SISTEMA.............................................................................................. 25
FIGURA 11: DIAGRAMA DE CLASSES DO SISTEMA .............................................................................. 26
FIGURA 12: FLUXOGRAMA UML DO SISTEMA ...................................................................................... 27
FIGURA 13: CÓDIGO PRINCIPAL DO SISTEMA ...................................................................................... 28
FIGURA 17: INTERFACE GRÁFICA DO SISTEMA ................................................................................... 32
FIGURA 18: MENU “ARQUIVO” E AS OPÇÕES CONTIDAS................................................................... 32
FIGURA 19: MENU “INSERIR CIDADES” ................................................................................................... 32
FIGURA 20: MENU “CUSTO DE ROTA” ...................................................................................................... 33
FIGURA 21: CAMPOS PARA SELEÇÃO DAS CIDADES DE PARTIDA E DESTINO........................... 33
11
1. INTRODUÇÃO
Hoje em dia a otimização de processos está em alta. Tudo deve ser rápido, fácil
e objetivo. E isso deve-se à preocupação com a escassez de tempo e recursos
utilizados. Analisando essa necessidade, tudo deve ser feito pelo “caminho mais
curto”, ou seja, do modo mais rápido e econômico.
Como exemplo, tem-se uma situação na qual uma pessoa precisa ir de uma
cidade à outra e necessita de informações tais como distância, número de pedágios,
quantidade de litros de combustível que deverá ser utilizado e quais as rotas
possíveis, optando pelo caminho mais curto e mais barato. Dessa maneira conseguese um planejamento simples, mas que auxilia muito.
Essa pesquisa enfatiza a otimização de processos, aliada à princípios de teoria
de grafos, ou seja, criação de um sistema que reproduza a ação humana de pesquisar
caminhos, distâncias, rotas, contribuindo para relativa melhora na velocidade dessa
ação.
Através do Algoritmo de Dijkstra para cálculo do caminho de custo mínimo ou
menor caminho que também implica em menor custo, é possível a criação de um
software para desenvolvimento de grafos demonstrando o menor caminho a ser
percorrido. Através da definição de uma origem e um destino em um grafo que contem
varias possibilidades de caminho e de custo, o algoritmo de Dijkstra calcula e define o
melhor caminho a ser percorrido.
12
2. TEORIA DOS GRAFOS
De acordo com Tenenbaum, um grafo consiste num conjunto de nós ou vértices e num
conjunto de arcos ou arestas. Cada arco no grafo é especificado por um par de nós.
Se os pares de nós que formam os arcos forem pares ordenados, diz-se que o grafo é
um grafo orientado ou dígrafo (Tenenbaum, 1995).
Um grafo não precisa necessariamente ser uma árvore, mas uma árvore tem que ser
um grafo. Outra observação é que um nó não precisa ter grafos associados a ele.
Um nó v incide em um arco y se v for um de seus nós no par ordenado que eles
formam x.
A graduação de um nó é o número de arcos ou arestas que têm v como cabeça, e a
graduação de saída de v é o número de arcos que tem v como terminação da seta.
Um nó v será adjacente a um nó u se existir um arco de v até u. Se v for adjacente a u,
v será chamado de sucessor de u, e u chamado predecessor de v.
Um grafo onde existem valores associados a cada arco, é chamado de Grafo
Ponderado, ou Rede, e o valor de cada arco é denominado Peso.
Um caminho de comprimento L do nó a ao nó b é definido como uma seqüência de
L+1 nós.
Nós que possuem caminhos para si mesmos, são chamados Ciclos. Se um grafo
contiver um ciclo, será um grafo cíclico, senão será acíclico ou DAG, iniciais de
directed acyclic graph.
2.1. Aplicações de Grafos
Grafos podem ser aplicados em várias situações, como representação de um grupo de
cidades e suas respectivas estradas de ligação, para conseguir descobrir o caminho
mais curto entre duas delas. A seguir uma breve ilustração dessa aplicação usando
grafo ponderado.
Figura 1: Grafo que demonstra a questão-problema.
13
No grafo acima estão dispostas cinco cidades da região de Campinas, com suas
respectivas estradas de ligação e cidades adjacentes. Para descobrirmos o menor
caminho entre duas das cidades presentes neste grafo, Utilizaremos o algoritmo de
Dijkstra.
Considerando o nó de origem como sendo a cidade de Pedreira e o nó de destino
como sendo a cidade de Holambra, o algoritmo deverá encontrar o caminho mais curto
entre os 2 nós, fazendo o teste para todas as rotas possíveis. Assim o conjunto PERM,
conterá os nós escolhidos depois de comparados inicialmente conterá apenas a
cidade de Pedreira, e para cada nó fora de PERM, manteremos a menor distancia
entre o mesmo e Pedreira, usando caminhos onde o único nó que não esteja em
PERM seja ele.
O próximo passo é adicionar esse novo nó que possui a menor distância em PERM.
Este último nó adicionado será agora o nó atual, a partir de onde serão refeitos os
cálculos de distância para os nós adjacentes a ele que não estiverem em PERM, pois
pode haver um caminho menor de Pedreira, passando pelo nó atual do que o que
havia antes do atual ser adicionado ao conjunto. Caso isso acontecer, o caminho
deverá ser atualizado.
Essa rotina acontecerá tantas vezes quanto for necessário, para que o algoritmo
chegue até o nó de destino, previamente proposto pelo usuário.
Outro exemplo seria uma rede de canalização de água de um município, com as rotas
que a água poderia fazer passando pela tubulação, para quem sabe resolver
problemas de distância e desnível da tubulação, implicando na melhoria do serviço
público.
2.2 Caminho de Custo Mínimo
De acordo com a situação apresentada na introdução, existem necessidades de se
encontrar um “Caminho de Custo Mínimo”, que como como o próprio nome indica, é
um caminho de uma posição à outra, de modo que a soma dos pesos das arestas que
as interligam seja minimizada.
Há alguns exemplos de algoritmos que podem ser utilizados nesses casos, como por
exemplo Dijkstra, que soluciona o problema em um grafo dirigido ou não dirigido com
arestas de peso não negativo. O algoritmo usado para solucionar o mesmo problema
em um grafo com pesos negativos é o algoritmo de Bellman-Ford. Outro exemplo
também é o Algoritmo de Floyd-Warshall que resolve o problema de calcular o
caminho mais curto entre todos os pares de vértices em um grafo orientado e
valorado. Esses são apenas alguns algoritmos para essa finalidade e há vários outros.
14
3.ALGORITMOS DE MENOR CAMINHO
3.1. Algortimo de Bellman-Ford
O Algoritmo de Bellman-Ford funciona de forma semelhante ao de Dijkstra, que será
visto no próximo subtítulo, porém resolve o problema de caminho mínimo de um modo
mais geral, que é quando há arestas com pesos negativos, onde o Algoritmo de
Dijkstra não funciona bem o suficiente. Esse algoritmo retorna FALSE quando
encontra arestas com pesos negativos, indicando não haver uma solução, e retorna
TRUE indicando que conseguiu o caminho mais curto de acordo com o que foi
solicitado pelo usuário.
função BellmanFord(lista vértices, lista arestas, vértice origem)
// Esta implementação recebe um grafo representado como uma
// lista de vértices e arestas e modifica os vértices para
// que que seus atributos distância e anterior armazenem
// os caminhos mais curtos.
// Passo 1: Inicializar o grafo
para cada vértice v em vértices faça:
se v é origem então:
v.distância = 0
senão:
v.distância := infinito
v.anterior := nulo
// Passo 2: Ajustar as arestas repetidamente
repita tamanho (vértices) vezes:
para cada aresta uv em arestas faça:
u := uv.origem
v := uv.destino
// uv é a aresta de u para v
se v.distância > u.distância + uv.peso então:
v.distância := u.distância + uv.peso
v.anterior := u
Figura 2: Pseudocódigo Bellman-Ford
15
// Passo 3: Verificar a existência de ciclos com peso negativo
para cada aresta uv em arestas faça:
u := uv.origem
v := uv.destino
se v.distância > u.distância + uv.peso então:
erro "O grafo contém um ciclo de peso negativo."
Figura 3: Pseudocódigo Bellman-Ford
3.2. Algoritmo de Dijkstra
O algoritmo de Dijkstra calcula o caminho de custo mínimo entre vértices de um
grafo. Um grafo é representado como um conjunto de vértices ligados por retas ou
arestas, as arestas podem ser direcionadas, e são representadas por “setas”.
Escolhido um vértice como raiz de busca, este algoritmo calcula o custo mínimo
deste vértice para todos os demais vértices do grafo. Apesar de não garantir
resultados com exatidão diante de arcos com valores negativos, mas sua performance
é de um nível bom e não é muito complicado de implementar.
Esse algoritmo parte de uma estimativa inicial para o custo mínimo e vai
sucessivamente ajustando esta estimativa.
Ele considera que um vértice esteja fechado quando já tiver sido obtido um
caminho de um custo mínimo do vértice tomado como raiz da busca até ele.
Seja G(V,A) um grafo orientado e s um vértice de G:
1. Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e
infinito às demais estimativas;
2. Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice
que precede t no caminho de custo mínimo de s para t);
3. Enquanto houver vértice aberto:
• seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os
vértices abertos;
• feche o vértice k
• Para todo vértice j ainda aberto que seja sucessor de k faça:
•
some a estimativa do vértice k com o custo do arco que une k a j;
•
caso esta soma seja melhor que a estimativa anterior para o vértice j,
substitua-a e anote k como precedente de j.
16
3.2.1. Funcionamento do Dijkstra
Assumindo-se um conjunto denominado PERM, que conterá inicialmente apenas o nó
de origem S. A qualquer momento PERM contém todos os nós cujos menores
caminhos já foram determinados, usando apenas vértices em PERM a partir de S.
Para cada nó X
fora de PERM manteremos a menor distância dist[X] de S a X
utilizando caminhos onde o único vértice que não está em PERM seja X. Será
fundamental também armazenar o nó adjacente (precedente) a X no caminho, em
caminho[X].
Continuando, pega-se o nó, entre todos os que ainda não pertencem a PERM, com
menor distância dist e adiciona-se este nó que será chamado de atual a PERM, e
recalcula-se as distâncias para todos os nós adjacentes a ele que não não façam parte
de PERM, pois pode haver um caminho menor a partir de S, passando por atual, do
que o que estava antes de atual ser adicionado a PERM. Se houver um caminho mais
curto será necessário atualizar caminho[X] de forma que atual é o vértice adjacente a
X pelo novo caminho mínimo.
•
Inicialmente todos os nodos têm um custo infinito, exceto s (a raiz da busca) que tem
valor 0:
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
∞
∞
∞
∞
PRECEDENTES
-
-
-
-
-
Figura 4: Passo 1 da Implementação Dijkstra
•
seleciona s (vértice aberto de estimativa mínima)
•
fecha s
•
recalcula as estimativas de u e x
17
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
10
∞
5
∞
PRECEDENTES
-
S
-
S
-
Figura 5: Passo 2 da Implementação Dijkstra (UFSCAR, 2008)
•
seleciona x (vértice aberto de estimativa mínima)
•
fecha x
•
recalcula as estimativas de u,v e y
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
8
14
5
7
PRECEDENTES
S
X
X
S
X
•
seleciona y (vértice aberto de estimativa mínima)
•
fecha y
•
recalcula a estimativa de v
18
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
8
14
5
7
PRECEDENTES
S
X
X
S
X
•
selecione u (vértice aberto de estimativa mínima)
•
feche u
•
recalcule a estimativa de v
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
8
9
5
7
PRECEDENTES
S
X
X
S
X
•
seleciona v (vértice aberto de estimativa mínima)
•
fecha v
19
VÉRTICES
S
U
V
X
Y
ESTIMATIVAS
0
8
9
5
7
PRECEDENTES
S
X
U
S
X
Quando todos os vértices tiverem sido fechados, os valores obtidos serão os custos
mínimos dos caminhos que partem do vértice tomado como raiz da busca até os
demais vértices do grafo. O caminho propriamente dito é obtido a partir dos vértices
chamados acima de precedentes.
Para exemplificar, considere o caminho de custo mínimo que vai de s até v, cujo custo
mínimo é 9. O vértice precendente de v na última das tabelas acima é u. Sendo assim,
o caminho é:
s → ... → u → v
Por sua vez, o precedente de u é x. Portanto, o caminho é:
s → ... → x → u → v
Por último, o precedente de x é o próprio vértice s. Logo, o caminho de custo mínimo
é:
s → x → u → v
Como apresentado o algoritmo de Dijkstra computa apenas um único caminho de
custo mínimo entre um dado par de vértices. Para se obter todos os caminhos de
custo mínimo entre dois vértices é necessário modificar a forma de anotação dos
precedentes. A modificação no passo 3 indicada a seguir é suficiente para permitir o
cômputo de todos os caminhos por um processo similar ao descrito acima.
Para todo vértice j ainda aberto que seja sucessor de k faça:
20
•
some a estimativa do vértice k com o custo do arco que une k a j;
•
caso esta soma seja melhor que a estimativa anterior para o vértice j,
substitua-a e anote k como precedente único de j;
•
caso esta soma seja igual à estimativa anterior para o vértice j, adicione k ao
conjunto dos precedentes de j;
Supondo que o peso do arco (y,v) no grafo acima fosse 2, haveriam dois caminhos de
custo mínimo do vértice s para v. Esta duplicidade resulta em dois precedentes para o
vértice v: Sendo assim, os dois caminhos são dados por: (s → ... → u → v) e (s → ...
→ y → v). Seguindo as precedências para u e y nestes dois casos obtemos os dois
caminhos: (s → x → u → v) e (s → x → y → v).
21
4. PLATAFORMA DE IMPLEMENTAÇÃO
4.1. Plataforma .NET
Plataforma de software criada pela Microsoft
®
que conecta informações,
sistemas, pessoas e dispositivos. Foi desenvolvida sobre os padrões Web Services
XML, fornece conectibilidade à sistemas e aplicativos, sejam novos ou já existentes,
independente de seu sistema operacional, tipo de computador, dispositivo ou
linguagem usada na sua criação.
A idéia principal dessa plataforma é a mudança de foco da área de informática,
que deve passar de web sites e dispositivos isolados, para vários dispositivos,
computadores, transações e serviços que estejam conectados diretamente e
trabalhando em conjunto, o que auxiliaria para soluções mais amplas.
Sua funcionalidade básica foi passada para a ECMA (European Computer
Manufacturer’s Association – Associação de Fabricantes de Computador Europeus) e
está em processo de padronização.
Resumindo, o recurso básico da plataforma .NET é que permite a execução do
código intermediário compilado por várias linguagens de programação diferentes,
desde que sejam compatíveis com uma definição comum para os tipos de dados
básicos. (Cantù, 2003)
A seguir, teremos os termos que constituem essa plataforma.
4.1.1. Termos da Plataforma .NET
• CLI (Common Language Infrastructure – Infra-Estrutura de Linguagens Comum): é a
base da plataforma, e compreende muitas especificações diferentes.
o
CTS (Common Type Systems – Sistemas de Tipos Comum): cria a fundação
para integrar linguagens de programação diferentes, e especifica como os
tipos de dados serão declarados e usados, e os compiladores de linguagem
devem ser compatíveis, para utilizarem-se dessa integração independente de
linguagem fornecida pela plataforma .NET.
o
Metadados Extensíveis: cada unidade de implantação, chamada assembly,
deve descrever a si mesma. Desse modo, um assembly deve trazer consigo
seus dados de identificação (nome, versão, cultura e chave pública
opcionais), dados que descrevem os tipos definidos dentro do assembly,
dados que relacionam os outros arquivos referenciados e todas as
22
permissões especiais de segurança exigidas. Acerca disso, sistema de
metadados pode ser estendido, ou seja, personalizado pelo usuário.
o
CIL (Common Intermediate Language – Linguagem Intermediária Comum):
linguagem de programação de um ambiente de execução virtual com um
microprocessador abstrato, ou seja, os compiladores que têm como destino a
plataforma .NET não geram instruções de CPU nativas, mas sim instruções
na linguagem intermediária do processador abstrato.
o
P/Invoke : os programas executados no ambiente de tempo de execução são
reproduzidos em sua própria sandbox particular, entretanto esse ambiente de
tempo não substitui completamente a API Win32, portanto deverá haver um
modo mais fácil de fazer uma ponte entre os dois. Essa tal ponte chama-se
Platform Invocation Service (Serviço de Chamadas de Plataforma).
o
FCL (Framework Class Library – Biblioteca de Classes da Estrutura):
hierarquia de classes semelhante à VCL da Borland, mas a primeira tendo
uma abrangência em muito mais áreas de programação. A vantagem da FCL
está no fato de que partes da hierarquia de classes podem ser fatoradas,
como exemplo, criar uma versão simples a ser usada em um dispositivo
portátil.
o
Formato de Arquivos PE (Extended Portable Executable – Executável
Portátil) Estendido: a Microsoft
®
está utilizando seu formato de arquivo-
padrão, usado pelos arquivos-padrão executáveis no Win32, para dar o
suporte necessário aos requisitos de metadados da CLI. A vantagem do seu
uso é o fato de o sistema operacional poder carregar um aplicativo .NET da
mesma maneira que carregaria um aplicativo Win32 nativo.
•
CLR (Common Language Runtime – Ambiente de Tempo de Execução de
Linguagens Comum): enquanto a CLI é uma especificação, o CLR é a
implementação dessa especificação feita pela Microsoft ®. O CLR é responsável por
todos os aspectos do universo .NET, como o carregamento da imagem executável,
verificação de sua identidade e segurança quanto a tipos de dados, compilação do
código CIL em instruções nativas de CPU e gerenciamento do aplicativo durante sua
vida útil.
o
CLS (Common Language Specification – Especificação de Linguagens
Comum): Estreitamente ligada ao CTS, é um subconjunto da especificação
que define as regras que governam o modo como os tipos criados nas
diferentes linguagens de programação podem operar cooperativamente,
tendo como objetivo encontrar um denominador comum entre elas. (Cantù,
2003)
23
4.2. Visual Studio 2005 Express e 2008 Express
O Visual Studio é um kit de desenvolvimento de software criado pela Microsoft ® que auxilia
programadores a integrarem ferramentas, editores, linguagens e diversas ferramentas já
incluídas no pacote. Ótima ferramenta para desenvolvimento web ou desktop, com interface
amigável e relativamente simples.
As versões utilizadas nesse trabalho foram a Visual Studio 2005 Express e a Visual Studio
2008 Express, ambas gratuitas e disponíveis para download no próprio site da Microsoft ®.
4.2.1. Linguagem de Programação C#
A linguagem C # é relativamente simples, com apenas cerca de 80 palavras-chave e uma
dúzia de alto - datatypes, mas C# é muito expressivo, quando se trata de aplicar conceitos
modernos de programação. C# inclui todo o apoio para linguagem estruturada, baseada em
componentes, orientada a objetos construída sobre os ombros de C++ e Java.
Tal linguagem foi desenvolvida por uma pequena equipe liderada por dois engenheiros da
Microsoft ®, Anders Hejlsberg e Scott Wiltamuth. Hejlsberg que também é conhecido por
criar Turbo Pascal, uma linguagem de programação para computadores populares, e por
liderar a equipe que desenhou Borland Delphi, o primeiro sucesso de desenvolvimento
integrado para programação de ambientes cliente / servidor. (Liberty, 2005)
As justificativas para o uso desta linguagem no projeto são, entre outras, o fato de C# ser
uma linguagem atual, portanto tem muito a oferecer ainda, além de fornecer fácil conversão
do código dito desktop para web, e apresentar características desejáveis ao projeto,
visualmente (parte gráfica otimizada) e operacionalmente (desenvolvimento rápido do
código).
24
5. DETALHAMENTO DO ALGORITMO
5.1. Grafo pré-disposto no algoritmo
A figura 10 ilustra o grafo que será usado no funcionamento do sistema.
Figura 10: Grafo padrão do sistema.
Foram criados diagramas, para auxiliar no entendimento do funcionamento do
sistema, que serão abaixo apresentados.
5.1.1. Diagrama de Classes
25
Figura 11: Diagrama de Classes do Sistema
Foi elaborada uma classe Carte, que se inter-relaciona com outras classes, que lhe
servem de base, para que por sua vez possa servir de base a classe AlgoDijkstra, que
possui o algoritmo principal do sistema.
5.1.2. Fluxograma UML
Para auxiliar o desenvolvimento do sistema, e ao mesmo tempo o entendimento do
mesmo por terceiros, foi elaborado também um fluxograma UML (Unified Modeling
Language), que é uma linguagem para especificação, documentação, visualização e
desenvolvimento de sistemas orientados a objetos
26
Figura 12: Fluxograma UML do Sistema
27
6. DESENVOLVIMENTO DA APLICAÇÃO
O algoritmo que foi utilizado é o de Dijkstra, o programa foi desenvolvido sobre a plataforma
.NET, da Microsoft ® , e o código desenvolvido em linguagem C#.
O sistema possui uma tela inicial, na qual será solicitado ao usuário que forneça sua cidade
de partida, e sua cidade de destino. Com esses dados, o programa retornará o caminho
mais curto entre as cidades escolhidas. Esses resultados serão gerados em documentos
XML.
Finalizando sua busca, o usuário terá a opção de salvar o documento, para posterior
impressão.
6.1. Implementação do Código: Algoritmo Dijkstra em C#
A seguir será apresentado o trecho principal do código do sistema, comentado função
á função, para melhor entendimento.
namespace Dijkstra
{
# Classe do algoritmo Dijkstra
class AlgoDijkstra
{
# Lista das cidades a serem criadas
#que será chamada de List<Cupula>
public List<Cupula> as_estacoes;
public AlgoDijkstra(List<Cupula> estacoes)
{
as_estacoes = estacoes;
}
#Custo mínimo entre as estações
public Cupula abre_min(List<Cupula> lista)
{
Figura 13: Código principal do Sistema
28
#Cria uma nova cidade com valor inicial de rota
Cupula res = new Cupula(0, 0, "nulo");
res.set_cout(double.MaxValue);
# percorre a lista
foreach (Cupula s in lista)
{
if (s.cout() <= res.cout())
res = s;
}
lista.Remove(res);
return res;
}
# ALGORITMO DE DIJKSTRA IMPLEMENTADO EM C#
# Encontra o menor caminho partindo do ponto inicial até
# chegar ao ponto final, definido pelo usuário
public List<Cupula> encontrar_caminho(Cupula partida, Cupula destino)
{
List<Cupula> caminho = new List<Cupula>();
List<Cupula> Cupulas_a_abrir = new List<Cupula>();
Cupula Cupula_abrir;
# Adiciona custo para caminho entre duas cidades
foreach (Cupula sta in as_estacoes)
{
sta.set_cout(double.MaxValue);
sta.set_pred(null);
Cupulas_a_abrir.Add(sta);
}
29
partida.set_cout(0);
Cupula_abrir = abre_min(Cupulas_a_abrir);
# Enquanto cidade onde está passando no momento for diferente da #cidade #diferente de
destino, continua correndo o grafo.
while (Cupula_abrir != destino )
{
# Percorre o array Cupulas a começar pelo menor valor
foreach (Cupula s in Cupulas_a_abrir)
{
double val = Cupula_abrir.cout() + Cupula_abrir.cout_arco(s);
if (s.cout() > val)
{
s.set_cout(val);
s.set_pred(Cupula_abrir);
}
}
Cupula_abrir = abre_min(Cupulas_a_abrir);
}
Cupulas_a_abrir.Clear();
# Verifica se há ou não uma ligação entre as cidades, e
#caso não haja exibe mensagem de erro
if (destino.cout() == double.MaxValue)
{
MessageBox.Show("Não existe rotas entre " + partida.nome + "
destino.nome);
}
else
30
e " +
# Caso haja um caminho é feita a ligação entre os pontos
{
while (Cupula_abrir != partida)
{
caminho.Add(Cupula_abrir);
Cupula_abrir = Cupula_abrir.get_pred();
}
}
# Adiciona ponto inicial
caminho.Add(partida);
caminho.Reverse();
return caminho;
}
#fim
}
}
6.2. Interface da Aplicação
A interface desenvolvida tem o intuito de facilitar a visualização das cidades, rotas e valores
criados para que o algoritmo faça seu trabalho que é de escolher a menor rota.
Com interface simples, composta por um gerenciador de arquivos(abrir e salvar arquivos
XML), comandos de criação de cidades e criação de rotas com seus respectivos valores.
31
Figura 17: Interface Gráfica do Sistema
•
A interface gráfica do programa possibilita a abertura e salvamento de arquivos XML,
que contenham os grafos criados pelo mesmo.
Figura 18: Menu “ARQUIVO” e as opções contidas
•
Inserir cidades, definindo o nome da mesma e suas coordenadas para visualização
na tela, como num plano cartesiano.
Figura 19: Menu “INSERIR CIDADES”
32
•
Após a criação das cidades, é definido o valor do caminho entre duas cidades,
digitando o valor total de custo entre as mesmas;
Figura 20: Menu “CUSTO DE ROTA”
As duas setas azuis possibilitam desfazer e refazer o ultima ação de atribuição de valor de
rota.
•
No campo “PARTIDA” deve-se selecionar a cidade de origem, e no campo
“DESTINO” a cidade-objetivo.
Figura 21: Campos para seleção das cidades de partida e destino
•
Depois de selecionados “PARTIDA” e “DESTINO”, pressiona-se o botão verde, que
aciona a funcionalidade principal do sistema, que é a de descobrir o caminho mais
curto entre as cidades escolhidas.
33
7. CONCLUSÃO
A necessidade de saber qual caminho lhe traz mais lucro em uma viagem cada vez
mais é perseguida por transportadoras ou mesmo simples consumidores, a fim de
economizar tempo e dinheiro através de uma tomada de decisão em que a mesma lhe traga
tal economia.
Sendo assim, muitas indústrias de softwares tomam a iniciativa diante da demanda,
de construir diversas ferramentas que provêem menor caminho diante de uma determinada
rota.
Com a linguagem de programação C# aliada ao algoritmo de Dijkstra, foi possível a
construção de um software que, após a alimentação de dados via interface gráfica, fornece
os caminhos possíveis com o traçado do menor caminho e, portanto menor custo.
O software neste trabalho desenvolvido foi testado diante de um cenário no qual há
dez cidades na região metropolitana de Campinas, que possui várias diversificações, como
cidades próximas sem pedágio, cidades próximas com pedágio e distantes com e sem
pedágio.
Tendo feito o cálculo de quanto seria gasto em uma pequena viagem entre as
cidades vizinhas como, por exemplo, Campinas-Jaguariúna, Pedreira-Jaguariúna, AmparoPedreira, Serra Negra-Amparo, Sto. Antonio da Posse-Amparo, Holambra-Sto. Antonio da
Posse, Arthur Nogueira-Holambra, Mogi Mirim-Holambra e Mogi Guaçu-Mogi Mirim, já pode
ser feita a estimativa de gasto de cidade pra cidade, para que o software analise através
desses valores de gasto de combustível e pedágio, qual o menor e mais barato caminho a
ser percorrido pelo motorista.
Após o desenvolvimento do sistema pode-se afirmar que o algoritmo de Dijkstra e a
linguagem C# formaram uma boa parceria, pois foi obtido um software simples, porém
funcional.
Futuras implementações serão ainda definidas, como por exemplo um banco de
dados, onde serão armazenados variados destinos, rotas, valores, para que o software
atinja uma abrangência de uso muito maior, podendo ter inserção de dados por exemplo,
interestaduais.
34
• 8. REFERÊNCIAS BIBLIOGRÁFICAS
•
CANTÙ, Marco Dominando o Delphi 7: a Bíblia. São Paulo: Makron Books,
2003
•
DER. Departamento de Estradas de Rodagem. Disponível via URL em:
http://200.144.29.101/website/webrota/viewer.htm. Acesso em 04 de ago de
2007
•
LIBERTY, Jesse Programing C#: Building .Net Applications with C#. 4. ed.
[S.I]: O’reilly, 2005
•
Lima, Edwin C# e .Net para desenvolvedores / Edwin Lima, Eugênio Reis –
Rio de Janeiro : Campus, 2002 ISBN 85-352-0954-9
•
LUX, Beatriz e FURTADO, João Carlos Sistema de Otimização de Rotas
com Suporte de Software Gerenciador de Informações Geográficas.
Disponível
via
URL
em:
http://www.abepro.org.br/biblioteca/ENEGEP2001_TR11_0928.pdf.
Acesso
em 23 Maio de 2008
•
PRESSMAN, ROGER S. Engenharia de Software. São Paulo: Makron
Books, 1995
•
SANTOS, Michael S. ASP.NET. Palmas: [s.n.], 2003
•
TENENBAUM, Aaron M. Estrutura de dados usando C. São Paulo: Makron
Books, 1995
•
UFSCAR, Universidade Federal de São Carlos Algoritmo de Custo Mínimo
Dijkstra. Disponível via URL em: http://www.inf.ufsc.br/grafos/temas/custominimo/dijkstra.html. Acesso em 26 Maio de 2008
•
VAMBERTO, Carlos Curso de C#. Disponível via URL em:
http://www.msdnbrasil.com.br/secure/sharepedia/arquivos/Modulo_1_Introduc
ao_ao_DOTNET_com_C_.pdf. Acesso em: 05 de dez. de 2006
•
WIKIPÉDIA. Desenvolvido pela Wikimedia Foundation. Apresenta conteúdo
enciclopédico.
Disponível
via
URL
em:
http://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Dijkstra&oldid=637018
1. Acesso em: 05 Ago de 2007
35

Visualizar - Polis Educacional

Transcrição

Documentos relacionados

Caminho mais curto a partir de um nó Algoritmos de Dijkstra e

incubadora de transporte para recem nascido e prematuro

Conexidade e Distância

Exercicios 3 - Departamento de Matemática - PUC-Rio

Método Bonecas Russas para Conjunto Independente

Introduç˜ao `a Teoria dos grafos

Análise de Redes Sociais

EasyCyclomaticComplexity Tool: Uma ferramenta de apoio ao

faculdade norte capixaba de sâo mateus análise e desenvolvimento

PREFEITURA MUNICIPAL DE VESPASIANO

Teoria dos Grafos Aula 9

universidade federal do ceará departamento de computação curso