Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Comparar diferentes casos particulares (instâncias) de um mesmo problema, identificando as semelhanças e diferenças entre eles, e criar um algoritmo para resolver todos, fazendo uso de variáveis (parâmetros) para permitir o tratamento de todos os casos de forma genérica.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma lista de pares (origem,destino). Quais parâmetros tornam a solução genérica e que estrutura pode ser reutilizada entre instâncias para otimizar desempenho?
- A) Assinatura: caminhos_em_lote(grafo).
- B) Usar apenas um parâmetro de origem/destino na assinatura.
- C) Assinatura: caminhos_em_lote(grafo, pares, lista_pesos).
- D) Assinatura: caminhos_em_lote(grafo, pares, heurística_opcional). Parâmetros: grafo, pares, heurística/estratégia/limitações. Estrutura reutilizável: tabela de distâncias pré-computada ou árvore de caminhos por fonte (cache de SSSP).
- E) Não é necessário definir uma estrutura reutilizável entre instâncias.
✅ Resposta correta: alternativa D
Resolução passo a passo
- O problema pede uma assinatura genérica para resolver vários pares origem-destino sobre o mesmo grafo. Os parâmetros essenciais são o grafo (vértices, arestas e pesos), a lista de pares (origem, destino) e, opcionalmente, uma heurística ou estratégia de execução, como uma função de estimativa para A* ou limites de custo. Passo 2: A alternativa D cobre esses três papéis na assinatura caminhos_em_lote(grafo, pares, heurística_opcional), tornando a solução genérica e flexível. Passo 3: Para otimizar o desempenho, a estrutura reutilizável é um cache de caminhos por fonte. Como várias instâncias podem compartilhar a mesma origem, executa-se um algoritmo de caminho mínimo de fonte única (SSSP, como Dijkstra em grafos com pesos não negativos) uma só vez por origem e guarda-se a árvore de caminhos ou as distâncias obtidas, evitando recomputação. Outra opção é pré-computar uma tabela de distâncias entre os pares, útil quando o número de consultas justifica o custo. Passo 4: Por que as outras estão erradas: a alternativa A omite os pares, de modo que não há como representar as múltiplas instâncias; a alternativa B reduz a assinatura a um único par, contrariando a ideia de processamento em lote; a alternativa C inclui lista_pesos, que é redundante, pois os pesos já pertencem à estrutura do grafo; a alternativa E ignora que reaproveitar resultados entre consultas é justamente o ganho de desempenho pedido. Passo 5: Conclusão: a alternativa correta é a D, que coincide com o gabarito oficial.
💡 Dica: Considere as estruturas de dados que podem ser reutilizadas.
Alternativa por alternativa
Imagina que basta passar o grafo, pois os pares poderiam ser descobertos internamente. Esquece que a entrada do problema é justamente a lista de pares a resolver.
Acredita que um único parâmetro de origem e destino seria suficiente, confundindo a consulta isolada com o processamento de várias instâncias em lote.
Por que engana: O aluno pode confundir a necessidade de múltiplos parâmetros com a simplicidade de usar apenas um par origem/destino, levando a uma solução menos eficiente.
Entende que os pesos devem ser passados separadamente, sem perceber que eles já fazem parte da estrutura do grafo, o que torna lista_pesos redundante.
Parâmetros permitem aplicar o algoritmo a grafos e critérios distintos; reutilizar tabelas/SSSP evita recomputar caminhos repetidos, reduzindo custo ao processar várias instâncias.
Acha que cada consulta pode ser resolvida do zero, sem aproveitar resultados anteriores, desconsiderando que várias instâncias sobre o mesmo grafo permitem reutilizar distâncias e árvores de caminhos.
Raio-X da questão
caminho mínimo em grafos
avaliacao
algoritmos de grafos · estruturas de dados
Revisar algoritmos de caminho mínimo e estruturas de dados em grafos.
O aluno pode confundir a necessidade de múltiplos parâmetros com a simplicidade de usar apenas um par origem/destino, levando a uma solução menos eficiente.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Elabore um algoritmo em pseudocódigo que, dado um grafo representado por lista de adjacência e dois vértices (origem…
- Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias, qual…
- Considere um algoritmo que encontra rotas em uma rede (grafo). Para generalizá-lo a diferentes métricas de custo (tempo…
- Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa…
- Considere um problema que envolve a otimização de rotas entre várias cidades. Qual estrutura é mais eficiente para…
Todas as questões de Estratégias de solução de problemas - Generalização
🔎 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