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
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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