Teoria de grafos - Atividade 3

Prévia do material em texto

Teoria dos Grafos 
 
Atividade 3 
 
Pergunta: 
Os grafos são ferramentas matemáticas que possibilitam propor soluções para 
diversos problemas, dessa forma, são comumente utilizadas na busca de 
soluções em diversos segmentos. Uma indústria de insumos para produtos 
farmacêuticos faz entregas em uma determinada região do país, e devido ao baixo 
tempo que esses produtos químicos podem permanecer nas condições de 
transporte no caminhão. São necessários alguns planejamentos de qual o melhor 
caminho a seguir. O trajeto é representado pela Tabela 1. 
 AAA BBB CCC DDD EEE FFF GGG HHH III JJJ 
AAA 20 20 38 39 46 
BBB 20 27 44 
CCC 20 27 45 32 
DDD 38 44 45 21 20 26 
EEE 39 
FFF 46 21 17 
GGG 20 17 
HHH 26 36 
III 17 36 
JJJ 32 17 
 
Tabela 01 - Rotas de Entrega 
Fonte: Elaborada pelo autor. 
 
Porém, para que não ocorra aumento no tempo de entrega, é necessário 
desenvolver um grafo planar, com os seus respectivos custos, de forma que se 
encontre o menor trajeto entre as cidades AAA e FFF. 
Caro(a) estudante, considerando o problema apresentado, para buscar a solução 
é necessário fazer o grafo planar, e analisar o menor custo de deslocamento para 
minimizar o tempo de entrega dos insumos. Sendo assim, haveria uma forma de 
propor uma solução do problema apresentado, com a utilização de alguma técnica 
encontrada na teoria dos grafos? 
 
 
 
 
Respostas: 
 
 Conforme o exposto na questão, a tabela pode ser representada pelo grafo 
abaixo: 
 
 
 
Onde, se apropriando de um algoritmo A* o resultado do menor trajeto de entrega 
entra cidade AAA e FFF é o caminho: 
 
Posição Atual Próximo Destino Valor Aresta Valor Total 
AAA FFF 46 46 
 
AAA => FFF. 
 Caso a empresa decida fazer a entregar utilizando o melhor caminho passando 
por todos as cidades apenas uma vez e efetuando as entregas no maior número de 
cidades partindo do ponto AAA até o ponto FFF o caminho ficaria da seguinte forma: 
 
Posição Atual Próximo Destino Valor Aresta Valor Total 
AAA BBB 20 20 
BBB CCC 27 47 
CCC JJJ 32 79 
JJJ GGG 17 96 
GGG DDD 20 116 
DDD FFF 20 136 
 
AAA =>BBB=>CCC=>JJJ=>GGG=>DDD=>FFF. 
 
 
Neste caso poderia ser implementando junto ao Algoritmo A* um outro array para 
contar o número de vetores visitados fazendo prioridade o maior número de vetores no 
array com o menor custo de viagens, porém neste caso específico, as cidades EEE, III 
e HHH não fariam parte do percurso devido a suas arestas orientadas. Esta solução não 
é uma solução ótima para o grafo, porém ela consegue passar no maior número de 
cidade sem repetir nenhuma, partindo do ponto AAA até o ponto FFF. 
 
Um caminho ideal para uma possível resolução do problema seria encontrar um 
caminho ótimo conforme o PCV (problema do caixeiro viajante), onde seria necessário 
iniciar o ponto de partida do nó BBB e o nó final seria o III e num trecho deste caminho 
é possível fazer a entrega da cidade AAA até FFF no menor custo possível, pois as 
cidades esta ligadas diretamente. 
 
 
 
 
 
Posição Atual Próximo Destino Valor Aresta Valor Total 
BBB CCC 27 27 
CCC JJJ 32 59 
JJJ GGG 17 76 
GGG DDD 20 96 
DDD EEE 21 117 
EEE AAA 39 156 
AAA FFF 46 202 
FFF HHH 17 219 
HHH III 36 255 
 
BBB=>CCC=>JJJ=>GGG=>DDD=>EEE=>AAA=>FFF=>HHH=>III. 
 
 
 
Referencias: 
Pesquisa Operacional II - Aula 08 - O problema do Caixeiro Viajante - UNIVESP 
< https://www.youtube.com/watch?v=yI9bRgXbE1c >