Ao criar um jogo de tabuleiro digital, você deve representar as jogadas como um grafo. Se cada movimento pode…
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
Ao criar um jogo de tabuleiro digital, você deve representar as jogadas como um grafo. Se cada movimento pode levar a um novo nó, como você descreveria o algoritmo para encontrar o caminho mais curto?
- A) Usar busca em profundidade
- B) Aplicar o algoritmo de Dijkstra
- C) Fazer uma pesquisa aleatória
- D) Utilizar o algoritmo de Prim
- E) Seguir o caminho mais longo
✅ Resposta correta: alternativa B
Resolução passo a passo
- A questão pede um algoritmo para encontrar o caminho mais curto em um grafo, em que cada movimento leva a um nó novo. Passo 2: Esse problema é o clássico de caminho mínimo entre um nó de origem e os demais. Passo 3: O algoritmo de Dijkstra resolve exatamente isso: mantém uma estimativa da menor distância conhecida até cada nó, começa pela origem com distância zero e, a cada passo, escolhe o nó ainda não processado com menor estimativa, atualizando os vizinhos quando encontra um caminho melhor. Passo 4: Ao final, cada nó tem a menor distância a partir da origem, desde que os pesos das arestas sejam não negativos, o que é natural em um jogo em que cada jogada tem um custo. Passo 5: A alternativa A está errada, pois a busca em profundidade explora um ramo inteiro antes de voltar e não garante o caminho mais curto. Passo 6: A alternativa C está errada, pois uma pesquisa aleatória não tem garantia de encontrar o menor caminho. Passo 7: A alternativa D está errada, pois o algoritmo de Prim serve para construir uma árvore geradora mínima, e não para calcular caminhos mais curtos entre dois nós. Passo 8: A alternativa E está errada, pois o caminho mais longo é o oposto do que o problema pede. Passo 9: Portanto, o gabarito B está correto.
💡 Dica: Considere algoritmos como Dijkstra ou A* para encontrar o caminho mais curto.
Alternativa por alternativa
Acredita que qualquer busca que percorre todo o grafo encontra o menor caminho, sem perceber que a busca em profundidade não compara distâncias entre os caminhos.
Por que engana: Escolher a busca em profundidade, que não garante o caminho mais curto em todos os casos.
Correto, Dijkstra é ideal para encontrar o caminho mais curto em grafos.
Imagina que testar caminhos ao acaso e ficar com o menor deles dá o resultado ótimo, usando a intuição de que muitas tentativas resolvem tudo.
Confunde caminho mínimo com árvore geradora mínima, pois ambos envolvem minimizar pesos e grafos, mas o Prim conecta todos os nós com custo total mínimo e não encontra a rota entre dois nós.
Lê o adjetivo ao contrário e interpreta 'mais curto' como 'mais longo', invertendo o objetivo do enunciado.
Raio-X da questão
caminho mais curto em grafos
avaliacao
algoritmos de busca · representação de grafos
Revisar algoritmos de busca em grafos e suas aplicações.
Escolher a busca em profundidade, que não garante o caminho mais curto em todos os casos.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Ao criar um jogo de tabuleiro digital, como você utilizaria uma árvore para representar as etapas do jogo?
- Em um jogo de tabuleiro, você precisa mover uma peça de um ponto A para um ponto B, passando por 3 obstáculos. Se cada…
- Imagine que você está programando um jogo onde os personagens precisam seguir rotas em um mapa. Quais são as etapas…
- Imagine que você está criando um jogo de tabuleiro. Como você usaria um algoritmo para decidir o movimento dos…
- Explique como listas e grafos podem ser usados em um jogo de tabuleiro virtual.
- Imagine que você está criando um jogo de tabuleiro digital. Como você usaria uma matriz para representar o tabuleiro e…
🔎 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