Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um…
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
Descreva um algoritmo que poderia ser utilizado para encontrar o caminho mais curto entre duas cidades em um mapa representado por grafos. Explique como as variáveis e as arestas devem ser definidas para que o algoritmo funcione corretamente.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Um algoritmo como Dijkstra pode ser utilizado para encontrar o caminho mais curto. As variáveis devem incluir a lista de cidades (nós) e as distâncias entre elas (arestas). É importante garantir que as arestas sejam ponderadas corretamente, representando a distância real entre as cidades. O algoritmo deve percorrer todos os nós, calculando a distância acumulada até o nó de destino, escolhendo sempre a menor distância até encontrar o caminho mais curto.
Explicação
O algoritmo de Dijkstra é eficaz para encontrar o caminho mais curto em grafos, pois utiliza uma abordagem sistemática que garante a exploração de todos os nós de forma otimizada. A definição adequada das variáveis, como cidades e distâncias, é crucial para que o algoritmo funcione, permitindo que as arestas reflitam corretamente as relações entre os nós. Ao priorizar as menores distâncias acumuladas, o algoritmo assegura que o caminho mais curto seja encontrado de maneira eficiente.
Raio-X da questão
algoritmo de caminho mais curto
avaliacao
representação de grafos · algoritmos de busca
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode descrever um algoritmo que não considera corretamente as arestas ou as variáveis necessárias para calcular o caminho mais curto.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Na cantina da escola, Ana informa o lanche desejado, a quantidade e se vai pagar em dinheiro ou cartão. A atendente…
- Em um jogo criado pela turma, a pontuação de cada equipe é calculada multiplicando a quantidade de desafios concluídos…
- Em uma exposição, um painel registrou as cores dos crachás lidos na entrada. Lista A: azul, verde, azul, amarelo. Lista…
- Em uma cozinha, duas receitas foram preparadas em horários diferentes. Receita 1: uma torta de legumes começou a assar…
- Por que uma cozinha solidária pode ter alimentos guardados e, ainda assim, não conseguir montar todas as cestas…
- Moradores acompanham, pelo celular, um sistema de irrigação instalado em canteiros de uma praça. A cada manhã, dois…
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