Lista de Exercícios - Cálculo de Distâncias e Vizinhança entre Cidades

Universidade Federal Rural do SemiÁrido Departamento de Engenharias e Tecnologia LAED II PET2037 e PEX1247 Professor Kennedy Lopes Data 13112022 Roteiro 03 Introdução A lista de cidades apresentada no arquivo cidadescsv se encontram geograficamente nas localizações indicadas no arquivo coordenadascsv Sabendo disso podese calcular com esses arquivos as distâncias entre as cidades A e B a partir de suas latitudes e longitudes distAB Ax Bx² Ay By² Sendo Ax e Ay a longitude e latitude da cidade A e Bx e By são a latitude e longitude da cidade B Exemplo hipotético Cidade ALat 10 Log 20 Cidade BLat 15 Log 18 distAB Ax Bx² Ay By² 1 distAB 10 15² 20 18² 2 distAB 5² 3² 3 distAB 25 9 4 distAB 583 km 5 Considere que as distâncias são medidas em km Novo cálculo de vizinhança A vizinhança entre cidades pode ser definida pelo motivo das cidades terem uma fronteira em comum ou não Deste modo a cidade de Pau dos ferros por exemplo tem as cidades São Francisco do Oeste Francisco Dantas Serrinha dos pintos Antônio Martins Rafael Fernandes e Encanto como vizinhos Mas apesar disto outras cidades são influenciadas ou influenciam a cidade de Pau dos Ferros como Portalegre Martins Alexandria São Miguel entre outras mesmo não sendo vizinhos Sabendo disso a proposta desse roteiro é definir uma nova medida de vizinhança baseado na distância entre as cidades Nosso princípio será o seguinte Duas cidades serão consid eradas vizinhas ou influentes se estiverem a uma distância mínima D entre elas Um exemplo diferente do nosso mas não tão diferente de influência entre as cidades podem ser visto na figura 1 Nesta figura a influência das cidades são baseadas pela carac terísticas socioeconômicas que influenciam cada região Figure 1 Microrregiões do RN Fonte microrregiões do RN 2 Exercício avaliativo Construa um Grafo na qual Os Vértices são as cidades Se duas cidades estão a uma distância de até D km então existe uma Aresta que as conectam Questão Única I Calcule a distância entre cada dois pares de cidades vértices Se a distância for menor do que uma distância D km1 conecte as cidades por uma aresta ponderada o peso entre das arestas é igual a distância entre elas II Identifique a cidade vértice que tem mais cidades vizinhas grau dos vértices no Rio Grande do Norte em função da distância D III Qual cidade não tem vizinhos baseados na distância D no Rio Grande do Norte IV Qual a menor distância D necessária para todas as cidades sejam consideradas vizinhas no Rio Grande do Norte As respostas devem estar no arquivo maincpp com o seguinte modelo apresentado neste arquivo Observações Observação 01 Utilizem qualquer estrutura de Grafos apresentado em sala de aula Os recomendados por mim são Matriz de Adjacência ou Lista de Adjacência Na matriz de Adjacência cada elemento da matriz será representado por um número que indica baseado na distância D Negativo Se as cidades não forem vizinhas Distância entre elas Se as cidades forem vizinhas Na Lista de Adjacência o grafo é construído a partir de um vetor de listas lineares nas quais cada lista corresponde a um conjunto de cidades que são vizinhas a primeira cidade da lista 1A distância D é um parâmetro da função que o grafo será construído 3 Observação 02 Os métodos de captura de dados já foram apresentados no repositório hashTable Neste repositório já existe a construção das estrtuturas iniciais do Grafo que são as construções de GPS e Cidade Observação 03 A próxima aula será dedicada exclusivamente a produção desse grafo Espero que todos estejam presentes para que juntos possamos tirar todas as dúvidas 4