Exercícios de Fixação 07 - Método Guloso - Gabarito

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 07
Método Guloso
 1. Eis um problema que ocorre em análise automática de programas. Para um conjunto de
variáveis x1, …, xn, são dadas algumas restrições de igualdade, da forma “xi = xj” e
algumas restrições de desigualdade “xi ≠ xj”. Será que é possível satisfazer todas elas? Por
exemplo, as restrições x1 = x2, x2 = x3, x3 = x4, x1 ≠ x4, não podem ser satisfeitas. Sendo
assim, é possível utilizar o método guloso para elaborar um algoritmo eficiente que tome
como entrada m restrições sobre n variáveis e decida se as restrições podem ser satisfeitas?
Justifique.
Sim, pois o problema exibe as propriedades exigidas por problemas aos quais podemos
empregar o MG: escolha gulosa – uma solução ótima global pode ser obtida a partir de
escolhas ótimas locais (gulosas); para cada decisão, a melhor opção é escolhida, sob uma
visão top-down e uma subestrutura ótima – uma solução ótima contém em si, soluções
ótimas para os subproblemas. 
 2. Nem sempre é possível aplicar um algoritmo guloso para resolver um problema. Existem 2
características que podem indicar que os problemas podem ser resolvidos utilizando a
estratégia gulosa. Sendo assim, explique porque o problema da mochila binária não pode ser
resolvido por um algoritmo guloso.
Na modalidade binária, quando consideramos um item para inclusão na mochila, devemos
comparar a solução para o subproblema no qual o item é incluído com a solução para o
subproblema no qual o item é excluído, antes de fazer a escolha. Neste ponto, geram-se
muitos subproblemas superpostos (caso legítimo de aplicação da PD).
 3. Considere um jogo do tipo 8-puzzle, cujo objetivo é conduzir o tabuleiro esquematizado na
figura abaixo para o seguinte estado final.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Considere ainda que, em determinado instante do jogo, se tenha o estado E0 a seguir.
Pelas regras desse jogo, sabe-se que os próximos estados possíveis são os estados E1, E2 e E3
mostrados a seguir.
Considere uma função heurística h embasada na soma das distâncias das peças em relação ao estado
final desejado, em que a distância d a que uma peça p está da posição final é dada pela soma do
número de linhas com o número de colunas que a separam da posição final desejada. Por exemplo,
em E1, d(1) = 2 + 1 = 3. 
Sendo assim, pode-se afirmar que se utilizando um algoritmo de busca gulosa pela melhor escolha
que utiliza a função h, o próximo estado no desenvolvimento do jogo a partir do estado E0 tem de
ser E3? Justifique. 
Correto pois dos três estados E1, E2 e E3 possíveis, o estado com menor soma das distâncias entre a
posição atual das peças e a posição final é o estado E3 – o que representa uma escolha gulosa.
 4. Considere o problema: Dado um grupo de cidades em uma região que está nos estágios
iniciais de planejamento e seus administradores estão decidindo onde colocar escolas. Há
apenas 2 restrições: cada escola deve ser em uma cidade e ninguém deve viajar mais que 50
km para alcançar uma delas. Qual o número mínimo de escolas necessário? 
Você recomenda o uso da estratégia gulosa para o problema? Justifique.
Sim, pois se trata de um típico problema de cobertura de vértices. Para cada cidade x, seja
Sx o conjunto de cidades a no máximo 50 km dela. Uma escola em x essencialmente
“cobriria” as outras cidades. A questão é, então, quantos conjuntos Sx têm de ser
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
selecionados para cobrir todas as cidades da região? 
Complementando, o seguinte algoritmo indica o caminho para resolver o problema.
Entrada: Um conjunto de elementos B; conjuntos S1, …, Sm  B.
Saída: Uma seleção dos Si cuja união é B.
Custo: Número de conjuntos selecionados.
Repetir até que todos os elementos de B estejam cobertos: 
Selecionar o conjunto Si com o maior número de elementos não cobertos.
 5. Suponha uma série de eventos, por exemplo, as transações feitas na bolsa de valores, na
forma compra Dell, vende HP, compra Google, … Uma certa ação pode acontecer mais de
uma vez nessa sequência. Dada uma outra sequência, decida o mais rápido possível, se ela é
uma subsequência da primeira. Elabore um algoritmo eficiente para as sequências de
tamanho m e n.
Sugestão de solução
algoritmo Subsequencia
Entrada: Sequência S' = s'1...s'm e S = s1...sn
Saída: verdadeiro, se S'  S //S' é uma subsequência de S
se m > n então
retorne falso
i   1←
para j   1, ..., n faça←
se s'i = sj então
i   i + 1←
se i > m então retorne verdadeiro
retorne falso
A complexidade do algoritmo é O(n).
 6. Foi desenvolvido um novo algoritmo para encontrar árvores espalhadas mínimas, baseado
na seguinte propriedade: Selecione qualquer ciclo no grafo e seja e, a aresta mais pesada
deste ciclo. Então, existe uma árvore espalhada mínima que não contém e . A entrada é
algum grafo não-direcionado G = (V, E), em formato de lista de adjacência, com pesos nas
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
arestas {we}. Segue o algoritmo.
ordene as arestas de acordo com seus pesos
para cada aresta e  E, em ordem decrescente de we:
se e é parte de um ciclo de G:
G = G – e //quer dizer, remova e de G
retornar G
O algoritmo é baseado no método guloso? Justifique. 
Sim, pois o problema exibe as propriedades exigidas por problemas aos quais podemos
empregar o MG: escolha gulosa (G = G – e) – uma solução ótima global pode ser obtida a
partir de escolhas ótimas locais (gulosas); para cada decisão, a melhor opção é escolhida,
sob uma visão top-down e uma subestrutura ótima – uma solução ótima contém em si,
soluções ótimas para os subproblemas. 
	Lista de Exercícios de Fixação 07