Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que uma modelagem precisa possa ser empregada durante a proposição de soluções. Essa análise deve preceder, inclusive, a etapa de projeto de um algoritmo guloso.
Nesse contexto, dado um conjunto { x1, x2, …, xn } de pontos na reta dos números reais, analise as asserções a seguir e a relação proposta entre elas.
I. É possível projetar uma estratégia gulosa para encontrar o menor conjunto de intervalos fechados de comprimento 1 (um) contendo todos os pontos.
Porque:
II. A cada etapa da estratégia gulosa uma escolha local ótima pode ser feita de modo a garantir a obtenção de uma solução final ótima.
a) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
b) As asserções I e II são proposições falsas.
c) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
d) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
e) As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Soluções para a tarefa
Resposta:
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Explicação:
Algoritmo guloso ou míope, é técnica de projeto de algoritmos que tenta resolver o problema fazendo a escolha localmente ótima em cada fase com a esperança de encontrar um ótimo global.
Resposta:
As asserções I e II são verdadeiras, e a II é uma justificativa correta da I.
Explicação:
Resposta certa. Considere o intervalo mais à esquerda. Sabemos que esse intervalo deve conter o ponto mais à esquerda. Então, sabemos que seu lado esquerdo é exatamente o ponto mais à esquerda. Portanto, simplesmente removemos qualquer ponto que não pertença ao conjunto informado e que esteja a uma unidade de distância do ponto, uma vez que eles estão contidos neste único intervalo. Em seguida, nós apenas repetimos esse processo até que todos os pontos sejam cobertos. Como em cada etapa há uma escolha claramente ótima de onde colocar o intervalo mais à esquerda, essa solução final é ótima. Portanto, ambas as afirmativas são verdadeiras e a II justifica a primeira.