dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Em um famoso título de video game, o herói deve percorrer um reinado para salvar sua princesa, presa em um castelo. Para expressar o progresso do personagem durante a aventura, é disponibilizado um mapa semelhante ao da figura abaixo, mas com uma extensão maior. Nele, cada ponto destacado (com uma "moeda") é uma fase, e o herói avança pelos caminhos a partir do ponto inicial (START), podendo escolher uma próxima fase sempre que vencer a atual.

Sabendo que todas as fases têm a mesma dificuldade e duram praticamente o mesmo tempo, um garoto deseja terminar o jogo da forma mais rápida possível, para que ainda lhe sobre tempo para estudar.

Nesta situação, NÃO É ÚTIL para planejar a mínima sequência de fases que se precisa jogar, do ponto inicial (START) até o castelo:
I) Aplicar busca em largura a partir do ponto inicial.
II) Aplicar busca em profundidade a partir do ponto inicial.
III) Aplicar o algoritmo de Prim a partir do ponto inicial.
IV) Aplicar o algoritmo de Dijkstra a partir do ponto inicial.

Escolha a alternativa verdadeira:

1. Todas as afirmativas estão incorretas.
2. Apenas as afirmativas I, III e IV estão incorretas.
3. Apenas as afirmativas I, II e IV estão incorretas.
4. Apenas as afirmativas I e IV estão incorretas.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira