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
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo…
- Em um mapa de transporte, cada ligação entre dois locais tem um custo positivo, como tempo ou preço da viagem. Um…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
- Explique como um algoritmo pode ser utilizado para encontrar o caminho mais curto entre dois pontos em um grafo. Utilize…
- Dado um grafo não direcionado (representado por lista de adjacência) que modela ruas entre bairros, qual algoritmo é…
- Uma equipe de mobilidade urbana modelou um conjunto de cidades como um grafo. Cada vértice representa uma cidade, cada…
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