Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar…

Questão

Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias vilas e a escola, minimizando tempo total e respeitando capacidade dos ônibus. Descreva as estruturas (registros, listas, matrizes, grafos), o formato dos registros e a estratégia algorítmica a ser adotada.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Resposta modelo — Estruturas: (1) Registro Vila {id, coordenadas, alunos, janela_horária, demanda} e Registro Ônibus {id, capacidade, tempo_disponível}. (2) Grafo G(V,N): vértices = vilas ? escola; arestas = caminhos rodoviários com peso = tempo estimado. Implementar grafo como lista de adjacência de registros de aresta {destino, tempo, distância, capacidade_rodovia}. (3) Matriz de distâncias D[n×n] (opcional) contendo tempos mínimos entre todos os pares, gerada por algorítmo de caminhos mínimos (Dijkstra por fonte ou Floyd–Warshall se n pequeno), para acelerar consultas durante roteamento. Algoritmo: (A) Coletar dados e construir registros; (B) Construir lista de adjacência e, se conveniente, calcular matriz D de tempos mínimos; (C) Agrupar vilas por proximidade e demanda com heurística gulosa: ordenar vértices por distância à escola e atribuir a cada ônibus até sua capacidade (nearest-neighbor respeitando janelas); (D) Para cada rota inicial aplicar refinamento local (2-opt ou troca entre rotas) usando D para avaliar ganho; (E) Validar janelas temporais e reatribuir se necessário. Justificativa técnica: o grafo modela conectividade real e permite calcular caminhos mínimos; a lista de adjacência é eficiente para grafos esparsos; a matriz D acelera avaliações de custo entre pares durante heurísticas. Complexidade e trade-offs: Dijkstra por origem O(m log n) por origem; Floyd–Warshall O(n^3) apenas se n pequeno. Para otimização global do tipo VRP, usar heurísticas (cluster-first, route-second) e depois aprimorar; registrar resultados em listas de registros para facilitar apresentação e iteração colaborativa.

Explicação

A proposta abrange estruturas adequadas para modelar o problema, como registros para vilas e ônibus, além de um grafo que representa a conectividade entre os pontos. A estratégia algorítmica combina a construção de um grafo com uma heurística gulosa para otimizar as rotas, considerando a capacidade dos ônibus e as janelas de tempo. A inclusão de uma matriz de distâncias permite acelerar o processo de avaliação, tornando o algoritmo mais eficiente na busca por soluções.

Raio-X da questão

Questões parecidas com resolução

• Descreva um algoritmo colaborativo para distribuir notebooks entre turmas de várias escolas, detalhando como representar…
• Descreva com precisão o algoritmo e as estruturas de dados (registros, listas ou grafo) para um programa que organiza…
• Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
• Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de…
• Descreva um algoritmo colaborativo que use um grafo para alocar professores a turmas considerando restrições de horário…
• Elabore um algoritmo simples que utilize árvores ou grafos para resolver um problema cotidiano, como o planejamento de…

Todas as questões de Algoritmos