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

0
FACULDADE NORTE CAPIXABA DE SÂO MATEUS
ANÁLISE E DESENVOLVIMENTO DE SISTEMAS
ELTON DOUGLAS SILVA
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM
GRAFOS.
SÃO MATEUS
2012
1
ELTON DOUGLAS SILVA
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM
GRAFOS.
Trabalho de Conclusão de Curso apresentado ao
programa de Graduação no Curso Superior
Tecnológico em Analise e Desenvolvimento de
Sistemas da Faculdade Norte Capixaba de São
Mateus, como requisito para obtenção do grau de
Tecnólogo em Analise e Desenvolvimento de
Sistemas.
Orientador: Lucas Costa Jardim.
SÃO MATEUS
2012
2
Catalogação na fonte elaborada pela “Biblioteca Dom Aldo Gerna”/UNISAM
S586o
Silva, Elton Douglas
A otimização de problemas de caminho mais curto entre dois pontos em uma rota,
utilizando algoritmos baseados em grafos/– São Mateus: UNISAM /Faculdade Norte
Capixaba de São Mateus, 2012.
58.f : enc.
Orientador: Lucas Costa Jardim
Trabalho de conclusão de curso (Tecnólogo em Análise e Desenvolvimento de
Sistemas)
UNISAM / Faculdade Norte Capixaba de São Mateus, 2012.
1.Análise 2. Protótipo 3. Dijkstra I. Silva, Elton Douglas II.UNISAM /
Faculdade Norte Capixaba de São Mateus, 2012. III. Título.
CDD 005.1
3
ELTON DOUGLAS SILVA
A OTIMIZAÇÃO DE PROBLEMAS DE CAMINHO MAIS CURTO ENTRE DOIS
PONTOS EM UMA ROTA, UTILIZANDO ALGORITMOS BASEADOS EM
GRAFOS.
Trabalho de Conclusão de Curso apresentado ao programa de Graduação no Curso Superior
Tecnológico em Analise e Desenvolvimento de Sistemas da Faculdade Norte Capixaba de São
Mateus, como requisito para obtenção do grau de Tecnólogo em Analise e Desenvolvimento de
Sistemas.
Aprovada em 24 de novembro de 2012
COMISSÃO EXAMINADORA
_____________________________________________________
Profº Lucas Costa Jardim
Faculdade Norte Capixaba de São Mateus
Orientador
_____________________________________________________
Profº Ramilton Costa Júnior
Faculdade Norte Capixaba de São Mateus
Membro 1
_____________________________________________________
Profº Temístocles A. Rocha
Faculdade Norte Capixaba de São Mateus
Membro 2
4
Dedico este trabalho a Deus, meu
Senhor, por ter me dado forças para
completar este desafio, esta etapa da
minha vida acadêmica, por me amparar
nos momentos de angustia e fraqueza,
pois sei que sem Ele eu não teria
conseguido. Que toda honra e glória seja
dada a Ti Senhor.
Dedico aos meus familiares por sempre
me apoiarem e estarem presentes
incentivando.
5
Meus sinceros agradecimentos ao
Professor (orientador) Lucas Costa
Jardim, por ter aceitado este desafio
comigo, por ter me ajudado nesta batalha
e por ter contribuindo para a conclusão
deste projeto. Professor Lucas, muito
obrigado.
Meus sinceros agradecimentos a Ivani
Francisca dos Santos, por sua imensa
ajuda, tanto intelectual quanto pessoal.
Por sempre está disposta a ajudar sem
cobrar nada em troca, pelos sinceros
gestos de tolerância, compreensão e
carinho. Ivani, muito obrigado.
Meus sinceros agradecimentos a todos os
professores que fizeram parte da minha
jornada acadêmica na instituição, sem
vocês esta jornada não poderia ter sido
completada. Professores, muito obrigado.
6
“A arte de programar consiste em
organizar e dominar a complexidade”.
(Edsger Dijkstra)
7
RESUMO
O presente trabalho tem como objetivo apresentar alguns aspectos sobre a Teoria
Geral dos Grafos, pseudocódigos que trabalham com grafos buscando a otimização
(melhor resposta) para encontrar o menor caminho entre dois pontos em uma rota.
Para o levantamento das informações contidas nesta pesquisa, utilizou-se o
emprego de uma pesquisa exploratória, respaldando-se em pesquisas bibliográficas
e virtuais. Para uma melhor visualização, foi desenvolvido um Protótipo, no qual foi
aplicado o algoritmo selecionado como o mais indicado para solucionar o problema
proposto nesta pesquisa. A escolha do algoritmo se deu através de comparações
dos seus valores de complexidade, análise assintótica.
PALAVRAS-CHAVE: Análise. Protótipo. Dijkstra.
8
ABSTRACT
This work aims to present some aspects about the General Theory of Graphs,
pseudocódigos working with graphs seeking optimization (best response) to find the
shortest path between two points on a route. To survey the information contained in
this research, we used the employment of an exploratory research, supporting
research into bibliographic and virtual. For best viewing, we developed a prototype, in
which we applied the algorithm selected as the most suitable for solving the problem
proposed in this research. The choice of algorithm is made by comparing the values
of complexity, asymptotic analysis.
KEYWORDS: Analysis. Prototype. Dijkstra.
9
LISTA DE FIGURAS
FIGURA 1.0 – PROBLEMA DADO A EULER EM 1736............................................21
FIGURA 2.0 - GRAFO MONTADO DO PROBLEMA DADO A EULER EM 1736....22
FIGURA 3.0 – GRAFO..............................................................................................22
FIGURA 4.0 – GRAFO DIRECIONADO....................................................................24
FIGURA 5.0 – GRAFO NÃO DIRECEIONADO.................................................... ......24
FIGURA 6.0 – GRAFO PONDERADO......................................................................25
FIGURA 7.0 – GRAFO SIMPLES.............................................................................25
FIGURA 8.0 – GRAFO COMPLETO........................................................................25
FIGURA 9.0 – ALGORTIMOS EM DIAGRAMA DE BLOCOS ................................26
FIGURA 10.0 - ALGORITMO TEXTUAL..................................................................26
FIGURA 11.0 – PSEUDOCÓDIGO DO ALGORITMO DE WARSHALL...................27
FIGURA
12.0
–
PSEUDOCÓDIGO
DO
ALGORITMO
DE
DIJKSTRA
–
RELAXAMENTO DAS ARESTAS.............................................................................30
FIGURA 13.0 – GRAFO ORIENTADO.....................................................................31
FIGURA 14.0 – PSEUDOCÓDIGO ALGORITMO DE BELLMAN-FORD.................32
FIGURA 15.0 – ANÁLISE ASSINTÓTICA – ............................................................38
FIGURA 16.0 – DIAGRAMA DE CASO DE USO – PROTÓTIPO............................44
FIGURA 17.0 – DIAGRAMA DE ATIVIDADES – EXECUTAR DIJKSTRA...............46
FIGURA 18.0 – DIAGRAMA DE SEQUÊNCIA.........................................................47
FIGURA 19.0 – DIAGRAMA DE CLASSE................................................................48
FIGURA 20.0 – GRAFO PRÉ-DISPOSTO DO PROTÓTIPO..................................49
FIGURA 21.0 – PROTÓTIPO – TELA PRINCIPAL..................................................50
FIGURA 21.1 – PROTÓTIPO – TELA PRINCIPAL – PARTE INFERIOR ..............50
FIGURA
21.2
–
PROTÓTIPO
–
SIMULAÇÃO
ENTRADA
DE
DADOS
MANUALMENTE......................................................................................................51
10
LISTA DE TABELAS
TABELA 1.0 – SEQUÊNCIA DE DIAGRAMAS – ALGORITMO DE DIJKSTRA........28
TABELA 2.0 – TABELA COM OS DADOS DO GRAFO DA FIGURA 13.0 ..............31
TABELA 3.0 –EXEMPLO PL.....................................................................................39
TABELA 4.0 – COMPLEXIDADE DOS ALGORITMOS.............................................41
11
SUMÁRIO
1 INTRODUÇÃO .................................................................................................. 13
1.1 JUSTIFICATIVA DO TEMA.................................................................................. 13
1.2 DELIMITAÇÃO DO TEMA ................................................................................... 14
1.4 OBJETIVOS ........................................................................................................ 15
1.4.1 OBJETIVO GERAL ................................................................................................ 15
1.4.2 OBJETIVOS ESPECÍFICOS ..................................................................................... 15
1.5 HIPÓTESE .......................................................................................................... 15
1.6 META................................................................................................................... 15
1.7 METODOLOGIA .................................................................................................. 16
1.7.1 CLASSIFICAÇÃO DA PESQUISA ............................................................................. 16
1.7.2 TÉCNICAS PARA COLETA DE DADOS ...................................................................... 17
1.7.3 FONTES PARA COLETA DE DADOS ......................................................................... 17
1.7.4 CARACTERIZAÇÃO DA AMOSTRA PESQUISADA ....................................................... 18
1.7.5 INSTRUMENTO PARA A COLETA DE DADOS ............................................................. 18
1.7.6 POSSIBILIDADE DE TRATAMENTO E ANÁLISE DOS DADOS. ....................................... 18
1.8 APRESENTAÇÃO DOS CONTEÚDOS DAS PARTES DO TRABALHO............ 19
2.0 REFERENCIAL TEÓRICO ......................................................................... 20
2.1 MODELAGEM DE PROBLEMAS .................................................................... 2020
2.2 TEORIA GERAL DOS GRAFOS .......................................................................... 21
2.2.1 TIPOS DE GRAFOS ............................................................................................... 23
2.3 ALGORITMOS..................................................................................................... 26
2.3.1 ALGORITMOS DE MENOR CAMINHO OU CAMINHO MÍNIMO ......................................... 27
2.3.3 ALGORITMO DE BELLMAN-FORD ........................................................................... 31
2.4 ANÁLISE DE ALGORITMOS ............................................................................... 34
2.4.1 COMPLEXIDADE DOS ALGORITMOS - ANÁLISE ASSINTÓTICA .................................... 35
2.4.2 PROGRAMAÇÃO LINEAR.......................................................................................39
2.4.3 ALGORITMO ESCOLHIDO ...................................................................................... 41
2.5 FERRAMENTAS (IDE’S) E LINGUAGEM UTILIZADAS NO DESENVOLVIMENTO
DO SOFTWARE ........................................................................................................ 42
12
2.5.1 C# ..................................................................................................................... 42
2.5.2 UML - UNIFIED MODELING LANGUAGE OU LINGUAGEM DE MODELAGEM DE DADOS .... 42
3.0 IMPLEMENTAÇÃO DIJKSTRA – PROTÓTIPO ................................... 44
3.1 DIAGRAMA DE CASO DE USO .......................................................................... 44
3.1.2 DIAGRAMA DE ATIVIDADES ................................................................................... 45
3.1.3 DIAGRAMA DE SEQUÊNCIA ................................................................................. 466
3.1.4 DIAGRAMA DE CLASSES..................................................................................... 477
3.2 GRAFO DE ESTUDOS – PROTÓTIPO ............................................................. 488
3.3 PROTÓTIPO ..................................................................................................... 499
3.3.1 IMPLEMENTAÇÃO DO ALGORITMO DE DIJKSTRA EM C SHARP ............................... 522
4.0 CONCLUSÃO E RECOMENDAÇÕES .................................................. 555
4.1 CONCLUSÃO .................................................................................................... 555
4.2 RECOMENDAÇÕES ......................................................................................... 555
5.0 REFERÊNCIAS BIBLIOGRÁFICAS ...................................................... 577
13
1 INTRODUÇÃO
Gastos e tentativa de otimização, são fatores comuns no cotidiano de pessoas
físicas e jurídicas. Quem nunca se perdeu ou gastou mais combustível errando o
caminho para a casa de um “primo” que morava em outra cidade? Qual empresa
que nunca mudou uma rota dos seus veículos tentando achar o caminho mais curto
ou mais econômico para atingir ou concluir determinada meta? Bem, hoje com as
novas tecnologias (como o GPS) estes tipos de problemas se tornaram mais fáceis
de contornar.
Este trabalho abordará algoritmos que trabalham na otimização desses problemas
(menor caminho, melhor rota), os quais (os problemas) podem ser montados
graficamente utilizando grafos.
Padrões algorítmicos que foram criados para fins parecidos também foram
abordados, assim como a teoria dos grafos (onde foram apresentados apenas os
conceitos básicos, acreditando-se dar um bom suporte para o acompanhamento da
pesquisa).
Na etapa final foi desenvolvido um software (protótipo) no qual está implementado o
algoritmo que se foi identificado como o mais indicado para otimização deste tipo de
problema (menor caminho entre dois pontos de uma rota), onde o mesmo pode ser
alimentado diretamente pelo usuário.
1.1 JUSTIFICATIVA DO TEMA
Solução e otimização de problemas, são resultados constantemente buscados pela
humanidade. Trabalhos, pesquisas e abundantes denotações científicas foram e são
criadas para tais feitos. Uma das formas encontradas e utilizadas para obtenção da
otimização e solução de famosos problemas dados à sociedade (pontes de
Königsberg em 1736, o problema das 4-Cores de Francis Guthris/De Morgan em
1852), foi o uso da Teoria dos Grafos.
14
A Teoria dos Grafos é vista como uma das mais importantes áreas da matemática
discreta, a mesma é utilizada na construção de modelos para a visualização dos
problemas de um ângulo proporcionalmente melhor.
Com o avanço tecnológico depois da criação do primeiro computador eletrônico
(Eniac – 1946), o desenvolvimento e estudo dos algoritmos foram impulsionados.
Segundo Oliveira e Nunes (2011), nos anos 70 e 80 ocorrendo o desenvolvimento
da base matemática da Teoria dos Grafos, a mesma passou a ser utilizada com a
informática, na época na área de Análise de Redes Sociais.
Como fora demonstrado, a Teoria dos Grafos, ajudou e poderá ajudar a modelar
problemas de diversos setores de “N” áreas, que poderão abranger desde
problemas pequenos como serviços de entrega de pizzas ou problemas maiores
como atendimento bancário de aposentados, menor caminho entre dois pontos de
uma rota, dentre outros. Uma vez modelado o problema em questão, se pode utilizar
de algoritmos para ajudar na otimização do mesmo.
1.2 DELIMITAÇÃO DO TEMA
O presente trabalho, através de pesquisas (bibliográficas e virtuais), visa obter
informações e abordar métodos (algoritmos) que foram desenvolvidos com o
objetivo de trazer respostas mais computacionais (rápidas e mais precisas) para
otimização de problemas de caminho mais curto entre dois pontos de uma rota.
1.3 FORMULAÇÃO DO PROBLEMA
Baseando-se na diminuição de gastos e tempo, ao se otimizar qualquer processo de
um determinado trabalho, estamos gerando lucro e ou diminuição de custos.
Qual o algoritmo que melhor se enquadra para se obter de forma otimizada, o menor
caminho entre dois pontos de uma rota?
15
1.4 OBJETIVOS
1.4.1 OBJETIVO GERAL
Apresentar a utilização de algoritmos baseados em grafos na otimização de
problemas de menor caminho em uma rota, através um software (protótipo) que foi
desenvolvido, podendo o mesmo ser alimentado diretamente pelo usuário.
1.4.2 OBJETIVOS ESPECÍFICOS
 Pesquisar sobre algoritmos que tratam de problemas de menor
caminho.
 Levantar informações sobre a Teoria dos Grafos.
 Identificar qual o melhor algoritmo para se trabalhar com problemas de
menor caminho, onde o mesmo só utilize pesos de valores positivos.
 Desenvolver um software (protótipo) onde será aplicado um algoritmo
que melhor se enquadre no problema posposto nesta pesquisa e que
tenha a menor taxa de complexidade (valor assintótico), o qual irá
identificar o menor caminho entre dois pontos em uma rota.
1.5 HIPÓTESE
Acredita-se que ao final desta pesquisa, será possível enxergar a praticidade e
agilidade que se ganha ao implementarmos algoritmos baseados em grafos em
softwares que indicam o menor caminho entre dois pontos de uma rota.
1.6 META
Expor como a aplicabilidade de algoritmos baseados em grafos pode ajudar na
otimização de problemas de menor caminho em uma rota.
16
1.7 METODOLOGIA
Para Viegas (apud Reis, 2008, p. 44), “a metodologia é o conjunto de técnicas e
processos utilizado pela ciência para formular e resolver problemas de aquisição
objetiva do conhecimento de maneira sistemática.”.
Na metodologia, utiliza-se de técnicas propostas para obtenção de êxito do
problema proposto na pesquisa elaborada. Trabalhando com a mineração dos dados
pesquisados e fornecidos, mostrando as formas com que os mesmos foram
modelados.
1.7.1 CLASSIFICAÇÃO DA PESQUISA
Para Gil (2007), é possível classificar as pesquisas em três grandes grupos:
exploratórios, descritivas e explicativas. Onde as pesquisas exploratórias envolvem
levantamento bibliográfico, entrevistas com pessoas que tiveram experiências
práticas com o problema pesquisado e ou análise de exemplos. Já as pesquisas
descritivas têm o objetivo primordial à descrição das características dos fatores
estudados e estabelecendo as relações entre variáveis. Nas pesquisas explicativas
a preocupação central seria identificar os fatores que determinam ou que contribuem
para a ocorrência dos fenômenos, portanto, é neste tipo de pesquisa onde há um
maior aprofundamento da realidade, pois a mesma explica o porquê das coisas.
Reis (2008, p.51), dentro das pesquisas exploratórias, descreve bem o conceito da
pesquisa bibliográfica:
A pesquisa bibliográfica é a mais simples técnica de pesquisa. Ela explica
um problema, fundamentando-se apenas nas contribuições secundárias, ou
seja, nas informações e dados extraídos de livros de leitura corrente e de
referencias, de revistas impressas e virtuais, material audiovisual,
entrevistas, documentos, etc. de diferentes autores que versam sobre o
tema selecionado para o estudo.
Foi utilizada para a conclusão do projeto a pesquisa exploratória, respaldando-se
nos levantamentos de dados e análise de exemplos que serão obtidos através de
17
pesquisas bibliográficas e virtuais, visto que, não foram abordados problemas de
empresas ou setores reais, mas sim, exemplos para a compreensão do trabalho
proposto.
1.7.2 TÉCNICAS PARA COLETA DE DADOS
Richardson (1999, p. 219) “as técnicas de pesquisa não podem ser utilizadas como
receitas de instrumentos neutros, mas como meios de obtenção de informação cujas
qualidades e limitações devem ser controladas”.
Qualquer técnica utilizada para coleta de dados em um referido problema, pesquisa
e ou trabalho, não pode se utilizar de meios estagnados, parados, é preciso
observar o que se procura encontrar e quais os meios que estão sendo utilizados
para determinado fim.
Foram utilizadas no referente trabalho, técnicas de coleta e levantamento de dados
em fontes bibliográficas e virtuais (sites, fóruns, artigos).
1.7.3 FONTES PARA COLETA DE DADOS
As fontes para coletas de dados podem ser dividir em dois tipos: os de fontes
primárias e fontes secundárias.
Segundo Andrade (2001), fontes primárias são formadas por obras ou textos
originais, conteúdos ainda não trabalhados, sobre determinado assunto. As fontes
primárias, pela sua relevância, dão origem a outras obras, que vão formar uma
literatura ampla sobre aquele determinado assunto.
Para Cervo e Bervian (apud MERTENS; FUMANGA; TOFFANO; SIQUEIRA, 2007,
p. 60) “as fontes secundárias são provenientes de material bibliográfico colhido em
livros, revistas periódicas, jornais, anais de congressos e demais fontes impressas
ou eletrônicas”.
18
Seguindo estas linhas de raciocínio, foram utilizadas fontes secundárias, pois o
mesmo trabalhou com pesquisas bibliográficas e virtuais, atribuindo a base do seu
conteúdo nas informações adquiridas com as pesquisas.
1.7.4 CARACTERIZAÇÃO DA AMOSTRA PESQUISADA
O trabalho foi realizado através de pesquisas bibliográficas (livros, fontes impressas,
etc.) e virtuais (sites, artigos, fóruns), esperando adquirir informações necessárias
para a conclusão do mesmo com êxito.
1.7.5 INSTRUMENTO PARA A COLETA DE DADOS
Utilizaram-se pesquisas bibliográficas e virtuais, assim como leituras de materiais
impressos que se correlacionavam com o tema e problema sugeridos nesta
pesquisa.
Não se fez necessário a utilização de questionário ou outros instrumentos
semelhantes para coleta de dados referentes à pesquisa proposta.
1.7.6 POSSIBILIDADE DE TRATAMENTO E ANÁLISE DOS DADOS
Para Vergara (2003, p. 59), ”Tratamento dos dados refere-se àquela seção na qual
se explicita para o leitor como se pretende tratar os dados a coletar [...].”.
Partindo dessa premissa e visando elaborar uma pesquisa integra e sem erros, todo
o conteúdo pesquisado foi analisado, buscando evitar dados não precisos e
redundância de informações.
19
1.8 APRESENTAÇÃO DOS CONTEÚDOS DAS PARTES DO TRABALHO
Para a demonstração do objeto de estudo desta pesquisa, a mesma foi dividida em
05 capítulos:
Onde no primeiro capítulo é feita a Introdução, Justificativa do Tema, Delimitação do
tema, Formulação do problema, Objetivos (geral e específicos) e a Hipótese.
No segundo capítulo é exposto o Referencial Teórico, o qual fundamentaliza esta
pesquisa.
O terceiro capítulo apresenta o Protótipo, o qual se torna a parte prática deste
projeto, onde foi inserido o algoritmo (dentre os abordados por esta pesquisa) que
melhor se enquadrou para a resolução do problema proposto.
As Conclusões referentes a esta pesquisa e Recomendações para continuação do
protótipo (possíveis melhorias), setores onde o mesmo poderia ser empregado, etc.,
encontram-se no capítulo 4.
No capítulo 5 estão todas as referências bibliográficas utilizadas para a conclusão
deste projeto.
20
2.0 REFERENCIAL TEÓRICO
2.1 MODELAGEM DE PROBLEMAS
Ao tentarmos obter uma visualização mais ampla e com representações mais
simplificadas de um determinado problema, a modelagem pode ser uma excelente
ferramenta a se utilizar.
Para Goldbarg e Luna (2005, p. 2) “Os modelos são representações simplificadas da
realidade que preservam, para determinadas situações e enfoques, uma
equivalência adequada.”.
Expondo-se um problema que antes se encontrara em forma contextual, para um
modelo visual (gráfico), fará com que se obtenha uma melhor amplitude do mesmo,
consequentemente, se atribuirá uma otimista capacidade para a simplificação do
mesmo.
É importante lembrar que, todo modelo deve passar por um processo de validação,
onde ocorrem verificações da sua representatividade, é verificado se o modelo
realmente está de acordo com a atividade para o qual foi elaborado.
O conceito que é aferido aos modelos, de que eles demonstram uma representação
substituta da realidade, implicam em um alcance limitado.
Goldbarg e Luna (2005) relata que para alcançarmos modelos eficientes, são
necessárias pelo menos três habilidades: Foco holístico, que seria indispensável
quando estamos procurando solucionar um problema e nossa solução pode criar
outros problemas que podem posteriormente anular nossos esforços; Tratamento
eclético da dimensão da análise, onde todos os métodos utilizados terão de ser os
mais livremente dispostos, e por último a Tradução adequada, onde se indica que,
para se ter um bom modelo, se exigirá ter uma boa tradução de todos os dados e
contexto do problema.
21
2.2 TEORIA GERAL DOS GRAFOS
A Teoria dos Grafos é vista como uma das mais importantes áreas da matemática
discreta e também na área da Ciência da Computação.
Alguns autores como Bonchev e Rouvray (1991), relatam que o primeiro registro
conhecido da teoria dos grafos foi feito pelo matemático suíço Leonhard Euler, que
viveu entre 1707 e 1783, o qual utilizou a mesma pela primeira vez em 1736 para
resolver um problema que lhe foi entregue pelos cidadãos da cidade prussiana de
Königsberg, a qual era cortada pelo rio Pregel, que abrange uma porção de terra
(ilha). O problema que lhe foi proposto era determinar se era passível começar um
passeio por qualquer ponto das margens do rio (Pregel), ou da ilha, e percorrer por
todas as pontes (eram 07 no total), cada uma somente uma única vez, e voltar ao
ponto de partida.
Figura 1.0 – Problema dado a Euler em 1736
Fonte: DEWDNEY. 20.000 léguas matemáticas, (2000).
Montando o problema em um grafo, em 1736, Euler mostrou que este passeio é
impossível, que o mesmo só seria possível, se em cada ponto (ilha) houvesse duas
pontes, uma para entrada e outra para saída, formando assim em cada ponto um
número par de pontes.
A figura 2.0 ilustra um possível esboço feito por Euler, montado o problema proposto
a ele em forma de grafo.
22
Figura 2.0 – Grafo montado do problema dado a Euler em 1736
Fonte: DEWDNEY, 20.000 léguas matemáticas, (2000).
Goodrich e Tamassia (2007) relatam de forma simples, porém direta, o conceito de
grafos, onde dizem que um grafo é uma forma gráfica de representar
relacionamentos que existem entre pares de objetos.
Um grafo de forma simples, nada mais é que a representação visual (gráfica) de
elementos que se interligam e que de certa forma tem uma interdependência entre
si. O mesmo pode ser amplamente utilizado para representação visual de
problemas, onde trará uma melhor visualização do mesmo.
Os elementos do grafo são denominados de vértices (nós), que é um conjunto não
vazio de objetos e estão interligados através de traços, denominados arestas, que
são um conjunto de pares não ordenados.
Para um melhor entendimento, podemos imaginar uma árvore (no conceito de
árvores binárias em algoritmo), vários elementos (vértices) que estão ligados entre si
graficamente através de traços (arestas).
A figura 3.0 ilustra um exemplo simples de grafo.
Figura 3.0 – Grafo
Fonte: Fonte: Adaptado pelo autor
23
No seu conceito matemático, um grafo é G(V, A), onde V são os vértices e A as
arestas, o conjunto V = {1, 2,..., v} será composto dos “n” nós do grafo, e A = {1, 2,...,
a} conterá as “n” arestas. Sendo que, dependendo da situação, as arestas podem
ser direcionadas ou não, e também podem trazer sobre si pesos (valores numéricos)
associados, tornando-os assim Grafos Ponderados.
Partindo do seu conceito matemático, temos então na figura 3.0, os seguintes dados
representando G(V, A):
V = {2,4,5,6,8};
A = { { 2, 4} { 2, 6} { 4, 2} { 4, 5} { 4, 6} { 5, 4} { 5, 6} { 6, 2} { 6, 4} { 6 ,5} {8, 4}};
Outro ponto importante na teoria dos grafos é entender como os vértices podem
estabelecer vínculos (ligações) através das arestas, definindo-se assim a vizinhança
de vértices.
Caso não haja valores associados às arestas, dizemos que o grafo é Rotulado. Não
se encontrando também orientação nas arestas, ou seja, direcionamento da direção
da mesma, e sendo um vértice ‘A’ “amigo” do vértice ‘B’ e vice-versa, os mesmos
possuem uma relação simétrica.
Goldbarg e Luna (2005, p. 489) dizem que “[...] dois vértices xi e xj são vizinhos ou
adjacentes quando existe uma aresta que liga xi a xj ou vice-versa.”.
É válido ressaltar que a noção de vizinhança se dá apenas a grafos não orientados.
2.2.1 TIPOS DE GRAFOS
Dentre os diversos tipos de grafos, existem os direcionados e não direcionados.
Para Goldbarg e Luna (2005, p. 485), “um grafo é dito direcionado quando o sentido
das ligações entre os vértices é importante. Nesse caso normalmente as arestas são
chamadas por arcos.”.
Para obtenção de uma boa noção do que são grafos direcionados ou dígrafos, basta
pensarmos no grafo de um bairro, onde temos como os vértices (nós) alguns pontos
do bairro e as arestas seriam as ruas, que interligam os pontos do bairro entre si. O
contexto de direcionado está no fator de mão e contramão, imaginemos que para
24
irmos da prefeitura da cidade que está localizada neste bairro, até o fórum, podemos
ir pela rua principal, mas para voltarmos à prefeitura, a mesma rua não é permitida,
pois é via de mão única, assim como uma aresta de um grafo direcionado, ela tem
sentido certo denominado. Vale ressaltar que nos grafos direcionados, as arestas
são substituídas por setas que indicam o vértice de destino e o sentido (direção) da
mesma.
Figura 4.0 – Grafo direcionado
Fonte: Adaptado pelo autor
Já o conceito de grafo não direcionado, ou apenas grafo, é justamente o oposto do
direcionado, pois as arestas não implicam em uma direção precisa de segmento, e
se pode associar a cada aresta um subconjunto de dois ou de um elemento de V
(conjunto de vértices), indicando as localidades finais.
Figura 5.0 – Grafo não direcionado
Fonte: Adaptado pelo autor
25
Outro tipo de grafo é o ponderado, para Ziviane (2005, p. 255), “um grafo ponderado
possui pesos associados às suas arestas”. Neste modelo, os valores que estão
associados influenciam nas decisões de escolha do caminho, pois os custos sobre
cada aresta podem variar. Este tipo de grafo é muito utilizado em problemas de
caminho mínimo, que visa à diminuição (otimização) de custos ao atravessar o grafo
na rota referida pelo problema.
10
A
B
15
22
D
C
35
Figura 6.0 – Grafo ponderado
Fonte: Adaptado pelo autor
Quando se tem um grafo simples e uma ligação associada a cada par de vértices, é
dito que o mesmo é completo. Este conceito é dado, pois ha uma ligação,
comunicação, entre todos os vértices, podendo se ir a qualquer parte do grafo
partindo de qualquer vértice.
As figuras abaixo (figura 7.0 e figura 8.0) distinguem bem um grafo simples de um
grafo completo. Lembrando que a diferença está em que, em um grafo simples não
se apresentam laços nem arestas paralelas, e o grafo completo é um grafo simples,
mas todos os vértices estão interligados.
Figura 7.0 – Grafo simples
Fonte: Adaptado pelo autor
Figura 8.0 – Grafo completo
Fonte: Adaptado pelo autor
26
2.3 ALGORITMOS
Para Said (2007, p. 07), algoritmo é “[...] uma sequência finita de passos, descritos
em uma ordem lógica, que visam a atingir um objetivo bem definido.”.
Resumindo, algoritmo é um passo a passo estruturado, finito, elaborado com o
intuito de se conseguir realizar um objetivo determinado, tarefa, cálculo, receita, etc.
A importância dos algoritmos é indiscutível, pois como o mesmo fora descrito
anteriormente, ele é uma sequência finita de passos, algo lógico para se atingir
determinada meta, o mesmo pode partir das primícias de uma bula de remédios até
áreas computacionais, matemáticas etc.
Um algoritmo pode ser feito (aplicado) geralmente de duas formas: gráfica, onde
para uma melhor visualização serão utilizados diagramas de blocos; e de forma
textual, onde será utilizada linguagem de programação.
Figura 9.0 – Algoritmos em diagrama de blocos
Fonte: BAJPAI; MUSTOE; VALKER
Matemática para engenheiros. (1980).
Figura 10.0 – Algoritmo textual
Fonte: Adaptado pelo autor
27
2.3.1 ALGORITMOS DE MENOR CAMINHO OU CAMINHO MÍNIMO
A definição de caminho é clara, está ligada na rota e na distância entre dois pontos,
um passeio sem vértices repetidos. Sabendo-se disso, é fácil entender que, a
distância de um vértice z, em um grafo G, até o vértice y, do mesmo grafo, é a soma
dos pesos das respectivas arestas existentes entre os dois vértices. Logicamente
admitindo que exista ligação entre os dois vértices.
Então, é correto dizer que K é o menor caminho entre z e y, caso não acha outros
caminhos.
Para verificar a existência de caminho entres dois vértices de um grafo, temos de
observar suas ligações (arestas).
Muito utilizado para determinado fim, é o algoritmo de Floyd-Warshall (ou Warshall).
Ele trabalha com a busca do caminho mais curto (entre os pontos de uma rota) de
um grafo dirigido e com pesos, valores (grafo valorado).
Figura 11.0 – Pseudocódigo do algoritmo de Warshall
Fonte: GOODRICH, TAMASSIA. Estrutura de dados e algoritmos em Java. (2007).
O algoritmo de Dijkstra foi criado por um cientista da computação holandês,
chamado Edsger Wybe Dijkstra (Roterdã, 11 de Maio de 1930 – Nuenen, 6 de
Agosto de 2002), aproximadamente no final da década de 50.
Goodrich e Tamassia (2007) relatam que, ao se tentar descobrir o caminho mais
curto de v a qualquer outro ponto do grafo, o algoritmo de Dijkstra é uma das
28
primeiras opções, pois como ele é considerado um método guloso, a sua aplicação é
tida como uma grande nuvem, que vai se expandindo e inserindo nela os vértices do
grafo, até não sobrar vértice algum de fora da nuvem. Tendo assim ao final do
processo, encontrado o menor caminho de v para qualquer outro vértice (nó) do
grafo.
Basicamente o algoritmo de Dijkstra funciona buscando e comparando os valores
(pesos) das arestas adjacentes ao vértice de origem, inicialmente deixando todos os
outros vértices com o custo “infinito”, ainda não descoberto. Conforme o algoritmo
vai avançando pelo grafo, o mesmo vai “marcando”, selecionando os vértices com
menores pesos, colocando neles “tarjas”, sinais, marcadores que podem ser
temporários ou definitivos, indicando as arestas de menor distancia entre o vértice
de origem até o vértice atual, sendo considerado um método guloso, pois vai
selecionando e escolhendo o menor caminho encontrado até o momento, lógico,
enquanto o algoritmo não chega ao fim. Chegando ao final do grafo, o algoritmo
assim, consegue identificar, o menor caminho entre os dois pontos (vértices) do
grafo. Pois terá obtido e marcado as arestas e vértices com menor custo.
Ressaltando que, o algoritmo de Dijkstra trabalha com grafos dirigidos ou não, e
ponderados com valores apenas positivos.
A tabela abaixo ilustra o funcionamento do algoritmo de Dijkstra através de uma
sequencia de diagramas.
Algoritmo de Dijkstra – Sequencia de Diagramas (Continua até pág. 30).
Inicialmente todos os nodos tem um custo
infinito,
exceto s (a raiz da busca) que tem valor 0:
vértices
s u v x y
∞∞∞∞
estimativas
0
precedentes
- - - -
-
29
selecione s (vértice aberto de estimativa
mínima)
feche s
recalcule as estimativas de u e x
vértices
s u v x y
∞
estimativas
0 10
precedentes
s s -
5
∞
s -
selecione x (vértice aberto de estimativa
mínima)
feche x
recalcule 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
selecione y (vértice aberto de estimativa
mínima)
feche y
recalcule a estimativa de v
vértices
s u v x y
estimativas
0 8 13 5 7
precedentes s x y 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 u s x
30
selecione v (vértice aberto de estimativa
mínima)
feche v
vértices
s u v x y
estimativas
0 8 9 5 7
precedentes s x u s x
Tabela 1.0 – Sequencia de diagramas – Algoritmo de Dijkstra (Parte final da tabela - pág. 28, 29, 30).
Fonte: MARIANI – (Livro eletrônico) Site http://www.inf.ufsc.br/grafos/ (2012)
A figura 12.0 traz o pseudocódigo do algoritmo de Dijkstra, baseando no exemplo
dado do mesmo ser como uma nuvem, utilizando um recurso de “relaxamento de
aresta”, onde o relaxamento é dado por um caminho entre as arestas, ex (k, j),
tornando o relaxamento como uma espécie de mola, pois o mesmo vai se esticando
do ponto único de origem até o final, voltando ao ponto de partida, tendo assim o
resultado do melhor caminho.
Goodrich e Tamassia (2007) dizem que, seu principio básico é dado por:
Se D[u] + w((u, z)) < D[z] então
D[z] <- D[u] + w((u, z));
Onde D[u] é um rótulo, espécie de vetor ou pilha para cada vértice de u em V.
Figura 12.0 – Pseudocódigo do Algoritmo de Dijkstra – Relaxamento das arestas
Fonte: GOODRICH e TAMASSIA (2007).
31
2.3.3 ALGORITMO DE BELLMAN-FORD
O algoritmo de Bellman-Ford, criado por Richard Bellman e Lester Ford Jr, também é
um algoritmo de busca de caminho mínimo, basicamente sua diferença do Dijkstra, é
que, este aceita pesos negativos em suas arestas, enquanto o Dijkstra só aceita
valores positivos.
Levando-se em consideração o tempo gasto no processamento, o Dijkstra leva
vantagem, mas como dito antes, só trabalha com valores positivos em suas arestas.
Goodrich e Tamassia (2007) ressaltam que, devemos sempre buscar fazer com que
o grafo em que está sendo aplicado o algoritmo, deva ser um dígrafo (direcionado),
pois de outra forma (grafo não direcionado) poderíamos ir e vir por uma mesma
aresta, podendo ocorrer um loop (ciclo), deixando os pesos das arestas negativos, e
caso isso ocorra, se perderia o valor da distância entre os vértices, pois valores
negativos invalidam a noção de distância baseada no peso das arestas.
O algoritmo de bellman-ford, é mais fácil de ser compreendido e aplicado do que o
de Dijkstra. Tendo como exemplo o grafo da figura 13.0, é possível criar uma tabela
com os vértices de origem, destino e a distancia entre eles, criando uma maneira
mais didática para o entendimento da forma de aplicação e funcionamento do
algoritmo.
Figura 13.0 – Grafo orientado
Fonte: Adaptado pelo autor.
Origem
Destino
A
B
Distância
(Peso)
4
A
C
2
B
A
4
B
D
-5
C
A
2
C
E
3
D
C
8
E
D
-6
Tabela 2.0 – Tabela com os dados do grafo
da figura 13.0.
Fonte: Adaptado pelo autor.
32
O algoritmo de bellman-ford, baseia-se em:
Figura 14.0 – Pseudocódigo algoritmo de Bellman-ford
Fonte: GOODRICH, TAMASSIA. Projeto de Algoritmos: Fundamentos, análise e exemplos da
Internet. (2004).
Tendo como exemplo os dados da figura 13.0 e da tabela 2.0, a aplicação do
algoritmo de Bellman-ford (com a linguagem C/C++), se daria da seguinte maneira:
#include <iostream>
#define INFINITY 0x3f3f3f3f
#define NODOS 1000
using namespace std;
typedef struct {
int source;
int dest; //destino
int weigth; // peso
}Edge;
int distancia[NODOS];
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) {
33
int i,j,trocou;
for (i = 0; i < nodecount; i++) {
distancia[i] = INFINITY;
}
distancia[source] = 0;
for (i = 0; i < nodecount; i++) {
trocou = 0;
for (j = 0; j < edgecount; j++) {
if(distancia[edges[j].dest] > distancia[edges[j].source] + edges[j].weigth) {
distancia[edges[j].dest] = distancia[edges[j].source] + edges[j].weigth;
trocou = 1;
}
}
//se nenhuma iteração teve efeito, futuras iterações estão dispensadas
if (trocou == 0) break;
}
//usado somente para detectar ciclos negativos (dispensável)
for (i = 0; i < edgecount; i++) {
if (distancia[edges[i].dest] < distancia[edges[i].source + edges[i].weigth]) {
cout << "Ciclo negativo de pesos de arestas detectado" << endl;
break;
}
}
for (i = 0; i < nodecount; i++) {
cout << "A distancia mais curta entre os nodos " << source << " e " << i <<"
eh " << distancia[i] << endl;
}
}
int main(int argc, char *argv[])
{
34
//Este caso de teste produzira as distancias entre o nodo 0 e os outros nodos
Edge Arestas[8] = {{0, 1, 4}, {0, 2, 2}, {1, 0, 4}, {1, 3, -5},
{2, 0, 2}, {2, 4, 3}, {3, 2, 8}, {4, 3, -6}};
// BellmanFord(Estrutura,arestas,vertices,origem);
BellmanFord(Arestas,8,5,0);
system("PAUSE");
return 0;
}
2.4 ANÁLISE DE ALGORITMOS
Análise de Algoritmos é uma importante área da Ciência da Computação onde são
estudados os recursos e ou tempo necessários para a execução de um determinado
algoritmo.
Ziviane(2005, p. 03) relata que:
Depois que um problema é analisado e decisões de projeto são finalizadas,
o algoritmo tem de ser implementado em um computador. Neste momento,
o projetista tem de estudar as várias opções de algoritmos a serem
utilizados, em que os aspectos de tempo de execução e espaço ocupado
são considerações importantes.
Quando o tema em análise de algoritmos é Medida do Tempo de Execução de um
Programa, é preciso se preocupar ou ficar atento em pelo menos dois tipos distintos
de problemas quando, for feita a análise de um algoritmo em particular e a análise
de uma classe de algoritmos.
Knuth (apud Ziviane, 2005, p. 03) aborda que na análise de um algoritmo em
particular, é necessário saber qual é o custo de usar um dado algoritmo para
resolver um problema específico, que neste caso deverão ser investigadas as
características importantes do algoritmo em questão (número de vezes que cada
parte do algoritmo deve ser executada). Já na análise de uma classe de algoritmos,
35
devemos nos atentar para a seguinte pergunta: qual é o algoritmo de menor custo
possível para resolver um problema particular? Geralmente neste tipo de análise,
toda uma estrutura (família) de algoritmos destinados ao mesmo tipo de problema
deve ser analisada.
Algumas técnicas e ou maneiras são utilizadas para medirmos o custo de utilização
de um algoritmo. A implementação do mesmo (algoritmo em questão) em um
computador real, seria uma das maneiras para a medição do custo de utilização
(método empírico). Mas será que os dados obtidos por este tipo de medição, seriam
precisos?
Partindo do pressuposto que o algoritmo deveria ser ótimo (trabalhar conforme o
esperado ou seu custo ser menor ou igual ao custo possível) sem interferências de
fatores não correlatos, é correto afirmar que, não poderemos ter uma medição
precisa, já que vários fatores poderiam influenciar, tais como: quantidade de
memória, processador, compilador utilizado, etc.
Para encontrarmos meios mais contundentes e adequados, precisamos utilizar
métodos matemáticos, definindo o número de operações a serem executadas e o
custo de cada operação (complexidade dos algoritmos). No final se compararmos
algoritmos destinados à resolução de um mesmo tipo de problema, com algum custo
estimado e ou esperado, podemos então ter uma base de qual algoritmo teve um
desempenho melhor. Ou ainda podemos considerar ou analisar, como foi
mencionado anteriormente, somente as partes mais relevantes do código, como os
loops, abstraindo assim as outras partes (como atribuição).
2.4.1 COMPLEXIDADE DOS ALGORITMOS - ANÁLISE ASSINTÓTICA
Segundo Merdina e Fertig (2006) os algoritmos podem ter sua classificação definida
pelo tipo de expressão matemática que defini seu comportamento na análise de
complexidade. Para isso se utiliza o comportamento assintótico da função do tempo
“T” em relação ao tamanho da entrada do algoritmo (n).
36
O tempo de resposta de um algoritmo está intrinsicamente ligado ao tamanho da
entrada dos dados (n) e também a forma como os dados são inseridos (melhor caso,
pior caso e resultado esperado ou estimado).
A análise assintótica ignora constantes dependentes da máquina e olha em vez do
tempo real de execução, o crescimento do tempo de execução T(n).
Basicamente, é correto afirmar que, a análise assintótica não define expressamente
o número total de passos e ou operações que um algoritmo fará, mas ilustra o
comportamento que o mesmo terá quando variamos o valor da entrada dos dados
(n).
A classe assintótica é representada também pela notação O.
Merdina e Fertig (2006) apontam algumas classes com esta notação:
Constante: O(1)
Logarítmica: O(lg(n)) (representamos logaritmo na base 2 como lg)
Linear: O(n) (lê-se “O de n” ou “Ordem de n”)
Quadrática: O(n²)
Cúbica: O(n³)
Exponencial: O(cn), onde c é uma constante.
Tendo como base as informações dadas neste tópico, vamos tentar analisar um
simples algoritmo que trabalhe em função da resposta de uma simples somatória:
O pseudocódigo para este algoritmo ficaria assim:
Inicio
somatoria numérico;
somatoria  0;
para i  2 até n faça
somatoria  somatoria + i*i*i*i*i*i;
fimpara
37
escreva(somatoria);
fim
Se hipoteticamente atribuíssemos para operações simples como atribuições, somas,
multiplicações, etc., o valor de 01 unidade de tempo, o valor assintótico deste
algoritmo, seria algo em torno de 6n+4, ou seja, uma equação linear, portanto O(n).
Tentar atribuir um valor com exatidão, como foi o caso do pseudocódigo anterior,
nem sempre é possível, por isso como mencionado anteriormente, a Análise
Assintótica não procura mostrar o número exato de passos ou tempo que um
algoritmo levará para executar determinada tarefa, mas sim o valor assintótico do
mesmo quando o valor da entrada dos dados (n) variar ou tender ao
∞(infinito).
Quando passamos a analisar o valor da entrada (n) em sua forma assintótica
(tendendo ao infinito) dentro de, por exemplo, a denotação O, podemos ter com mais
clareza a velocidade, ou melhor, tempo de resposta de um determinado grupo de
algoritmos. Não dependendo assim de fatores referentes à máquina (memória,
compilador, processador, etc.).
Para uma maior clareza, vamos pensar em dois algoritmos que servem para a
mesma tarefa, onde o algoritmo A tem o tempo de resposta 350n + 550, e o
algoritmo B 3n² + 20n + 3. A princípio, com entradas pequenas, o algoritmo B levará
certa vantagem quanto ao A, ex:
Valor de T(n) = 3;
A = 350 * 3 + 500 = 1550; O(n)
B = 3*3² + 20 * 3 + 3 = 90; O(n²)
Mas quando pensamos no valor de (n) subindo assintóticamente, claramente o
algoritmo A executará uma menor quantidade de tarefas para satisfazer todas as
operações do algoritmo, ex:
Valor de T(n) = 300;
A = 350 * 300 + 500 = 105500; O(n)
B = 3 * 300² + 20 * 300 + 3 = 276003; O(n²)
38
Ainda observando os exemplos acima, pode-se notar que um algoritmo de equação
linear sempre será mais rápido que um algoritmo quadrático, pois em algum ponto
(n0) o algoritmos quadrático ultrapassará o linear, assim como um O(log(n)) será
mais rápido que um linear. E também é válido dizer que, a análise assintótica
dispensa os termos de menor valor, pois os mesmos não influenciam de maneira
significativa no resultado final. Sendo assim, em um algoritmo de equação 5n² + 20n
+ 6, somente será levado em consideração o maior termo, no caso 5n², logo teremos
a denotação O(n²) para tal algoritmo.
A figura 15.0 mostra com mais clareza como algoritmos de diferentes notações se
comportam quando a entrada (n) é variada, independentemente se o computador
que o algoritmo de maior ordem esteja rodando seja algumas vezes mais rápido que
o outro algoritmo. Neste exemplo, pode-se observar que, em algum ponto quando a
marca do n0 é assintoticamente alta, o algoritmo de proporção f(n) passa ser a
melhor escolha.
Figura 15.0: Análise Assintótica
Fonte: GOODRICH, TAMASSIA. Estrutura de dados e algoritmos em Java. 4. ed. ( 2007).
É válido ressaltar que, dependendo do tamanho da entrada e a forma como a
mesma é inserida, muitas vezes poderemos optar por um algoritmo de ordem maior,
pois seu rendimento inicial, quando o valor de n ainda é pequeno, ou seja, não
atingiu o ponto n0, pode ser mais rápido que o algoritmo de menor ordem.
39
2.4.2 PROGRAMAÇÃO LINEAR
Segundo Gomes e Ribeiro (2004, p. 59) “a programação linear lida basicamente com
o problema de alocar recursos escassos a atividades que por eles “competem” entre
si, e cujo modelo se representa por meio de expressões lineares”.
Uma observação válida é que, o termo programação, não diz respeito à
programação de computadores, mas sim a planejamento, estrutura de ajuda a
decisões, como alocar melhor os recursos disponíveis.
Como base para uma melhor compreensão, será abordado um caso hipotético onde
uma Empresa pretende otimizar sua produção mensal de cadeiras e mesas,
visando, logicamente, diminuir seus custos e maximizar os lucros. Sabendo-se que,
cada mesa precisa de 6 horas de carpintaria e 4 horas de pintura, as cadeiras
precisam de 4 horas de carpintaria e 2 horas de pintura. Durante o período
analisado, há disponível 240 horas-homem de carpintaria e 100 horas/homem de
pintura. Cada mesa lucra R$ 7,00 e cada cadeira R$ 5,00.
Montando os dados em uma tabela temos:
Horas para produzir 01 unidade
Departamento
Horas
Mesas (M)
Cadeiras (C)
Carpintaria
6
4
240
Pintura
4
2
100
Lucro unitário
7
5
disponíveis
Tabela 3.0 – Exemplo PL
Fonte: Adaptado pelo autor
Depois de modelados os dados em uma tabela e já sabermos o que a empresa
procura (otimizar custos e maximizar lucros), temos de observar os recursos
escassos ( horas disponíveis).
Agora é necessário observar, qual produto deverá ser utilizado, produzido, em
detrimento de outro. Exemplo será que devemos produzir mais mesas? Isso
40
consequentemente exigiria mais madeira e tempo, o que deixaria as mesas com
menor uso de tais recursos.
Segundo Chase, Jacob e Aquilano (2006, p. 665) “quando um único objetivo deve
ser maximizado (como o lucro) ou minimizado (como os custos), pode-se utilizar a
programação linear”.
Utilizando a formula para Maximizar (Z = C1X1 + C2X2 + ... + CnXn ou
) e aplicando os dados informados pelo problema, obteremos o
valor de Z (Maximização dos lucros), logicamente substituindo os valores de C1X1 ...
pelos valores reais de cadeiras (C) e mesas (M).
Logo a função para maximização seria 7M + 5C, ou seja, a quantidade de mesas x
R$ 7,00 + a quantidade de cadeiras x R$ 5 reais.
Observando as restrições implícitas pelo problema (tempo de carpintaria 240h,
tempo de pintura 100h), sabemos que, cada mesa gasta 6h e cada cadeira 4h, logo
temos a inequação de 6M + 4C <= 240. Fazendo o mesmo processo para a pintura,
temos a inequação 4M + 2C <= 100.
Conclui-se portanto que, para todo M,C >= 0, focando a maximização dos lucros 7M
+ 5C, temos as restrições 6M + 4C <= 240 e 4M + 2C <= 100. Resolvendo assim de
forma linear o problema.
Imaginando um quadro também hipotético, onde precisaríamos modelar um cenário
de mapa rodoviário onde sua estrutura construída em grafos pode ser de proporções
gigantescas, e a necessidade de aplicar isso em um espaço ou tela de forma
otimizada, priorizando algo (qualidade da imagem, por exemplo) e observando as
restrições (tamanho da tela), o estudo desta resposta pela programação linear se
torna algo interessante.
Resumindo, como relata Chase, Jacob e Aquilano (2006, p. 665) “a programação
linear reúne às várias técnicas matemáticas utilizadas para alocar os recursos
limitados entre as demandas competitivas de uma maneira ótima”.
41
2.4.3 ALGORITMO ESCOLHIDO
A tabela 3.0 descreve o tempo de resposta (complexidade algorítmica) dos
algoritmos pesquisados para a conclusão da referente pesquisa.
AUTORES
DESCRIÇÃO
COMPLEXIDADE
Algoritmo utilizado em
buscas de menor
Bellman-Ford
caminho, diferenciado
O(va)
pois aceita pesos
negativos nas arestas.
Algoritmo utilizado em
Floyd-Warshall
buscas de menor caminho
em grafos orientados e
O(n³)
valorados.
Algoritmo utilizado em
buscas de menor caminho
Dijsktra
em uma rota, partindo de
um ponto qualquer, sendo
O(n²)
considerado um algoritmo
guloso.
Tabela 4.0 – Complexidade dos algoritmos
Fonte: Adaptado pelo autor.
Com base nas informações adquiridas através das pesquisas realizadas para este
projeto, foi utilizado para a conclusão do mesmo o algoritmo de Dijkstra. O qual
melhor se enquadra para resolução do problema proposto por esta pesquisa, visto
que, o algoritmo trabalha com pesos positivos nas arestas dos grafos, e tem uma
resposta mais rápida (O(n²)) quando se comparado aos demais algoritmos
abordados neste projeto.
42
2.5
FERRAMENTAS
(IDE’s)
E
LINGUAGEM
UTILIZADAS
NO
DESENVOLVIMENTO DO SOFTWARE
2.5.1 C#
O C# (leia-se Cê charp ou C Sharp) é uma linguagem orientada a objetos criada
pela Microsoft (baseada nas linguagens C, C++ e Java), trabalha juntamente com
sua plataforma .Net.
Sharp (2008) relata que o C# é uma poderosa linguagem orientada para
componentes da Microsoft, e que para um usuário com alguma experiência em
outras linguagens orientadas a objetos como C++ e Java, a sua assimilação com a
sintaxe e com o modo de trabalhar com a mesma será rápida.
O protótipo foi desenvolvido com a utilização da linguagem C# juntamente com o kit
de
desenvolvimento
Microsoft
Visual
C#
2008
Express
(kit
gratuito
de
desenvolvimento de aplicativos, criado pela Microsoft, com o intuito de auxiliar os
programadores que trabalham com a linguagem C#).
A escolha desta linguagem e IDE para o desenvolvimento do aplicativo se dá pelo
fato de as mesmas terem sido usadas em algumas disciplinas estudadas durante a
graduação.
2.5.2 UML - UNIFIED MODELING LANGUAGE OU LINGUAGEM DE MODELAGEM DE DADOS
Para uma melhor visualização de algumas funções e operações do software
desenvolvido nesta pesquisa, foi utilizada como técnica de modelagem dos dados a
UML.
Segundo Booch, Rumbauch e Jacobson (2005, p. 13), “a UML, Linguagem Unificada
de Modelagem, é uma linguagem gráfica para visualização, especificação,
construção e documentação de artefatos de sistemas complexos de software”.
43
Booch, Rumbauch e Jacobson (2005), descrevem que a UML surgiu por volta da
metade da década de 90, quando Booch, Jacobson e Rumbauch, perceberam que
seus trabalhos anteriores (Rational Software Corporation, Objectory e General
Electrics) estavam interligados de forma natural e progressiva, só lhes restando
assim, juntarem os esforços e abstraírem o melhor de cada ideia.
44
3.0 IMPLEMENTAÇÃO DIJKSTRA – PROTÓTIPO
3.1 DIAGRAMA DE CASO DE USO
Segundo Medeiros(2004), um caso de uso é uma representação de diversas,
variadas ações, as quais representam uma macroatividade.
A figura 16.0 mostra com um caso de uso, uma visão macro do Protótipo criado
nesta pesquisa.
Figura 16.0 – Diagrama de Caso de Uso – Protótipo
Fonte: Adaptado pelo Autor.
Como observado na figura 16.0, o funcionamento do software é bem simples e
objetivo, buscando mostrar na prática, o funcionamento do algoritmo de Dijkstra.
No primeiro processo o usuário irá indicar qual o tipo de grafo que o algoritmo
deverá trabalhar, e isso também influenciará na forma como as pontas das arestas
serão desenhadas pelo software. Em seguida o usuário irá criar as cidades (nós),
depois estabelecer as ligações existentes entre as mesmas e o peso (a distancia)
45
nas arestas equivalentes entre um nó e outro. Após estes processos, deverá ser
informado pelo usuário, o ponto de partida (origem) em que o algoritmo deverá
começar a buscar as menores rotas, e por último, o usuário inicia o software,
deixando todos os cálculos e processos necessários para obter a menor, ou melhor,
rota, incumbidos ao programa, onde uma vez finalizados os processos, o software
retornará, as menores distâncias entre todos os pontos do grafo, partindo do ponto
de origem informado pelo usuário.
3.1.2 DIAGRAMA DE ATIVIDADES
Os diagramas de atividades tem basicamente por função, mostrar as execuções,
tarefas e ou atividades que ocorrem entre uma atividade e outra.
Para um melhor entendimento e compreensão de algumas funcionalidades do
protótipo, foi elaborado um diagrama de atividades (figura 17.0), baseado no
processo de executar o algoritmo de Dijkstra no software, onde após a inserção dos
dados pelo usuário e acionado a funcionalidade do algoritmo, o mesmo começa a
fazer uma varredura dos dados, analisando-os e checando possíveis erros nos
dados inseridos, como peso negativo das arestas, falta de ligação entre os vértices
(nós), quantidade de nós insuficientes.
46
Figura 17.0 – Diagrama de Atividades – Executar Dijkstra
Fonte: Adaptado pelo autor
3.1.3 DIAGRAMA DE SEQUÊNCIA
Segundo Medeiros (2004, p. 147),
este diagrama pode ser usado para mostrar a evolução de uma dada
situação em determinado momento do software, mostrar uma dada
colaboração entre duas ou mais classes e pode, também, ser usado para
mostrar a tradução de um Caso de Uso desde a interação com o usuário até
a finalização daquele dado processo.
47
A figura 18.0, ilustra o diagrama de sequência do processo de execução do
algoritmo de Dijkstra. Onde o mesmo complementa o diagrama de atividades,
proporcionando assim, um melhor entendimento deste processo.
Figura 18.0 – Diagrama de sequência
Fonte: Adaptado pelo autor
3.1.4 DIAGRAMA DE CLASSES
Para representar as relações e os conceitos entre as classes que fazem parte de um
sistema, dá-se a elaboração de um diagrama de classes.
48
O protótipo apresentado neste projeto foi desenvolvido utilizado programação
orientada a objetos. Para um melhor acompanhamento e entendimento do código,
foi criado o diagrama de classes de parte do código.
Figura 19.0 – Diagrama de classe
Fonte: Adaptado pelo autor
3.2 GRAFO DE ESTUDOS – PROTÓTIPO
A imagem a seguir mostra o grafo que está pré-fixado no código do programa, se
baseando nele que foi testado, abordado e estudado o funcionamento do algoritmo
em questão (Dijkstra).
49
Figura 20.0 – Grafo pré-disposto do protótipo
Fonte: Adaptado pelo autor
3.3 PROTÓTIPO
A figura abaixo mostra a tela inicial do protótipo, onde tanto os dados de entrada,
assim como os de respostas, serão mostrados.
É nesta tela que todo o controle das informações que serão utilizadas (como tipo de
grafo (direcionado ou não), forma como os dados serão inseridos, tipo de inserção
de
dados
(manual
ou
não),
etc.)
é
administrado.
No lado direito, no pequeno espaço branco, abaixo do label Melhor caminho.:, serão
mostrados os nomes das cidades que farão parte da menor rota do grafo elaborado.
50
Figura 21.0 – Protótipo – Tela Principal
Fonte: Adaptado pelo autor
Na parte inferior da tela principal, é possível observar alguns botões, combobox,
textbox e radiobuttons, onde que, para uma correta funcionalidade do software, é
imprescindível que acha um controle correto sobre os mesmos.
Figura 21.1 – Protótipo – Tela Principal – Parte inferior
Fonte: Adaptado pelo autor
Dentro de cada combobox está a lista de cidades que estão pré-dispostas no
programa (figura 20.0), onde o usuário deverá selecionar uma cidade como origem e
outra como destino. Depois de selecionadas as cidades o usuário deverá clicar no
51
botão Dijkstra para que o programa execute o algoritmo que fará a busca pela
melhor rota entre as duas cidades selecionadas.
O botão Habilitar forma manual (ver figura 21.1) quando pressionado, habilita a
forma manual de inserção dos dados, onde fica por inteira responsabilidade do
usuário que todos os dados inseridos, estejam de forma correta, para que não haja
falha ou erros no processo de busca de menor rota.
Após todos os processos de inserção de dados, (modo manual), e pressionado o
botão Dijkstra, a parte branca da tela principal, deverá mostrar em cada nó, o valor
do seu menor caminho entre ele e o nó principal (origem), isso acontece, pois como
explicado anteriormente nesta pesquisa, o algoritmo de Dijkstra é um método
guloso, ou seja, ele não calcula somente o melhor caminho entre dois pontos de um
grafo, mas sim, o melhor caminho entre o nó principal e os demais nós do grafo,
tornando assim, cada resultado apresentado nos nós, o melhor ou menor caminho
existente.
Figura 21.2 – Protótipo – Simulação entrada de dados manualmente
Fonte: Adaptado pelo autor
52
3.3.1 IMPLEMENTAÇÃO DO ALGORITMO DE DIJKSTRA EM C SHARP
O código abaixo é parte principal ou pelo menos um pedaço dela, do algoritmo
responsável pela otimização da busca das menores rotas. O código está adaptado
para a linguagem escolhida. Tomei o cuidado de comentar os passos envolvidos
neste trecho do código, para uma melhor compreensão do mesmo.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Dijkstra
{
class Dijkstra
{
//Variáveis (vetores) para armazenamento da distância e caminho de cada nó
(vértice)
public double [] distancia;
public int [] caminho;
//Lista para armazenar os nós ainda não checados pelo algoritmo
private List<int> lista_nos = new List<int>();
//Função de inicialização
public void Inicializar(int comeco, int tamanho)
{
distancia = new double[tamanho];
caminho = new int[tamanho];
for (int i = 0; i < tamanho; i++)
{
distancia[i] = Double.PositiveInfinity; //Preenchendo com valores positivos
"infinitos"
lista_nos.Add(i); //Adicionando nós na lista ^^
}
/*Aqui, estou colocando o valor 0(zero) para o ponto inicial
e nulo (-1) para os caminhos anteriores */
distancia[comeco] = 0;
caminho[comeco] = -1;
}
53
private int proximoVertice()
{
double min = Double.PositiveInfinity;
int Vertex = -1;
//Procurando na lista pelas menores rotas (pesos nas arestas)
foreach (int j in lista_nos)
{
if (distancia[j] <= min)
{
min = distancia[j];
Vertex = j;
}
}
lista_nos.Remove(Vertex); // Retira da lista o menor vértice encontrado
return Vertex; // Retorna o vértice de menor valor encontrado naquela busca
}
//Método construtor
public Dijkstra(double[,] G, int comeco)
{
int pNegativos = 0;
//Só pra nível de observação, para não dá erro no algoritmo
//... verificando se o grafo contém algo,
//e se contém pelo menos 2 vértices (Matrix de adjacencia ...então N x N ...
colunas = linhas)
if (G.GetLength(0) < 1 || G.GetLength(0) != G.GetLength(1))
{
MessageBox.Show("Erro no gráfico", "Error", MessageBoxButtons.OK,
MessageBoxIcon.Error);
}
else
{
int tamanho = G.GetLength(0); //Instancio o tamanho que deverá ter os
meus vetores (caminho e distancia)
Inicializar(comeco, tamanho);
while (lista_nos.Count > 0)
{
int u = proximoVertice();
/* Laço inicial para a busca das conecções dos vértices */
for (int v = 0; v < tamanho; v++)
54
{
/* Checando se tem pesos negativos ligados nos vértices */
if ((G[u, v] < 0) && (pNegativos == 0))
{
MessageBox.Show("O Grafo contém pesos negativos", "Erro Pesos Negativos", MessageBoxButtons.OK, MessageBoxIcon.Error);
pNegativos = 1;
}
/* Verifica se existe alguma ligação (aresta) entre os nós em
questão*/
if ((G[u, v] > 0) && (pNegativos == 0))
{
/* Se existir, fazer o relaxamento da aresta*/
if (distancia[v] > distancia[u] + G[u, v])
{
distancia[v] = distancia[u] + G[u, v];
caminho[v] = u;
}
}
}
}
}
}
}
}
55
4.0 CONCLUSÃO E RECOMENDAÇÕES
4.1 CONCLUSÃO
Diminuir custos e aumentar a velocidade das respostas são fatores constantemente
analisados e trabalhados para obtenção de êxito em ambos.
Em problemas de menor caminho entre dois pontos de um grafo valorado, com
pesos apenas positivos, observou que o algoritmo de Dijkstra juntamente com a
linguagem C#, obteve o desempenho, por esta pesquisa, esperado.
Após pesquisar e analisar os valores assintóticos de vários algoritmos, e colocar em
prática o qual se mostrou o melhor (algoritmo de Dijkstra), foi constato que a
utilização de algoritmos que trabalham com grafos, traz um desempenho favorável.
É nítida a otimização de tempo nas respostas.
Empresas de transportes, autônomos, taxistas e afins, que trabalham no ramo de
transportes e fretes, trabalhando com softwares do mesmo gênero, poderiam
diminuir os custos com combustível, pois saberiam antes da jornada de trabalho, o
menor caminho a seguir.
4.2 RECOMENDAÇÕES
Recomendo que este projeto seja trabalhado mais amplamente, podendo o mesmo
ser migrado para plataformas Mobiles, onde suas atualizações poderiam ser feitas
através de uma base de dados, a qual conteria informações de diversas cidades e
suas distancias entre si. Também tendo uma opção onde o usuário entraria com a
informação do consumo do seu automóvel (Km/l), e ao final do processo, o software
além de trazer a menor rota, também indicaria quantos litros de combustível,
aproximadamente, o usuário iria gastar naquela viagem. Trazendo assim um
conforto e praticidade aos profissionais do ramo de transporte (taxistas, autônomos,
etc.). Pois o funcionamento desde protótipo, não se baseia em como chegar a um
56
determinado local, mas sim, quais são os melhores ou menores caminhos a seguir
para chegar lá.
57
5.0 REFERÊNCIAS BIBLIOGRÁFICAS
1.
ANDRADE, Maria Margarida de. Introdução à metodologia do trabalho
científico: elaboração de trabalhos na graduação. 5. ed. São Paulo: Atlas, 2001.
2.
BAJPAI, Avi C.; MUSTOE Leslie R.; VALKER, Dennis. Matemática para
engenheiros. São Paulo: Hemus-Livraria Editora Ltda. 1980.
3.
BONCHEV, Danail; ROUVRAY, Denni H. Chemical Graph Theory:
introduction and fundamentals. 1. ed. Amsterdam: Gordon and Breach Science
Publishers S.A, 1991.
4.
CHASE,
Richard
B.;
JACOBS
F.
Robert;
AQUILANO,
Nicholas
J.
Administração da produção para a vantagem competitiva. Porto Alegre:
Bookman, 2006.
5.
DEWDNEY, A.K. 20.000 léguas matemáticas: um passeio pelo misterioso
mundo dos números / A.K. Dewdney. Rio de Janeiro: Jorge Zahar Ed., 2000.
6.
GIL, Antonio Carlos. Como Elaborar Projetos de Pesquisa. 4.ed. São Paulo:
Atlas,2007.
7.
GOLDBARG,
Marco
Cesar;
LUNA,
Henrique
Pacca
L.
Otimização
combinatória e programação linear. 2. Ed. Rio de Janeiro: Elsevier, 2005.
8.
GOMES, Carlos Francisco Simões; RIBEIRO, Priscila Cristina Cabral. Gestão
da Cadeia de Suprimentos integrada à Tecnologia da Informação. São Paulo :
Pioneira Thomson Learning, 2004.
9.
GOODRICH, Michael T; TAMASSIA, Roberto. Estrutura de dados e
algoritmos em Java. 4. ed. – Porto Alegre : Bookman, 2007.
58
10.
GOODRICH, Michael T; TAMASSIA, Roberto. Projeto de Algoritmos:
Fundamentos,
análise
e
exemplos
da
Internet.
Porto
Alegre:
Bookman
CompanhiaEd, 2004.
11.
do
MARIANI, Antonio Carlos. Livro eletrônico: Algoritmo de Dijkstra para cálculo
Caminho
de
Custo
Mínimo.
Disponível
em
http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html (Acessado em maio de
2012).
12.
MEDEIROS, Ernani Sales de. Desenvolvendo software com UML 2.0:
definitivo. São Paulo: Pearson Makron Books, 2004.
13.
MEDINA, Marco; FERTIG, Cristina. Algoritmos e programação: teoria e
prática. São Paulo: Novatec Editora, 2006.
14.
MERTENS, Roberto S. Kahlmeyer; FUMANGA, Mario; TOFFANO, Claudia
Benevento; SIQUEIRA, Fabio. Como elaborar projetos de pesquisa: Linguagem e
método. 1. ed. Rio de Janeiro: FGV, 2007.
15.
OLIVEIRA, Tereza Farias de; NUNES, Márcia Vidal. Cidadania e cultura
digital: apropriações populares da Internet. Rio de Janeiro: E-papers, 2011.
16.
REIS, Linda G. Produção de monografia da teoria à prática / Linda G. Reis.
2. ed.Brasília : Senac-DF, 2008.
17.
RICHARDSON, Robert Jarry. Pesquisa social: métodos e técnicas. São
Paulo:Atlas, 1999.
18.
SAID, Ricardo. Curso de Lógica de Programação. São Paulo: Digerati
Books, 2007.
19.
SHARP, John. Microsoft Visual C# 2008: passo a passo / John Sharp. Porto
Alegre : Bookman, 2008.
59
20.
VERGARA, Sylvia Constant. Projetos e relatórios de pesquisa em
administração. 4. ed. São Paulo: Atlas, 2003.
21.
ZIVIANE, Nivio. Projeto de algoritmos: com Implementações em Pascal e C.
2. ed. rev. e ampl. São Paulo: Pioneira Thomson Learning, 2005.