Algoritmo Greedy com Exemplos: Método e Abordagem Greedy

O que é um algoritmo ganancioso?

No Algoritmo ganancioso um conjunto de recursos é dividido recursivamente com base na disponibilidade máxima e imediata desse recurso em qualquer estágio de execução.

Para resolver um problema com base na abordagem gananciosa, existem duas etapas

  1. Verificando a lista de itens
  2. Otimização

Esses estágios são cobertos paralelamente neste tutorial de algoritmo Greedy, no decorrer da divisão da matriz.

Para entender a abordagem gananciosa, você precisará ter um 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 se a estruturação do problema pode parar em um número finito de etapas gananciosas.

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

Neste tutorial de algoritmo Greedy, você aprenderá:

História dos algoritmos gananciosos

Aqui está um marco importante de algoritmos gananciosos:

  • Algoritmos gananciosos foram conceituados para muitos algoritmos de caminhada de 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 de custos de caminhos 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 livro de introdução clássica 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 reduzida a 'gananciosa' ou 'não gananciosa'. Essas declarações foram definidas pela abordagem adotada para avançar em cada etapa do algoritmo.

Por exemplo, o algoritmo de Djikstra utilizou uma estratégia gananciosa gradual identificando 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 suma, um algoritmo deixa de ser ganancioso se, em qualquer estágio, ele dá um passo que não é ganancioso localmente. Os problemas gananciosos param sem nenhum escopo adicional de ganância.

Características da abordagem gananciosa

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

  • Existe uma lista ordenada de recursos, com custos ou atribuições de valor. Estes quantificam as restrições em um sistema.
  • Você obterá a quantidade máxima de recursos no momento em que uma restrição for aplicada.
  • Por exemplo, em um problema de agendamento de atividades, os custos dos recursos são em horas e as atividades precisam ser realizadas 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 desvantagens, que podem torná-la adequada para otimização.
  • Um motivo importante é alcançar a solução mais viável imediatamente. No problema de seleção de atividades (Explicado abaixo), se mais atividades podem ser feitas antes de terminar a atividade atual, essas atividades podem ser realizadas no mesmo tempo.
  • Outra razão é dividir um problema recursivamente com base em uma condição, sem a necessidade de combinar todas as soluções.
  • No problema de seleção de atividades, a etapa de 'divisão recursiva' é alcançada escaneando uma lista de itens apenas uma vez e considerando certas atividades.

Como resolver o problema de seleção de atividades

No exemplo de agendamento de atividades, há um tempo 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 se analisa a capacidade de realizar mais de uma Atividade restante.
  2. atividades restantes: atividades em um ou mais índices antes da atividade considerada.

A duração total fornece o custo de execução da atividade. Ou seja, (término - início) 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 durante uma atividade considerada.

Arquitetura da abordagem Greedy

PASSO 1)

Examine 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 momento, a atividade considerada termina, comece a procurar por uma ou mais atividades restantes.

ETAPA 3)

Se não houver mais atividades restantes, a atividade restante atual se torna a próxima atividade considerada. Repita as etapas 1 e 2, com a nova atividade considerada. Se não houver atividades restantes, vá para a etapa 4.

PASSO 4 )

Retorna a união dos índices considerados. Esses são os índices de atividade que serão usados ​​para maximizar o rendimento.

Arquitetura da abordagem gananciosa



Explicação do código

 #include #include #include #define MAX_ACTIVITIES 12 

Explicação do código:

  1. Arquivos de cabeçalho / classes 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 hora.
  4. Um construtor padrão TIME
  5. Variável de 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. Timestamps 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 planejador.
  2. O Índice considerado é o ponto de partida para a varredura da matriz.
  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 novo operador.
  5. O ponteiro programado define a localização da base atual para ganância.
 Scheduler() { considered_index = 0; scheduled = NULL; ... ... 

Explicação do código:

  1. O construtor do planejador - parte 2 da definição da classe do planejador.
  2. O índice considerado define o início atual da varredura atual.
  3. A extensão gananciosa atual é indefinida no início.
 for(init_index = 0; init_index 

Explicação do código:

  1. Um loop for para inicializar as horas de início e de 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 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 planejador.
  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. O greedy_extent é inicializado apenas um índice após o índice considerado.
 Activity * Scheduler :: activity_select(int considered_index) { while( (greedy_extent current_activities[greedy_extent]).start.hours current_activities[considered_index]).finish.hours )) { printf('
Schedule start:%d 
finish%d
 activity:%d
', (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 agendáveis ​​antes que a Atividade considerada (fornecida pelo índice considerado) termine.
  3. Enquanto isso for possível, uma instrução de depuração opcional é impressa.
  4. Avance 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. As verificações condicionais se todas as atividades foram cobertas.
  2. Caso contrário, você pode reiniciar seu guloso com o Índice considerado como o ponto atual. Esta é uma etapa recursiva que divide avidamente a definição do problema.
  3. Se sim, ele retorna ao chamador sem espaço para 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 planejador.
  2. Um novo Scheduler é instanciado.
  3. A função de seleção de atividade, que retorna um ponteiro do tipo activity, 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 

Desvantagens dos algoritmos gananciosos

Não é adequado para problemas Greedy em que uma solução é necessária para cada subproblema, como classificação.

Em tais problemas de prática de algoritmo Greedy, o método Greedy pode estar errado; no pior caso, até mesmo levar a uma solução não ideal.

Portanto, a desvantagem dos algoritmos gananciosos é não saber o que está à frente do estado ganancioso atual.

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

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

No entanto, se o algoritmo tomou um caminho abaixo do ideal ou adotou uma estratégia de conquista. então, 25 seria seguido por 40, e a melhoria geral do custo seria de 65, que é avaliado em 24 pontos a mais como uma decisão abaixo do ideal.

Exemplos de algoritmos gananciosos

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

  • Algoritmo de árvore de expansão mínima de Prim
  • Problema do caixeiro viajante
  • Gráfico - Colorir Mapa
  • Algoritmo de árvore de abrangência mínima de Kruskal
  • Algoritmo de árvore de expansão mínima de Dijkstra
  • Gráfico - Capa do Vértice
  • Problema da mochila
  • Problema de programação de trabalho

Resumo:

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