MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-083

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 da personagem durante a aventura, é disponibilizado um mapa semelhante ao da figura abaixo, mas com uma extensão maior. Nele, cada ponto indicado 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, as seguintes estratégias foram consideradas 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 que lista TODAS as estratégias que podem ser usadas, individualmente, com sucesso, na resolução do problema:

1. I, II, III, IV.
2. Apenas I, II e IV.
3. Apenas I, III e IV.
4. Apenas I e IV.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira