Algoritmos em grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2963 palavras )
  • Download(s) : 0
  • Publicado : 24 de novembro de 2012
Ler documento completo
Amostra do texto
Departamento de Ciência da Computação-UFMG
ALGORITMOS E ESTRUTURAS DE DADOS III
Nome: Pedro Magalhães Fortini
TRABALHO PRÁTICO 1

1. Introdução

O objetivo principal do trabalho prático proposto é a implementação e uso de algoritmos para a estrutura de dados grafo, além do exercício da linguagem de programação C.
Para tal, nos foi apresentado o problema de alocação da filial de umaempresa distribuidora de produtos chamada Atlanticon. A Atlanticon decidiu instalar uma nova filial em dada região e necessita saber onde deve ser instalada sua filial, dessa forma, ela conta com a malha viária da região o que permite saber a distância entre duas cidades quaisquer que sejam conectadas por algum trilho. De posse da malha viária, o objetivo é determinar qual é a melhor cidade para ainstalação da filial em cada um de três cenários possíveis, são eles:

- Cenário 1: No primeiro cenário a cidade deve ser escolhida de modo a minimizar os custos de entrega da Atlanticon, em especial o gasto em combustível pelos trens. Considerando que cada cidade emite a mesma quantidade de pedidos em um mesmo intervalo de tempo.

- Cenário 2: Nesse cenário deve ser levado em conta também onúmero de pedidos feito por cada cidade. Assim, além da malha de distâncias entre as cidades, também será fornecida a média de pedidos de cada cidade. Considerando que a proporção desses pedidos entre as cidades vai se manter a mesma, devemos agora decidir a
Localização da filial levando em conta o volume de pedidos de cada cidade além de minimizar o gasto de combustível nas entregas.

- Cenário 3:A Atlanticon decidiu lançar um novo serviço que consiste em uma taxa adicional paga no momento da compra de modo a garantir que produto será entregue rigorosamente dentro de um prazo de X horas. A empresa, portanto, gostaria de saber em qual cidade deveria ser instalada a filial para garantir o menor valor de X, considerando que todos os trens viajam a velocidade constante.

Além de determinarpara cada cenário qual a melhor escolha de cidade para instalação da filial, deve ser determinado também o aumento percentual em gasto de combustível caso a escolha seja feita tendo como base o cenário 3 em detrimento do cenário1.Assim, para cada instância do problema, recebemos a malha viária das cidades, que é um grafo não-direcionado, conectado e ponderado, no qual os vértices representam ascidades da região, e as arestas indicam a existência de uma malha viária ligando as cidades com o peso associado sendo a distância entre as mesmas, e um vetor com a média de pedidos feitos por cada cidade na região.



2. Solução Proposta

Tendo em vista a modelagem do problema como um grafo não-direcionado, conectado e ponderado, o algoritmo base utilizado na solução de todos os cenáriospropostos foi o algoritmo de Dijkstra para caminhos mais curtos entre um vértice origem e todos os demais vértices de um dado grafo.
Um caminho mais curto em um grafo G, não pode conter ciclos, uma vez que a remoção do ciclo do caminho produz um caminho com os mesmos vértices origem e destino e com menor peso, assim, faz sentido se falar em uma árvore de caminhos mais curtos, uma vez que o caminhodeve ser conectado. No algoritmo de Dijkstra, a árvore de caminhos mais curtos fica armazenada em um vetor Antecessor, sendo que para cada vértice v pertencente ao conjunto de vértices de G, o Antecessor [v] é outro vértice u que o antecede na árvore de caminhos mais curtos. A principal técnica utilizada no algortimo de Dijkstra é o relaxamento, que faz uso de um vetor p, no qual p[v] armazena umaestimativa de caminho mais curto entre o vértice origem e o vértice v. O processo de relaxamento de uma aresta (u, v) consiste em verificar se é possível melhorar o melhor caminho obtido até o momento até v se passarmos por u, se isso acontecer, então o p[v] e Antecessor [v] devem ser atualizados. O algoritmo de Dijkstra também faz uso de um heap indireto, no qual os vértices do grafo são...
tracking img