Uma empresa de entregas usa um mapa digital representado por um grafo. Nesse modelo, cada cruzamento é um…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Uma empresa de entregas usa um mapa digital representado por um grafo. Nesse modelo, cada cruzamento é um vértice e cada trecho de rua é uma aresta. Como os trechos têm comprimentos e condições de trânsito diferentes, cada aresta recebe um peso correspondente ao tempo estimado de deslocamento. Para orientar o entregador entre dois pontos, o sistema deve considerar o tempo total de cada rota e indicar aquela cujo tempo total seja o menor possível. Com base no texto, qual função principal de um algoritmo de caminhos mínimos aplicado a esse grafo?
- A) Selecionar a sequência de arestas cuja soma dos tempos seja a menor possível.
- B) Contar a quantidade de pontos visitados na rede.
- C) Somar os tempos de todas as conexões da rede.
- D) Escolher a conexão com menor tempo em cada etapa.
- E) Listar todas as rotas existentes entre os pontos.
✅ Resposta correta: alternativa A
Resolução passo a passo
- O texto descreve um grafo em que vértices são cruzamentos, arestas são trechos de rua e cada aresta tem peso igual ao tempo estimado de deslocamento.
- O enunciado afirma que o sistema deve considerar o tempo total de cada rota e indicar aquela cujo tempo total seja o menor possível.
- Um algoritmo de caminhos mínimos tem exatamente essa finalidade: encontrar, entre dois vértices, a sequência de arestas cuja soma dos pesos é a menor possível. Logo, a alternativa A está correta, e ela coincide com o gabarito oficial.
- A alternativa B está errada, pois contar pontos visitados não envolve pesos nem tempo total de rota.
- A alternativa C está errada, pois somar todas as conexões da rede não produz nenhum caminho entre dois pontos.
- A alternativa D está errada, pois escolher a aresta mais barata em cada etapa é uma heurística gulosa que nem sempre gera o caminho de menor tempo total.
- A alternativa E está errada, pois listar todas as rotas é uma tarefa de enumeração, não de otimização, e o texto pede apenas a rota de menor tempo.
💡 Dica: Pense sobre os algoritmos de grafos conhecidos.
Alternativa por alternativa
Como cada aresta possui um peso associado ao tempo de deslocamento, o algoritmo deve comparar as rotas possíveis considerando a soma dos pesos de suas arestas. A rota escolhida é aquela com o menor tempo total, e não necessariamente a que possui menos trechos ou a que apresenta a conexão individual mais rápida.
O aluno entende que o algoritmo serve para contabilizar os vértices da rede, ignorando que o foco está nos pesos (tempos) das arestas.
O aluno acredita que o objetivo é somar o tempo de todos os trechos da cidade, sem perceber que o sistema busca um caminho entre dois pontos específicos.
Por que engana: Confundir caminho com menos arestas com caminho de menor custo, escolhendo o caminho com menos passos em vez do menor peso total.
O aluno confunde o caminho mínimo global com a escolha local da aresta mais barata a cada passo, que pode levar a uma rota de tempo total maior.
O aluno interpreta que a tarefa é listar todas as possibilidades de rota, quando o enunciado pede apenas aquela de tempo total mínimo.
Raio-X da questão
caminho mais curto em grafos
avaliacao
conceito de grafos · noções de algoritmos
Revisar os algoritmos de busca em grafos, como Dijkstra.
Confundir caminho com menos arestas com caminho de menor custo, escolhendo o caminho com menos passos em vez do menor peso total.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Explique como um algoritmo para encontrar o menor caminho em um grafo pode ajudar na otimização de rotas em um serviço…
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
- Descreva como um grafo pode ajudar a otimizar rotas de entrega em uma empresa de logística.
- Você está desenvolvendo um aplicativo de entrega e precisa otimizar as rotas. Utilizando grafos, como você aplicaria…
- Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…
- Como um grafo pode ser usado para otimizar rotas de entrega em uma cidade?
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog