Num mapa de ruas de uma cidade (grafo com arestas não negativas), para encontrar o menor caminho entre dois…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Num mapa de ruas de uma cidade (grafo com arestas não negativas), para encontrar o menor caminho entre dois pontos, qual estratégia algorítmica geral é mais apropriada: gulosa, força-bruta, dividir-e-conquistar ou backtracking? Explique sucintamente.
- A) Gulosa — usar algoritmo do tipo Dijkstra (seleciona localmente a melhor distância acumulada).
- B) Dividir-e-conquistar: dividir o grafo reduz complexo para O(log n).
- C) Força-bruta: testar todos os caminhos é prático e eficiente.
- D) Backtracking: explorar caminhos com retrocesso resolve em tempo polinomial.
- E) Programação dinâmica (Floyd) é a melhor para um par de vértices, tempo O(n).
✅ Resposta correta: alternativa A
Resolução passo a passo
- Resolvi a questão sem olhar o gabarito. O problema pede a estratégia geral mais apropriada para achar o menor caminho entre dois pontos de um grafo com arestas não negativas, como um mapa de ruas. Passo 2: A estratégia gulosa faz, em cada etapa, a escolha localmente ótima e nunca revisa decisões. No caso do menor caminho, o algoritmo de Dijkstra escolhe sempre o vértice ainda não visitado com menor distância acumulada a partir da origem. Com arestas não negativas, essa escolha local garante o ótimo global. Passo 3: Por isso, a alternativa A está correta e coincide com o gabarito oficial. Passo 4: A alternativa B está errada, pois dividir o grafo não reduz o problema para O(log n); o grafo precisa ser percorrido e a divisão não garante o menor caminho entre dois pontos quaisquer. Passo 5: A alternativa C está errada, pois testar todos os caminhos cresce de forma exponencial e não é prático nem eficiente em mapas reais. Passo 6: A alternativa D está errada, pois backtracking explora caminhos com retrocesso e, no pior caso, é exponencial; não resolve o problema em tempo polinomial de forma geral. Passo 7: A alternativa E está errada, pois Floyd-Warshall é programação dinâmica para todos os pares de vértices, com custo O(n^3), e não é a melhor opção para um único par; além disso, o tempo não é O(n). Conclusão: a estratégia gulosa, na forma do Dijkstra, é a mais apropriada.
💡 Dica: Considere as características de cada estratégia algorítmica.
Alternativa por alternativa
Em grafos com arestas não negativas, algoritmos gulosos como Dijkstra garantem caminho mínimo ao expandir vértices na ordem de menor distância; força-bruta seria exponencial e as demais estratégias não garantem eficiência ótima nesse caso.
O aluno acredita que dividir o grafo em partes menores torna a busca logarítmica, como ocorre na busca binária. Ele aplica a ideia de redução por metade a uma estrutura que não permite isso.
O aluno supõe que, como as ruas são finitas, testar todos os caminhos seria viável e eficiente. Ele não percebe que o número de caminhos cresce exponencialmente com o número de ruas.
Por que engana: Confundir a abordagem gulosa com a força-bruta, acreditando que testar todos os caminhos é mais eficiente.
O aluno confunde backtracking, que explora caminhos com retrocesso, com uma técnica de tempo polinomial. Ele ignora que o retrocesso, no pior caso, examina combinações exponenciais.
O aluno associa Floyd-Warshall a uma solução ótima e rápida para um único par de vértices e confunde sua complexidade com O(n). Ele não nota que o algoritmo calcula todos os pares com custo cúbico.
Raio-X da questão
menor caminho em grafos
avaliacao
algoritmos de grafos · estratégias algorítmicas
Revisar algoritmos de busca em grafos e suas aplicações.
Confundir a abordagem gulosa com a força-bruta, acreditando que testar todos os caminhos é mais eficiente.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
- Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
- — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
- Ontem o mapa do festival me mandou dar uma volta enorme reclamou uma visitante. Para reduzir aglomeracoes, a…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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