Algoritmo ganancioso com exemplo: o que é, método e abordagem

O que é um algoritmo ganancioso?

A Algoritmo ganancioso Divide recursivamente um conjunto de recursos com base na disponibilidade imediata máxima desse recurso em qualquer etapa da execução.

A resolução de um problema com a abordagem gulosa tem duas etapas:

1. Verificando a lista de itens
2. Operacional

Ambas as etapas são executadas em paralelo, à medida que a matriz de entrada é progressivamente dividida.

Para seguir a abordagem gulosa, um conhecimento prático de recursividade e troca de contexto ajuda você. trace o código. O paradigma guloso pode ser descrito com um par de afirmações necessárias e suficientes.

Duas condições definem o paradigma ganancioso.

• Cada escolha feita passo a passo deve direcionar o problema para a sua solução mais aceitável.
• A estrutura do problema deve parar em um número finito de passos gulosos.

Com a teoria estabelecida, vamos analisar a história por trás da abordagem de busca gulosa.

História do ganancioso Algorithms

Aqui estão os marcos importantes na história dos algoritmos gulosos:

• Os algoritmos gulosos foram inicialmente concebidos para algoritmos de busca em grafos na década de 1950.
• Edsger Dijkstra desenvolveu seu algoritmo de caminho mais curto para encurtar rotas na capital holandesa, Amsterdã.
• Na mesma década, Prim e Kruskal desenvolveram estratégias de otimização que minimizam os custos dos caminhos ao longo de rotas ponderadas para construir árvores geradoras mínimas.
• Na década de 70, os pesquisadores americanos Cormen, Leiserson, Rivest e Stein descreveram a subestruturação recursiva de soluções gulosas em seu clássico. Introduction to Algorithms livro didático.
• O paradigma de busca gulosa foi catalogado como uma estratégia de otimização distinta nos registros do NIST em 2005.
• Até hoje, protocolos da web como o Open Shortest Path First (OSPF) e muitos protocolos de comutação de pacotes usam a estratégia gulosa para minimizar o tempo de trânsito em uma rede.

Estratégias e decisões gananciosas

A lógica se resume a uma escolha binária em cada etapa — “ganancioso” ou “não ganancioso” — com base na direção que o algoritmo toma para avançar.

Por exemplo, o algoritmo de Dijkstra identifica hosts na Internet avaliando uma função de custo a cada passo. O valor retornado pela função de custo determina se o próximo caminho é "ganancioso" ou "não ganancioso".

Resumindo, um algoritmo deixa de ser ganancioso no momento em que realiza uma ação que não é localmente ótima, e os problemas gananciosos param quando nenhuma outra ação gananciosa é possível.

Características do Algoritmo Ganancioso

As características importantes de um algoritmo Greedy são:

• Uma lista ordenada de recursos inclui atribuições de custo ou valor que quantificam as restrições do sistema.
• O algoritmo utiliza a quantidade máxima de recursos dentro do tempo estipulado pela restrição.
• Por exemplo, em um problema de planejamento de atividades, os custos dos recursos são medidos em horas e as atividades devem ser executadas em ordem sequencial.

Por que usar a abordagem gananciosa?

Aqui estão as razões para usar a abordagem gananciosa:

• A abordagem gananciosa apresenta vantagens e desvantagens que a tornam adequada para otimização.
• A razão mais óbvia é produzir uma solução viável imediatamente. No problema de seleção de atividades discutido abaixo, se mais atividades couberem antes da conclusão da atividade atual, elas podem ser agendadas na mesma janela de tempo.
• Outro motivo é que ele divide um problema recursivamente com base em uma condição, sem a necessidade de mesclar subsoluções.
• No problema de seleção de atividades, a etapa de divisão recursiva é realizada percorrendo a lista uma única vez e considerando apenas as atividades elegíveis.

Como resolver o problema de seleção de atividades

No exemplo de planejamento de atividades, cada atividade possui um horário de início e término e é indexada por um número para referência. Existem duas categorias de atividades:

1. Atividade considerada: A atividade de referência a partir da qual se mede a capacidade de realizar mais atividades restantes.
2. Atividades restantes: atividades em um ou mais índices à frente da atividade considerada.

O custo de execução de uma atividade é a sua duração, calculada como (fim – início).

A extensão gulosa é simplesmente o número de atividades restantes que podem ser realizadas dentro do tempo de uma atividade considerada.

Archiarquitetura da abordagem gananciosa

Passo 1) Analise a lista de custos de atividades começando com o índice 0 como o índice considerado.

Passo 2) Quando mais atividades puderem ser concluídas até o término da atividade considerada, procure por essas atividades restantes.

Passo 3) Se não for possível agendar mais atividades, a atividade restante atual torna-se a próxima atividade a ser considerada. Repita os passos 1 e 2 com a nova atividade considerada. Se não houver mais atividades disponíveis, vá para o passo 4.

Passo 4) Retorne a união dos índices considerados — estes são os índices de atividade que maximizam a produtividade.

Archiarquitetura da abordagem gananciosa

Code Explicação

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Explicação do código:

1. Arquivos/classes de cabeçalho incluídos
2. Número máximo de atividades configuráveis ​​pelo usuário.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Explicação do código:

1. Declara o espaço de nomes padrão para operações de streaming.
2. Uma definição de classe para TIME
3. Um carimbo de data/hora de uma hora.
4. Um construtor padrão TIME
5. A variável horas.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Explicação do código:

1. Uma definição de classe para Activity.
2. Registros de data e hora que, juntos, definem uma duração.
3. No construtor padrão, todos os registros de data e hora são inicializados com o valor 0.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Explicação do código:

1. Parte 1 da definição da classe do agendador.
2. `considered_index` é o ponto de partida para a varredura do array.
3. O parâmetro `init_index` é usado para atribuir timestamps aleatórios durante a configuração.
4. Um array de objetos Activity é alocado dinamicamente com o operador new.
5. O ponteiro agendado contém o resultado guloso atual.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Explicação do código:

1. Construtor do Scheduler — parte 2 da definição da classe.
2. O parâmetro `considered_index` marca o início da varredura atual.
3. A extensão do algoritmo guloso não está definida inicialmente.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Explicação do código:

1. Um laço "for" inicializa os horários de início e término de cada atividade agendada.
2. Inicializa a hora de início.
3. Inicializa o horário de término para ser igual ou posterior ao horário de início.
4. Uma instrução de depuração imprime as durações alocadas.

	public:
   		 Activity * activity_select(int);
};

Explicação do código:

1. Parte 4 — a parte final da definição da classe Scheduler.
2. activity_select() recebe um índice inicial como base e divide a busca gulosa em subproblemas.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. O operador de resolução de escopo (::) vincula a definição da função à classe Scheduler.
2. O valor de `considered_index` é passado, e `greedy_extent` é inicializado com o índice imediatamente seguinte.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Explicação do código:

1. A lógica principal — a extensão da busca gananciosa é limitada a MAX_ACTIVITIES.
2. A hora de início da atividade atual é comparada com a hora de término da atividade considerada.
3. Enquanto a condição for mantida, uma mensagem de depuração opcional será impressa.
4. A extensão gulosa avança então para o próximo índice na matriz de atividades.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Explicação do código:

1. A verificação condicional garante que todas as atividades foram cobertas.
2. Caso contrário, o algoritmo reinicia a busca gulosa a partir do índice atual — uma etapa recursiva que divide o problema de forma gulosa.
3. Em caso afirmativo, o controle retorna ao chamador, sem possibilidade de prolongar a ganância.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Explicação do código:

1. A função principal invoca o Agendador.
2. Um novo objeto Scheduler é instanciado.
3. A função activity_select() retorna um ponteiro Activity para o chamador assim que a busca gulosa terminar.

Saída:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Limitações da técnica gananciosa

A abordagem gulosa não é adequada para problemas que exigem uma solução ótima para cada subproblema, como a ordenação.

Nesses casos, o método guloso pode estar errado — no pior dos casos, produz uma solução não ótima.

A principal desvantagem dos algoritmos gulosos é que eles escolhem sem saber o que está por vir a partir do estado guloso atual.

O diagrama abaixo ilustra essa desvantagem do método guloso.

Na busca gulosa mostrada aqui como uma árvore (valor mais alto significa maior ganância), um algoritmo no valor 40 escolheria 29 em seguida, depois terminaria em 12, para um total de 41.

Em contrapartida, uma estratégia de dividir para conquistar seguiria 25 com 40, totalizando 65, o que representa 24 pontos a mais do que a escolha localmente gananciosa.

Exemplos de ganancioso Algorithms

A maioria dos algoritmos de redes se baseia em uma abordagem gulosa. Exemplos comuns de algoritmos gulosos incluem:

• Algoritmo da Árvore Geradora Mínima de Prim
• Problema do Caixeiro Viajante (aproximado)
• Mapa gráfico para colorir
• Algoritmo da Árvore Geradora Mínima de Kruskal
• Algoritmo de caminho mais curto de Dijkstra
• Cobertura de vértices do grafo
• Problema da mochila
• Sequenciamento de tarefas com prazos

Perguntas Frequentes