terça-feira, 24 de fevereiro de 2015

Algoritmos gulosos - Problema do planejamento (scheduling)

Olá pessoal, nesse post iremos falar sobre o problema do planejamento (scheduling) utilizando a estratégia gulosa para resolvê-lo.

Primeiramente precisamos saber o que é um algoritmo guloso. Algoritmo guloso/ganancioso (greedy algorithm) é uma técnica de algoritmos para resolver problemas de otimização. A estratégia é escolher a cada passo a solução que parece ser a melhor, ou seja, faz uma escolha ótima local na esperança de que esta escolha leve até a solução ótima global.

Um algoritmo guloso é "míope" pois nunca volta atrás, toma uma decisão sem se preocupar com as consequências, por isso, nem sempre conduz à soluções ótimas globais. Um exemplo de algoritmo que utiliza a estratégia gulosa é o Djikstra.

O problema do troco mínimo é um problema famoso onde se usa a estratégia gulosa. Digamos que tem-se um produto que custa 20 reais e o cliente dar 55 reais. O troco pode ser dado com notas de 20, 15, 10 ou 5, esse troco tem que ser feito com a quantidade mínima de notas.

55 - 20 = 35
35 - 20 = 15
15 - 15 = 0

Mínimo de notas: 3. O troco é dado com duas notas de 20 e uma nota de 15. Na wikipédia tem um exemplo disso: http://en.wikipedia.org/wiki/Greedy_algorithm

Muito fácil de implementar esse problema do troco mínimo não é mesmo? É claro que essa formulação que fiz é uma formulação bem simples, pois no mundo real temos uma quantidade de notas finita, nesse caso o algoritmo guloso poderá não levar a uma solução ótima e poderá nem sequer achar uma solução mesmo ela existindo. Bem, mas isso poderemos discutir em outra oportunidade.

Nesse post vamos resolver um problema de planejamento utilizando algoritmo guloso. Iremos organizar tarefas de forma que o tempo médio que cada tarefa fica no sistema é minimizado.

Imagine um sistema como sendo um caixa de banco e uma tarefa como sendo um cliente. O objetivo é minimizar o tempo que cada cliente espera desde quando ele entra no banco até o momento que termina de ser atendido. Nossa tarefa é minimizar o tempo que cada cliente gasta no sistema.

Chamaremos de "t1" o tempo gasto pelo cliente 1, "t2" o tempo gasto pelo cliente 2 e assim por diante.

t1 = 5
t2 = 10
t3 = 3

Temos algumas ordens:

123 = 5 + (5 + 10) + (5 + 10 + 3) = 38
132 = 5 + (5 + 3) + (5 + 3 + 10) = 31
e assim por diante...

123 significa que o cliente 1 foi atendido primeiro, depois veio o cliente 2 e por último o cliente 3.

A solução ótima é: 312 = 3 + (3 + 5) + (3 + 5 + 10) = 29.

Perceba que é muito simples de entender, a ideia é: o cliente que gasta menos tempo é atendido primeiro. Para resolver é só selecionar a cada passo o cliente que necessita de menos tempo.

Podemos ordenar os clientes em ordem crescente de acordo com os tempos de serviço. Muito simples não é mesmo?

Iremos resolver utilizando C++, mais precisamente a "priority_queue" que implementa uma fila de prioridades. A prioridade será pelo menor tempo de serviço, ou seja, uma heap mínima. 

O código é muito simples, veja:


Quaisquer dúvidas deixem nos comentários. Até a próxima!


Nenhum comentário: