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

Para entender a abordagem gananciosa, você precisará ter conhecimento prático de recursão e troca de contexto. Isso ajuda você a entender como rastrear o código. Você pode definir o paradigma ganancioso em termos de suas próprias declarações necessárias e suficientes.

Duas condições definem o paradigma ganancioso.

• Cada solução gradual deve estruturar um problema em direção à sua solução mais aceita.
• É suficiente que a estruturação do problema possa ser interrompida num número finito de passos gananciosos.

Continuando a teorização, vamos descrever a história associada à abordagem da busca gananciosa.

História do ganancioso Algorithms

Aqui está um marco importante de algoritmos gananciosos:

• Algoritmos gananciosos foram conceituados para muitos algoritmos de caminhada em grafos na década de 1950.
• Esdger Djikstra conceituou o algoritmo para gerar árvores geradoras mínimas. Seu objetivo era encurtar a extensão das rotas dentro da capital holandesa, Amsterdã.
• Na mesma década, Prim e Kruskal alcançaram estratégias de otimização baseadas na minimização dos custos de trajeto ao longo de rotas pesadas.
• Nos anos 70, os pesquisadores americanos Cormen, Rivest e Stein propuseram uma subestruturação recursiva de soluções gananciosas em seu clássico livro de introdução aos algoritmos.
• O paradigma Greedy search foi registrado como um tipo diferente de estratégia de otimização nos registros do NIST em 2005.
• Até o momento, os protocolos que executam a web, como o open-shortest-path-first (OSPF) e muitos outros protocolos de comutação de pacotes de rede, usam a estratégia gananciosa para minimizar o tempo gasto em uma rede.

Estratégias e decisões gananciosas

A lógica em sua forma mais fácil foi resumida em “ganancioso” ou “não ganancioso”. Essas afirmações foram definidas pela abordagem adotada para avançar em cada etapa do algoritmo.

Por exemplo, o algoritmo de Djikstra utilizou uma estratégia gradual e gananciosa para identificar hosts na Internet calculando uma função de custo. O valor retornado pela função de custo determinou se o próximo caminho é “ganancioso” ou “não ganancioso”.

Em resumo, um algoritmo deixa de ser ganancioso se em qualquer estágio ele der um passo que não seja localmente ganancioso. Os problemas dos gananciosos cessam sem qualquer escopo de ganância.

Características do Algoritmo Ganancioso

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

• Existe uma lista ordenada de recursos, com custos ou atribuições de valor. Eles quantificam as restrições em um sistema.
• Você utilizará a quantidade máxima de recursos no tempo em que uma restrição se aplicar.
• Por exemplo, num problema de agendamento de atividades, os custos dos recursos estão em horas e as atividades precisam ser executadas em ordem serial.

Por que usar a abordagem gananciosa?

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

• A abordagem gananciosa tem algumas vantagens e desvantagens, que podem torná-la adequada para otimização.
• Uma razão importante é alcançar imediatamente a solução mais viável. No problema de seleção de atividades (explicado abaixo), se mais atividades puderem ser realizadas antes de terminar a atividade atual, essas atividades poderão ser realizadas no mesmo tempo.
• Outro motivo é dividir um problema recursivamente com base em uma condição, sem necessidade de combinar todas as soluções.
• No problema de seleção de atividades, a etapa de “divisão recursiva” é alcançada examinando uma lista de itens apenas uma vez e considerando determinadas atividades.

Como resolver o problema de seleção de atividades

No exemplo de agendamento de atividades, há um horário de “início” e “término” para cada atividade. Cada atividade é indexada por um número para referência. Existem duas categorias de atividades.

1. atividade considerada: é a Atividade, que é a referência a partir da qual é analisada a capacidade de realizar mais de uma Atividade restante.
2. atividades restantes: atividades em um ou mais índices à frente da atividade considerada.

A duração total dá o custo de execução da atividade. Isto é (terminar – iniciar) nos dá a duração como o custo de uma atividade.

Você aprenderá que a extensão gananciosa é o número de atividades restantes que você pode realizar no tempo de uma atividade considerada.

Archiarquitetura da abordagem gananciosa

PASSO 1) Digitalize a lista de custos da atividade, começando com o índice 0 como o Índice considerado.

PASSO 2) Quando mais atividades puderem ser concluídas até o momento em que a atividade considerada terminar, comece a procurar por uma ou mais atividades restantes.

PASSO 3) Se não houver mais atividades restantes, a atividade restante atual se tornará a próxima atividade considerada. Repita o passo 1 e o passo 2, com a nova atividade considerada. Se não houver mais atividades restantes, vá para a etapa 4.

PASSO 4 ) Retorne a união dos índices considerados. Estes são os índices de atividade que serão usados ​​para maximizar o rendimento.

Explicação do código

#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. Um número máximo de atividades fornecidas pelo usuário.

using namespace std;

class TIME
{
    public:
    int hours;

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

Explicação do código:

1. O namespace 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 da atividade
2. Carimbos de data e hora definindo uma duração
3. Todos os carimbos de data/hora são inicializados com 0 no construtor padrão

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. O Índice Considerado é o ponto de partida para a digitalização do ordem.
3. O índice de inicialização é usado para atribuir carimbos de data/hora aleatórios.
4. Uma matriz de objetos de atividade é alocada dinamicamente usando o operador new.
5. O ponteiro programado define a localização base atual da ganância.

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

Explicação do código:

1. O construtor do agendador – parte 2 da definição da classe do agendador.
2. O índice considerado define o início atual da varredura atual.
3. A atual extensão gananciosa é indefinida no início.

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);
 }
…
…

Explicação do código:

1. Um loop for para inicializar os horários de início e término de cada uma das atividades atualmente agendadas.
2. Inicialização da hora de início.
3. Inicialização da hora de término sempre após ou exatamente na hora de início.
4. Uma instrução de depuração para imprimir as durações alocadas.

	public:
   		 Activity * activity_select(int);
};

Explicação do código:

1. Parte 4 – a última parte da definição da classe do escalonador.
2. A função de seleção de atividade toma um índice de ponto de partida como base e divide a busca gananciosa em subproblemas gananciosos.

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

1. Usando o operador de resolução de escopo (::), a definição da função é fornecida.
2. O Índice considerado é o Índice denominado por valor. Ogreey_extent é inicializado apenas um índice após o Índice considerado.

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++;
    	}
…
...

Explicação do código:

1. A lógica central – A extensão gananciosa é limitada ao número de atividades.
2. As horas de início da Atividade atual são verificadas como programáveis ​​antes que a Atividade considerada (dada pelo índice considerado) termine.
3. Contanto que isso seja possível, uma instrução de depuração opcional será impressa.
4. Avançar 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 condicional verifica se todas as atividades foram cobertas.
2. Caso contrário, você pode reiniciar seu ganancioso com o Índice considerado como ponto atual. Esta é uma etapa recursiva que divide avidamente a definição do problema.
3. Se sim, ele retorna ao chamador sem possibilidade de estender 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 usada para invocar o agendador.
2. Um novo Agendador é instanciado.
3. A função de seleção de atividade, que retorna um ponteiro do tipo atividade, volta ao chamador após o término da busca gananciosa.

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

Não é adequado para problemas gananciosos, onde é necessária uma solução para cada subproblema, como classificação.

Em tais problemas práticos de algoritmo Greedy, o método Greedy pode estar errado; no pior dos casos, conduzirá mesmo a uma solução não óptima.

Portanto, a desvantagem dos algoritmos gananciosos é não saber o que está por vir em relação ao estado ganancioso atual.

Abaixo está uma descrição da desvantagem do método Ganancioso:

Na varredura gananciosa mostrada aqui como uma árvore (valor mais alto, maior ganância), um estado de algoritmo no valor: 40 provavelmente assumirá 29 como o próximo valor. Além disso, sua missão termina em 12. Isso equivale a um valor de 41.

Porém, se o algoritmo seguiu um caminho abaixo do ideal ou adotou uma estratégia de conquista. então, 25 seriam seguidos por 40, e a melhoria geral dos custos seria de 65, o que é avaliado 24 pontos a mais como uma decisão abaixo do ideal.

Exemplos de ganancioso Algorithms

A maioria dos algoritmos de rede usa a abordagem gananciosa. Aqui está uma lista de alguns exemplos de algoritmos gananciosos:

• Algoritmo de árvore geradora mínima de Prim
• Problema do Vendedor Viajante
• Gráfico – Coloração do Mapa
• Algoritmo de Árvore Geradora Mínima de Kruskal
• Algoritmo de árvore geradora mínima de Dijkstra
• Gráfico - Cobertura de vértice
• Problema da mochila
• Problema de agendamento de trabalho

Resumo

Para resumir, o artigo definiu o paradigma ganancioso, mostrou como a otimização e a recursão gananciosas podem ajudá-lo a obter a melhor solução até certo ponto. O algoritmo Greedy é amplamente utilizado para solução de problemas em muitas linguagens como algoritmo Greedy Python, C, C#, PHP, Java, etc. O exemplo de seleção de atividades do algoritmo Greedy foi descrito como um problema estratégico que poderia atingir o rendimento máximo usando a abordagem gananciosa. Ao final, foram explicados os deméritos do uso da abordagem gananciosa.