Descreva com precisão o algoritmo e as estruturas de dados (registros, listas ou grafo) para um programa que…

Questão

Descreva com precisão o algoritmo e as estruturas de dados (registros, listas ou grafo) para um programa que organiza caronas entre estudantes: cada viagem tem motorista, capacidade e horário; alunos solicitam vagas em viagens compatíveis com seu horário. O programa deve atribuir passageiros maximizando o número de alunos atendidos, sem alocar um aluno a mais de uma viagem no mesmo horário, e produzir a lista de passageiros por viagem.

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

Resposta esperada

Modelo de solução: 1) Representação de dados: registro Viagem {id, motorista, capacidade, horario}; registro Aluno {id, nome, horarios_disponiveis, pedidos}. 2) Construção do grafo bipartido: nós à esquerda = alunos; nós à direita = viagens. Adicionar aresta aluno?viagem se o horário da viagem é compatível com a disponibilidade do aluno e se o aluno solicitou essa viagem. 3) Tratar capacidade das viagens: transformar cada viagem em um nó com capacidade igual ao número de vagas, ou modelar viagem?sumidouro com capacidade = capacidade. 4) Transformação para fluxo: criar fonte conectada a cada aluno com capacidade 1; arestas aluno?viagem com capacidade 1; arestas viagem?sumidouro com capacidade = capacidade da viagem. 5) Algoritmo de otimização: aplicar algoritmo de fluxo máximo (por exemplo Dinic ou Edmonds–Karp) para obter o emparelhamento que maximiza o número de alunos atendidos. Alternativa heurística: ordenar pedidos por prioridade e preencher vagas sequencialmente (menor garantia ótima). 6) Pós-processamento: a partir do fluxo, para cada viagem listar os alunos com aresta aluno?viagem saturada; gerar registros de saída por viagem. 7) Complexidade e justificativa: construção do grafo leva O(V+E); fluxo máximo com Dinic tem complexidade polinomial (depende de E e V) e garante solução ótima que respeita capacidades e restrição de um aluno por horário. Observações de implementação: usar listas de adjacência para o grafo, registros para viagens e alunos, e estruturas de fila para BFS/DFS no algoritmo de fluxo; validar horários e conflitos antes de criar arestas para reduzir E.

Explicação

A solução proposta utiliza uma representação eficiente dos dados e um grafo bipartido para modelar a relação entre alunos e viagens, permitindo a aplicação de algoritmos de fluxo máximo para otimizar a alocação de passageiros. A transformação das viagens em nós com capacidade e a conexão com uma fonte e um sumidouro garantem que as restrições de capacidade e horários sejam respeitadas. Além disso, a complexidade do algoritmo é abordada, assegurando que a solução seja viável em termos de desempenho.

Raio-X da questão

Questões parecidas com resolução

• Proponha um algoritmo colaborativo que utilize grafos e matrizes para planejar rotas de transporte escolar entre várias…
• Proponha um algoritmo para alocar salas de aula a turmas considerando horários, capacidade das salas e conflitos de…
• Descreva um algoritmo colaborativo para distribuir notebooks entre turmas de várias escolas, detalhando como representar…
• Descreva um algoritmo colaborativo que use um grafo para alocar professores a turmas considerando restrições de horário…
• Projete um modelo de objeto 'TransporteEscolar' indicando os atributos e variáveis essenciais (por exemplo: id_veiculo…
• Projete um algoritmo colaborativo para formar equipes em um projeto interdisciplinar: cada estudante é um registro…

Todas as questões de Programação - Linguagem de programação