Algoritmos gulosos
Uma introdução a estrategia de programação gananciosa
De modo geral, algoritmos gulosos são usados em problemas de otimização onde é interessante realizar um conjunto de melhores soluções locais, possuindo como objetivo obter uma solução ótima global, tomando como base um determinado parâmetro. Os parâmetros que definem o que será a melhor solução durante a iteração irá variar para cada problema.
Podemos então citar algumas das suas principais características:
- As escolhas realizadas são definitivas;
- Não levam em consideração as consequências de suas escolhas;
- Podem fazer cálculos repetitivos.
Podemos ver que essa estrategia nem sempre terá a capacidade de chegar a melhor solução do problema, sendo necessário que coloquemos mais informações nele para conseguirmos chegar a uma solução melhor.
Uma das suas principais vantagens é que são algoritmos simples e de fácil implementação. Uma das principais desvantagens é que eles podem entrar em loop, consequentemente desenvolvendo um caminho infinito.
Para melhor entendermos, tomemos a imagem a seguir como nosso conjunto de dados:
Nosso problema é traçar um caminho de um local X até um local Y. Cada vértice do grafo representa um local e as arestas representam o custo de sair de um local X para Y, sendo o mesmo valor de Y para X. Vamos considerar que nosso algoritmo guloso armazene a informação de onde veio, portanto não poderá fazer uma ação de volta, exemplo: se saiu do vértice 0 para o 1, ele não poderá sair do 1 para o 0.
Em um problema real, tomemos com exemplo que você queira sair de sua casa e ir até um determinado supermercado. Há várias ruas que te levam de maneiras diferentes até esse estabelecimento. A cada vez que você tem que escolher por qual rua seguir, você decide pela rua com menor comprimento, até chegar ao seu destino final. Ou seja, cada iteração significa a ação de escolher a próxima rua que levará até o supermercado. O algoritmo guloso focará então em encontrar a rua mais curta em cada iteração, no final possuindo um conjunto de ruas mais curtas que levam da sua casa até o supermercado.
Agora digamos que sua casa seja o vértice 0 e o supermercado o vértice 8, as arestas são as ruas. O caminho que o algoritmo guloso irá nos mostrar será: 0 →1 →2 →8, possuindo um custo total de 4+8+2=14.
Agora digamos que ainda queremos chegar no supermercado (vértice 8), porém você se mudou e sua casa agora é no vértice 7. O caminho que o algoritmo guloso irá nos apresentar será: 7 →6 →5 →2 →8, possuindo um custo total de 1+2+4+2=9. É maior que o custo que você teria se saísse de sua casa (vértice 7) pegando a rua direto pro supermercado (vértice 8), custaria 7, ou seja, 2 mais que a solução proposta pelo algoritmo, além de possuir mais iterações (escolhas de ruas, curvas, etc).
O algoritmo sempre tenta encontrar a melhor solução local, para no fim obter uma solução que resolva o problema, não necessariamente da melhor forma possível.
Outro exemplo que podemos tomar é o do grafo abaixo e em cada iteração iremos escolher o filho com maior peso.
Se observar bem, o filho de maior peso é 99, porém o grafo chega ao filho de peso 9. Nesse problema o algoritmo guloso não consegue alcançar a melhor solução global.
Esse artigo foi escrito para a disciplina de Tópicos Especiais em Computação XIV, no curso de Bacharelado em Tecnologia da Informação (BTI) da Universidade Federal do Rio Grande do Norte (UFRN), possuindo como professor Leonardo Bezerra. Grupo:
Resoluções de exercícios da plataforma LeetCode sobre esse tema (e outros temas) estarão no repositório leobezerra/leetcode-hero.
