Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado. Deseja-se determinar um

Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado. Deseja-se determinar um

ENADE 2014 - QUESTÃO 30

Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado. Deseja-se determinar um projeto de ligação entre esses n+1 pontos através de encanamentos com a menor extensão total. Um algoritmo proposto para a solução do problema executa os seguintes passos: 

1. Crie n+1 conjuntos unitários, cada um contendo um dos pontos a serem ligados entre si e insira esses conjuntos em um conjunto C.

2. Crie um conjunto D contendo um registro para cada combinação possível de dois pontos distintos a serem ligados. Cada registro deve conter os campos ci, cj e d, em que ci e cj são os dois pontos a serem ligados e d é a distância entre eles.

3. Enquanto D não estiver vazio faça

3.1.Remova o registro de D com o menor valor de distância d.

3.2.5e os valores de c, e c do registro removido pertencerem a conjuntos distintos de C, então:

3.2.1.Substitua estes dois conjuntos pela união entre eles.

3.2.2.Guarde o registro removido em um conjunto-solução.

Com base na descrição do problema e do algoritmo proposto, conclui-se que

A) o problema exemplifica a obtenção de uma árvore geradora mínima, portanto está no conjunto P.

B) o algoritmo é uma heurística para o Problema do Caixeiro Viajante, logo apresenta complexidade polinomial.

C) problema descrito é de otimização, logo pertence ao conjunto NP-difícil, mas não ao conjunto NP-completo.

D) uma alternativa para à solução do problema é usar o algoritmo de Dijkstra para obtenção do caminho mínimo entre dois pontos.

E) o passo de maior custo do algoritmo é a criação do conjunto D com as combinações de pontos, apresentando complexidade  computacional O(n!).

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

GABARITO:

A) o problema exemplifica a obtenção de uma árvore geradora mínima, portanto está no conjunto P.

QUESTÃO DISPONÍVEL EM:

- Prova Ciências da Computação ENADE 2014 com Gabarito