o Olá meu nome é Denilson professor no curso de bacharelado em Ciência da Computação na UNESP de Presidente Prudente SP projeto e análise de algoritmos colchão sua parte de projeto de algoritmos de hoje o assunto são de tratar os algoritmos gulosos A ideia é apresentar alguns conceitos Travis para entendimento do jovem príncipe logo seguido de dois exemplos e como o próprio nome diz a última Bullón de igreja de inglês tribo ideal aí o que que ele tem esse nome o sol algoritmos na que tem esse nome porque a cada etapa em busca de uma solução para um problema se busca da solução para o problema uma gente viu né no no força brother naqueles algoritmo de backtracking The Brand of Duty não tinha várias possibilidades de caminhos a serem seguidos em busca de uma solução certo então o que acontece E lá eles acabaram testando na tua casa todas as possibilidades de rotas Até chegar na solução ou na casa de banho geral da onde né na melhor solução seria um problema de utilização tá esse sal esqueci fimose são muito utilizados para problemas de otimização que você tem que encontrar a solução ótima né que elas ter menor custo maior custo tá então são muito utilizados para ele e por que que eles têm esse nome a ideia que a etapa né em busca da solução e toma decisão que com base na informação imediata eles têm mão tá sem se preocupar com efeito da sua decisão atual na solução futura Então as decisões são tomadas localmente ou seja para pegar aquele objeto né aquele estado o aquele caminho busca da solução que parece mais apetitoso né daí fazendo essa relação com o guloso né mas apetitoso e dá aquele momento e com base nessas várias decisões locais ele espera que ao chegar no final da solução essas decisões locais pareciam a melhores naquele momento né Elas veem uma solução ótima Global tá então daí que vem Augusto musculoso daí você observar é como você tomar suas decisões locais de uma maneira bem simples né Espero que ela parece melhor naquele momento os algoritmos blog está muito direto para você construir também simples implementar geralmente Então por inscrição algoritmos muito simples né de você entender entendimento é fácil e geralmente implementação também é bem sim tá e continuando é um progresso e estou acabei de comentar né apesar de ser na vontade dele nessa cidade Pode ser que nem sempre essas decisões locais rezou tem um ótimo Global tá algoritmos gulosos né para você ter certeza que ele sempre vai chegar no seu ótimo global ou seja aquele valor ótimo que minimize o custo que você tá pretendendo Ultimate milho curso que você tá aprendendo Pretender alcançar com solução ele tem que ser muito bem testados né tem que ser provados né bem formalmente para mostrar que disseram a gente funciona que nem sempre todas as soluções é baseado não eu gosto muito longe você vai chegar na melhor solução Global tá na nós temos um conjunto de algoritmos que passam infernos vou ilustrar um exemplo aqui mas o último de gráficos ou por último de graças por exemplo de vocês vão se não desperdiço e agora desgraças escrever que tem várias propostas são normas dentre vários outros eu preciso também tem propostas de abordagem gulosa que resultam na melhor solução Global Tá mas nem sempre o algoritmo guloso é aquele que Vai resultar na melhor solução Global por exemplo aquele hoje como que ele aquele problema que a gente viu da associação de tarefas você utilizar o último guloso e depois passou o teste Pois é você pega a primeira pessoa ver qual que é a melhor solução ali para melhorar essa e selecione depois a ser uma pessoa A melhor solução para tratar as tarefas restantes e selecionam você fizer isso você vai ver que nem sempre você vai chegar na solução ótima tá sem fazer um retrocesso então é um caso ali de exemplo que se você for tentar uma abordagem gulosa você vai chegar numa solução nem sempre vai ser solução ótimo agora eu sei que você chega com esse dente né É mas tem que sempre né daqui não tá conversando problema você vai chegar na solução então por isso que a gente fala também que é meu porque ele enxergaria somente localmente o que tá a vista agora nas etapas tem observar o que vem à frente tá E aí então por isso que alguns casos ele nem sempre vou encontrar mais força não é seria os conceitos principais né básicos é você criar A ideia é bem simples aí essa ideia ela vai se aplicar as diferentes diferentes problemas né diferente abordagem ou seja em cada problema você vai ter um é que tá fogo Loose você vai tomar a decisão do estado que você vai evoluir você seja qual é o rumo que você vai tomar em busca da solução Então dependendo do problema as plantas de gulosa vale vai variar de dois problemas aqui é bem simples pouquinho mais elaborar o primeiro mais cinco seria a ideia do programa do tronco problema bem é conhecido e também bem nos ativos para você ter uma abordagem gló aí né não trocar que você consiga botar o troco né para uma pessoa ou uma máquina de vendas Pois é morna produto é porque a pessoa comprou um produto para por uma nota e automaticamente você tem que dar o troco a ideia que você utiliza nesse troco de modo que você deu a menor número possível de moeda de moedas né para alcançar aquele troco por você também não encaixa presente banco por uma loja ou em qualquer outra aplicação que você tem igual não troco tá então se treinar o troco que usando o menor número possível de moeda é bom então vamos supor algumas coisas nós temos nosso sistema monetário moedas de um centavo tem que sentar os 10 25 e 50 centavo CD1 real tá de água padronizar que tudo centavo por que ela concentrado de ônibus não existe mais é porque eu tô lembrando mas eu vou manter aqui só para interno ilustrativo tá pode ser que os países você tenha ainda essas moedas todos para compor um troco bom então novamente a padronizar todo mundo centavos né todos os males em centavos eu coloquei aqui é de um real equivale assim então qualquer ideia vamos porque eu tenho que dar um troco de 2 e 89 nesse problema no tronco ter que dar 21 retornador de 89 por ter a Audi mostra que o minimize o número de moedas que eu vou utilizar para Então tem um problema de fertilização eu tenho várias possibilidades de compor 2/89 com essas moedas certo e eu tenho que achar que elas combinação que resulte no menor número de moedas eu poderia por exemplo de usam Dois igual eu vou crescendo nos Estados Unidos criança solução até que ele encontra uma solução que resulte no menor número possível de moedas mas o problema é que eu tenho que estratégia combinatórias Três Marias ter uma ordem exponencial para ter os resultados Tá então não seria melhor opção para colocar em prática mas sim uma abordagem gulosa o que deve ser pediculose esta tarde gulosa aqui a cada etapa eu sempre prefiro ela começa a dar o troco naquele momento pela moeda de maior valor ou seja eu tô subtraindo o valor de troco da opção né para cada etapa é escolher aquela moeda de maior valor tá então aqui está em vantagem gulosos e eu falo que selecionar uma moeda de maior valor a cada etapa sotando troco é bom para eu chegar numa solução ótimo bom então aqui que tá escutando gulosa e selecionar sempre aquela moeda de maior valor se for possível que que você se for possível só não passar o valor do Audi mesmo tá então o ônibus track alguns exemplos né vamos supor 2/89 ou converter tudo para sentar você nem para padronizar a mesma unidade que que eu faria eu começo pela moeda de maior valor por exemplo de um real no bar de lá no real centavo gostoso 189 eu ainda consigo usar de um real Então vou usar novamente sobre 89 centavos consigo usuário real não consigo mais então eu vou que para a próxima moeda de maior valor né então eu vou aparecer gulosa optando por aquela moeda de maior valor os 50 centavos sobrou 39 centavos novamente vou tomar o de maior valor quanto que tá o centro da vontade 25 e sobre o cantor centavos 25mh não dá para digitar e centavos é possível sim sobrou quatro centavos de dois também não dá sim tarde um sobrou três Só me responde novamente dois centavos de um nenhum centavo agiu novamente então quê que eu tenho aqui eu tenho troco ou seja 2/89 tá então você verificar todas as possibilidades a gente combinação Essa é aquela que resulta no menor número de moedas possível que eu chegar hoje eu tinha de novo tá tô nesse exemplo de nutrição do programa do troco para esse sistema monetário que a gente está usando aqui ele é a melhor opção ou seja ele sempre Vai resultar uma solução ótima que seria isso vai sempre chegar um ótimo Global tem que todas as possibilidades de solução a melhor é dada por essa quantidade aqui esse esse algoritmo sempre resultar nessa solução ah ah se eu mudasse sistema monetário né Vamos partilhar de 50 centavo é não funcionaria né vamos ver novamente do aquelas duas lá de um real sobre aqui de novo centavo entende 5025 tenho três moedas de 25 né não dá mais para usar de 25 ou para de 10 depois os quatro de um centavo então também daria certo continuaria funcionando Nossa hoje com horroroso tá agora vamos suporte a mude o nosso sistema monetário porque eu tenho um sistema monetário fictive porque eu tenho horas de 17 de dez centavos né abordagem gulosa continuaria funcionando ou seja ela também resulta ela chega não ótimo global é melhor solução vamos observar o imagina que eu tivesse que Dao 15 centavos de troco Nossa monetária ainda sem utilizar o de 50 centavos até que ele estivesse aqui eu gostaria por duas moedas de 10 centavo sim não sistema monetário humanizar que eu tive a moeda de 1 de 7 de 10 o que aconteceria primeiro ele optaria pela moeda de maior valor por dentro 10 centavo eu estou aqui cinco centavos de 10 não dá mais certo ainda mais explodiu eu tenho quis mas de um centavo só que a gente viveu foi utilizado 6 moedas para dar um pouco de um centavo neste sistema monetário foi a melhor solução obviamente não né tem uma solução melhor ótima em que o teria três moedas para chegar nesse troco você duas moedas de sete centavos e uma moeda de um centavo tá então aqui é uma ilustração né para mostrar para você que nem sempre o algoritmo guloso né tá qualquer configuração especificação de problema e vai chegar nos melhor solução por isso que sempre você for procurar o último guloso né você vai ver que ele é bem simples você propor Mas você tem que estudar bem para verificar se realmente vai sempre chegar na melhor solução Global tá então aqui é só uma ilustração para indicar aqui variando a especificação do problema a gente vê que a mesma estratégia gulosa não serviu para encontrar a melhor solução Global tá bom então aqui eu tenho que ia o que é chamado de ótimo local seja é uma solução ótima mas é uma solução localmente ópticos ou seja tem uma outra solução é chamada de ótimo Global você é a melhor solução dentre Todas aquelas existentes para aquela especificação de problema Então encontre uma solução é que é ótima dentre as várias soluções existentes mas era localmente ótima ou seja um controle de menino mas não é o menor. Né no caso aqui sei o que a quantidade de moedas né uma quantidade de baixo não é dentro das vagas existentes mas não é aquela que resulta no no menor nos moedas faz tudo aqui ó o esporte de passeio gráfico de todas as possibilidades de de quantidade de um essa também reduzir né só que combina expressão né Então imagina que você tenha lá os mínimos locais que a gente tá vendo aqui são pontos de baixo nem é de quantidade de moedas mas tem que ter um mínimo global que aquele ponto que resulta na melhor solução seria o menor número de moedas Tá e isso a gente fosse para maximizar a uma solução estrela chamada de Março no local são pontos de Março você seja uma grande quantidade de moedas mas não é o ponto de máximo Global surge a maior quantidade de moedas sabe aqui fazer uma associação com problema está lidar mas Sport está associado com qualquer os problemas que você tem Minimizar maximizar o curso né da sua solução aqui ilustração na gente fosse entre o máximo seria todas as moedas de um centavo né porque ele tem um centavo aqui um outro né que eu tenho vai dar dessert o restante de um pra chegar no segundo centavo e aqui eu tenho aquele mínimo local que eu comentei né seria uma moeda de 10 e o resto de cinco mais de um é que seria o mínimo Global se com três moedas eu daria o troco para 15 centavos tá joia então aqui é uma ilustração do que ser esses pontos de máximo de mim tá bom então conhecer gente percebe né o Como é o funcionamento de um algoritmo guloso para esse problema de troco e vamos para um outro exemplo imagine por exemplo que você tivesse várias ilhas representadas e que por esse círculos E aí você tem um projeto de construir um Pontes em para conectar todas essas Ilhas Hum e aqui você teria o curso vamos pro custo financeiro para fazer a construção da dessas pontos a ideia que você consiga conectar todas essas vezes não seja a partir de uma ilha eu consigo acessar Qualquer uma outra tá importa vai ter que dar uma volta grande ou não o importante é que elas estejam conectados e a ideia que eu construo essas pontos de modo que as eles estejam conectados e o gaste o menor recurso financeiro possível né então qual seria a combinação de pontos que eu deveria construir para que essas Ilhas todas fiquem conectadas e o valor que eu gasto seja o menor possível então vamos poder pensar amigo é um problema de otimização que a gente tem aqui podemos pegar um Branch and Bound por exemplo né ele Faria Faria todas as combinações aqui possível um força bruta e a gente vai verificar qual é a função de ligação que conecta todas as virilhas e chega no menor valor Possível é mas isso é molhar e muito né dependendo do número de livros de contos que eu tivesse então pode ser que deveria dessa quantidade de impraticável e eu não chegue a tempo aí de ter uma resposta vai tomar uma decisão tá então por isso que era interessante que a gente tem uma outra pede a implementação de algoritmo para tentar chegar nessa solução e essa soluções consegue com algoritmos gulosos tá então você vai ver que você é uma solução Bem eficiente bem simples com algoritmos gulosos e ele sempre vai chegar na solução ótima o amor por exemplo vamos supor que você tenha escritórios né espalhados na cidade o mesmo num prédio de uma empresa e você queira conectar esses escritórios uma rede privada Você tem um projeto do do curso para fazer o cabeamento entre todas as de escritórios porque sei que tá todos conectados modo que ele se comunicasse ilustração não é apenas uma ilustração com qual seria as conexões que eu deveria estabelecer para que o conector do Connect né todos esses escritórios e eles e um gaste o menor valor possível né então mais mais uma vez um problema bem similar a gente também resolve né com algoritmos gulosos tá o próximo você já tá estudando gráficos na Uni deu né mostrou de dados não é o na disciplina de teoria dos grafos não se você já conhece grau nos você vai ver que você tem aqui uma modelagem baseada em grafos e cada um desses simples né escritórios o Williams nesse exemplo anterior ele se é representado por um vértice as conexões possíveis as possíveis conexões seriam as arestas e o curso para construir essa conexão seria o quê o peso dar essa então você tem um grafo ponderado E você quer o que fazer com que todos esses vértices estejam conectados Ou seja você tem um grafo e conexo tá E ele não quiser é Versículos ou seja uma vez que ele tá conectar se ele é conexo né partir de um ponto você consegue chegar em qualquer outro. Você já partir de um vértice você consegue caminhar né Por esse gráfico e alcançar um outro vértice diz que o gráfico é conexo Oi e o nosso problema né é chamado de árvore geradora mínima tá então a ideia aqui a partir de uma uma formação do problema né que não estão gráfico aqui ó Mas por que fosse um projeto aí dessa Assembleia das ilhas outros escritórios a gente quer chegar o que no gráfico a né Connect né então seria aqui em vermelho sendo que as arestas foram selecionadas para resultar número menor número possível né de custo para fazer essa construção então como esse gráfico nexo e ele não precisa ter ciclos né que a partir de um ponto eu consigo chegar em outro então teria uma árvore né que esse caso particular de grato dá uma árvore quando vocês saírem é um gráfico conexo e a sica então por isso que vem o nome árvore geradora mínima né então por isso que é uma árvore geradora Porque a partir dessa árvore eu consigo que chegar nesse graça original por quê Porque eu vou ter todos os vértices o e consequentemente como eu tenho todos os vértices eu tenho ter um grafo gerador e comece grafo gerador é uma árvore escrevendo não é uma geradora ele vai ser mínima porque o que essa árvore que você somar o peso das arestas dessa árvore que você encontrou ela vai ser ele vai ser o menor possível para qualquer árvore geradora né ou para qualquer árvore que você consiga encontrar É nesse grafo manter nele Connect então por isso que vem o nome árvore geradora mínima seu porque essa árvore celular vingadora e mínima porque se você somar o peso dessas arestas ela vai ser o menor número possível para se gravar Pode ser que exista a outra árvore né Por exemplo nesse caso aqui ó eu poderia tirar a seresta ABC de Deus o outro e colocar as aresta a HD peso oito tá eu teria a mesma eu teria uma outra Árvore até né porque porque outra esta e quando colocar na minha solução mas o curso não mudaria é que eu troquei amar é sempre pelo outro por outra aresta de piso 8 tá bom então aqui um exemplo vamos supor que você tem que esse problema pois classificado né Tem esse grafismo tem os vértices tem as arestas e os pesos das arestas eu quero encontrar uma árvore geradora mínima né uns porque eu cheguei nessa solução aqui ó se eu somar os pesos das arestas vou chegar no valor 40 será que é a menor árvore árvore cujos o somatório na dos pesos das arestas é o menor possível que esse gráfico Ou seja é uma árvore geradora mínima eu vou ver que não né vou ver que tem outras árvores que eu posso gerar a partir desse grato tem um custo menor ou seja o que que ser esse curso o somatório das arestas da árvore tá eu tô nesse caso do teu uma árvore geradora né ou seja parte dela consistia no braço mas ela não é ninho tá então por isso que eu eu tenho uma outra solução né que essa que está apresentado aqui embaixo eu tenho uma árvore geradora do como o somatório do peso das arestas dele é o menor possível é para qualquer árvore encontrada a partir graça ela chamado de água gerador amigo tá então a solução que eu vou por aqui para vocês nem vou apresentar né de uma maneira genérica é a solução genérica para resolver esse problema é uma estratégia baseado em algoritmos gulosos tá Ou seja a cada interação ele vai tomar uma decisão local é esperança que essa decisão local resulte na melhor solução Global tá e pra esse problema de água geradora mínima ou só últimos conhecidos de gravo a gente tem a pena bem grosso ou eles são soluções é que utilizam estratégias gulosos e resultam sempre na melhor solução é bom então vamos lá aplicar um beijo populoso com o gato aí deve ser uma gosto não deixa né tá que tem duas dois conceitos que ele vai utilizar primeira chamado de corte Ingá Instituto só indicar uma indicação que a ideia é que eu vou tô passando aqui é uma ideia alto nível do Augusto Prim tá você vai ver aqui se você estudou bem um primo você vai perceber a ideia do motivo do primo Lógico que lá no primo como você estuda o algoritmo você consegue fazer facilmente essa relação mas obviamente que alguns tem estrutura de dados de apoio para comprar Sul para simular né Essas estratégias que eu tô colocando aqui tá então Antes de mostrar o algoritmo quero colocar dois conceitos primeiro corte em Graça o corte em Graça é uma estratégia que você faz em que você compra um vídeo seu lugar nos dois conjuntos um conjunto S e todos os demais vértices sejam ver - S porque deu ver eu são todos os versos graça anos o conjunto esta você vai a régua aqui ó ó por aqui esse corte no gráfico então tem aqui ó eu estabelece um conjunto é se tá formado por a BH e o outro conjunto né seria o que todos os demais vértices restantes do meu graça então é como se tivesse estabelecendo um corte aqui nesse grau e separei de um lado esses vértices do outro lado os outros pernas né sendo aqui esses velhos que estão conjunto eles podem estar conectados né relacionados com os vértices do outro conjunto aí vem o outro conselho de todas as arestas que estão cruzando esse corte seja conectam um vértice de um conjunto Conjunto S universo do outro conjunto às vezes estão cruzando o meu corte tá e no outro conceito com base nessas arestas que estão cruzando o quarto seria uma chamado de aresta leve seja dentre todas as arestas que estão cruzando o corte Qual é aquela de menor valor tô nesse exemplo aqui eu tenho uma aresta BC né de pessoas usando o quarto uma aresta a again de peso 7 kilos um corte Maressa HG de peso um usando o corte Qual é aquela de menor valor é aresta h g Montezuma Então essa aresta h g com o resumo é chamado de aresta leve tá então esses dois conceitos são utilizados nessa último eu vou passar que a ideia básica Redonda última do prêmio bom então lá a ideia seleciona o verso Inicial por Conjunto S tá então sempre tem começar por um serviço no universo e esse vértice adicionado no conjunto S como sequentemente eu tenho um conjunto pelo menos essa são todos os outros vértices com exceção desse verso que foi adicionado ao conjunto Oeste então o que que eu fiz estabelece um corte inicial a partir desse corte Inicial começa o meu algoritmo Então eu tenho lá encontrar esta leve e j né que cruza esse corte e adiciono essa aresta leve na minha solução também então é aqui de tal que a minha estratégia gulosa então a ideia que eu vou modificar cada interação E se eu vou modificar esse corte a cada interação do algoritmo e vou Identificar qual é a aresta leve naquele momento tô naquele momento eu pego a seresta Leve me adiciona a solução percebe que é uma estratégia simples o que aparentemente não dá certo mas ela funciona tá você vai ver que ela sempre Vai resultar na melhor solução Global né precisar de você ta observando ali o crescimento né da sua solução ao aos poucos né observando as opções locais ela sempre Vai resultar na melhor solução global para uma vez que eu adicionei ela aresta leva o que que eu faço eu vou ter que atualizar meu conjunto o s tá porque eu tenho que estabelecer que essa minha aresta que faz parte da solução e não pode estar usando o corte tá porque ela não seja adicionar novamente a solução então parece que eu faço eu pego Aquele perto né Will J aquele que não pertence ao conjunto S adicional conjunto essa aqui que eu quando eu adicionou esse Vert a conjunturais que eu fiz eu atualizei meu Conjunto S consequentemente usei - s e consequentemente também o corte tá então modifiquei o corte para esse gráfico e se esse conjunto B - s-1 fantasia ou seja tem vértices então ainda tem arestas cruzando o corte tá como é que era essa exclusão corte que eu faço repita o passo 2 Você já está abordagem gulosa né A minha interação gulosa ser o que verificar qual era essa leva nesse outro momento e o seleciona essa essa leve adiciona pra minha solução é isso vai se repetindo até que eu consiga adicionar todos os versos no conjunto S ou o que eu ou em outras palavras e forme uma árvore Tá então vamos colocar uma ilustração contém arquivos conjunto tá Oeste vemos esta solução esta leve no momento então inicia pelo vértice A ele vai ser adicionado o meu Conjunto S tá uma vez coisa nele no conjunto s.
o. v.
