Busca de caminho mínimo na computação

Prévia do material em texto

Busca de caminho mínimo na computação
Diego Caiena Rodrigues, Luiz Felipe C. Carvalho, Gabriel Carvalho Pinto,
Rodrigo F. P. Oliveira, Rômulo G. S. Sá, Wagner S. de Oliveira Jr
Instituto Ciberespacial – Universidade Federal Rural da Amazônia (UFRA)
{rodrigoacademy2018,romulo.gabss,caienawork,lfcunha.ti,gabrielcarvalhopi
nto123}@gmail.com
Abstract. This article aims to present the main uses of shortest path search
algorithms in the field of computing, which are Network Quality Services and
Vehicle Traffic Routing. Through the presentation of graph theory, the shortest
path problem and its algorithms.
Resumo. Este artigo tem como objetivo apresentar as principais utilizações
dos algoritmos de busca em caminhos mínimos na área da computação, que
são Serviços de Qualidade de Redes e Roteamento de Tráfego de Veículos.
Através da apresentação da teoria de grafos, do problema de caminho mínimo
e dos seus algoritmos.
1. Introdução
Assim como o, prático e pertinente, questionamento que busca saber o menor tempo
entre uma cidade e outra, ou então sobre o menor caminho até determinado destino,
estamos falando do Problema de Caminho Mínimo, um dos, devido a sua natureza
genérica, problemas mais estudados em meio a academia nas mais diversas áreas, desde
de Engenharia de transportes à Inteligência Artificial, sendo principalmente um assunto
contido na Teoria de Grafos.
A busca de caminho mínimo mesmo sendo popular em muitas das problemáticas
que podem ser representadas em grafos ou rede, são poucos os algoritmos mais
conhecidos, como: Algoritmo de Dijkstra e o de Bellman-Ford. Dentre todas as áreas
nas quais o Problema de Caminho Mínimo pode ser empregado como parte de
aplicações computacionais, conforme as literaturas pesquisadas, quais algoritmos de
busca de caminho mínimo são mais usados e em que áreas da computação são mais
comumente aplicadas é o que abordaremos no presente trabalho.
2. Embasamento Teórico
2.1. Grafos
Surgida a partir dos estudos de Euler, Kirchhoff e Cayley, a teoria dos grafos possui
aplicação em diversas ciências, principalmente as exatas, podendo ir desde a matemática
até as ciências sociais. O primeiro e mais famoso problema desenvolvido é o das pontes
de Königsberg - que consiste em determinar as possibilidades de transitar por toda a
cidade, tendo o ponto inicial e o final como o mesmo lugar, passando apenas uma vez
por todas as pontes.
De acordo com Prestes (2020) em seu livro introdução à teoria dos grafos:
“um grafo é uma estrutura discreta formada por um conjunto não vazio de vértices V e
um conjunto de arestas A ⊆ P(V ), onde P(V ) = {{x, y} : x, y∈ V } é o conjunto de
todos os pares não ordenados não necessariamente distintos gerados a partir de V [...]”,
ou seja um grafo é uma estrutura na qual seus conjuntos de vértices e arestas não são
vazios. Estas estruturas ainda podem ser classificadas como simples ou multigrafo.
2.2. Caminho mínimo
Como dito anteriormente, a teoria dos grafos pode ser aplicada em diversas áreas do
estudo, isso deve-se, principalmente, a mesma servir como modelo para
resolução/análise de alguns problemas como o escalonamento de processos;
reconhecimento de padrões; roteamento e dentre outras razões que levam a outros
estudos como o de caminho mínimo.
De acordo com Feofiloff (2020): “Um caminho C num grafo é mínimo se não
existe outro caminho que tenha a mesma origem e o mesmo término que C, mas
comprimento menor que o de C.” O foco principal desse conceito é o de encontrar um
caminho que gaste o menor quantitativo de recursos possíveis, indo de um ponto a outro
em um grafo múltiplo, tornando-o, assim, em um grafo simples. Dentro do estudo de
P.C.M., existem diversos métodos de resolução, dentre eles, os principais são os de
Dijkstra e Bellman-Ford.
Ambos os algoritmos tem como principal função identificar o menor caminho
entre os vértices de um determinado conjunto de arestas, sendo estes vértices contendo
valores - ponto principal onde ocorre a grande diferença entre ambos, dado que o de
Bellman-Ford atua em grafos com valores do conjunto de inteiros e o de Dijkstra atua
exclusivamente com valores naturais.
2.3. Algoritmo de Dijkstra
O algoritmo de Dijkstra tem o objetivo de alcançar o menor caminho ou o que possua o
menor custo em unidades de medidas entre todos os vértices de um grafo ponderado. O
processo de visita dos pontos ocorre inicialmente através do vértice de origem até o
mais aproximado e logo em seguida para o mais próximo assim sucessivamente até que
se tenha percorrido todos os pontos do grafo. Segundo Negri (2017) é um dos mais
eficientes quando se trata de solucionar problemas de caminhos curtos, podendo ser
aplicado somente em arestas com os valores dos seus pesos pertencentes ao conjunto
dos números naturais. As aplicações desse algoritmo são amplas podendo ser utilizadas
na construção de redes telefônicas, elétricas, rodoviárias entre outros tipos, além do
roteamento para sistemas de informação de tráfego e na montagem de circuitos
eletrônicos.
2.4. Bellman-Ford
O algoritmo de Bellman-Ford, similar ao que ocorre com Dijkstra, busca o caminho
mais curto de uma única fonte em um grafo ponderado. Bellman-Ford é usado
principalmente para grafos que possuem arestas com peso negativo. O algoritmo tem o
nome de seus criadores: Richard Bellman e Lester Ford Jr, além disso possui as
características de ser mais lento em comparação ao algoritmo de Dijkstra, mas por outro
lado é mais simples de se compreender.
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/paths-and-cycles.html#path
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/graphs.html#digraph
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/paths-and-cycles.html#origin-and-terminus
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/paths-and-cycles.html#origin-and-terminus
3. Revisão de Literatura
3.1. QoS - Qualidade de serviço em redes de computadores
Qualidade de Serviço ou QoS é o efeito coletivo do desempenho de um serviço, o qual
determina o grau de satisfação de um usuário quanto ao que está sendo oferecido
Carlos Alberto Kamienski (2000). O problema que se pretende abordar nesse assunto
utilizando o conceito de caminhos mínimos está relacionado ao roteamento em redes, ou
seja determinar uma rota que usa os recursos de rede de forma eficiente e satisfaz,
simultaneamente, requisitos como a qualidade de conexão ao encontrar o menor
caminho possível a ser percorrido pelos dados de ponta a ponta na rede.
Figura 1.1: Ilustração de uma rede de computadores. Cada segmento
colorido das cores preto e vermelho representaria a aresta de um grafo e
no fim delas há uma estação ou aparelho que representaria o vértice.
3.2. Roteamento de tráfego de veículos
Convenientemente o uso de veículos particulares são a melhor opção na hora de se
deslocar entre dois locais distantes, principalmente quando se pretende economizar
tempo. A criação de aplicações que visam informar ao motorista as condições em que o
tráfego se encontra até o destino desejado, possuem em sua base a implementação
robusta de algoritmos que tendem a informar o menor caminho para se percorrer até o
destino desejado. Um grande exemplo desses sistemas é o Waze, aplicativo “mobile”
que possui navegação por GPS e com recursos que são atualizados em tempo real pelos
próprios usuários.
Figura 1.1: Imagem retirada do aplicativo Waze que demonstra a
navegação por GPS e com seus indicadores de estados sendo
atualizados em tempo real.
4. Metodologia
A pesquisa realizada possui natureza exploratória, acerca do tema de Busca de Caminho
Mínimo, com o objetivo de saber quais os algoritmos, para a presente teoria, são mais
aplicados na computação, por meio da revisão de artigos que corroborem para o
esclarecimento do tema.
Dada a pesquisa, teve como meio de busca para obtenção de artigos o Google
Acadêmico, devido a facilidade proveniente de seu motor de busca e como critério
semântico “Aplicação caminho mínimo”, tendo em vista o aprimoramento da busca não
optando por uma sentençacom coesão entre as palavra e, sim, por usar as palavras como
tags de pesquisa.
5. Considerações finais
A busca pela solução com maior eficiência e que disponibilizará ao serviço e/ou
aplicações computacionais a melhor performance, nos quesitos de resposta e entrega de
resultados processados, usando algoritmos de caminho mínimo, garantirá que as
decisões a serem tomadas automaticamente pelos sistemas e/ou o suporte para o apoio
de tomadas de decisão serão de maior clareza bem como acompanhados de uma maior
confiabilidade no que diz respeito às circunstâncias de aplicação das tecnologias.
Através do avanço dos anos e o aumento da aplicabilidade dos algoritmos de
caminho mínimo desenvolvidos, tendo como alguns de seus principais o algoritmo de
Dijkstra e o algoritmo de Bellman-Ford uma série de áreas como os serviços de redes de
computadores e variantes, serviços de transporte de pessoas e/ou cargas juntamente com
outros, foram beneficiados com os avanços que tais algoritmos proporcionam a
processos na área da computação.
Referências
Prestes, E. (2020) “Matrizes de Adjacência e de Incidência”, In: Introdução à Teoria
dos
Grafos, pages 11-13,
http://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/Livro/LivroGrafos.pdf,
July.
Feofiloff, P. (2020) “Caminhos de comprimento mínimo”,
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/shortestpaths.html, July.
“Algoritmo de Bellman-Ford” (2019). In: WIKIPÉDIA, a enciclopédia livre,
https://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Bellman-Ford&oldid=555
62162, July.
Negri, M. A. S. (2017) “Caminhos em um grafo e o algoritmo de Dijkstra”,
https://repositorio.ufsc.br/xmlui/handle/123456789/183409, July.
Uchoa, J. S. (2012) “Caminhos mínimos com recursos limitados”,
https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14012013-165742/publico/
dissertacao_joeluchoa_6659698.pdf#page=45&zoom=100,76,409, July
Kamienski, C.A. & Sadok, D. (2020) “Qualidade de Serviço na Internet”,
In: 19ª JAI (Jornada de Atualização em Informática),
https://www.cin.ufpe.br/~cak/publications/jai2000.pdf July.
http://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/Livro/LivroGrafos.pdf
https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/shortestpaths.html
https://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Bellman-Ford&oldid=55562162
https://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Bellman-Ford&oldid=55562162
https://repositorio.ufsc.br/xmlui/handle/123456789/183409
https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14012013-165742/publico/dissertacao_joeluchoa_6659698.pdf#page=45&zoom=100,76,409
https://www.teses.usp.br/teses/disponiveis/45/45134/tde-14012013-165742/publico/dissertacao_joeluchoa_6659698.pdf#page=45&zoom=100,76,409
https://www.cin.ufpe.br/~cak/publications/jai2000.pdf