O que é um algoritmo ganancioso?
No algoritmo Greedy, 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
- Verificando a lista de itens
- Otimização
Esses estágios são cobertos paralelamente neste tutorial de algoritmo Greedy, durante a divisão do array.
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 da busca gananciosa.
Neste tutorial de algoritmo Greedy, você aprenderá:
- História dos algoritmos gananciosos
- Estratégias e decisões gananciosas
- Características da abordagem gananciosa
- Por que usar a abordagem gananciosa?
- Como resolver o problema de seleção de atividades
- Arquitetura da abordagem Greedy
- Desvantagens dos algoritmos gananciosos
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. Ele pretendia 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 gradativa identificando hosts na Internet calculando uma função de custo. O valor retornado pela função de custo determina 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 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.
- Atividade considerada : é a Atividade, que é a referência a partir da qual se analisa a capacidade de realizar mais de uma Atividade restante.
- atividades restantes: atividades em um ou mais índices à frente 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 tornará 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.
Explicação do código
#include#include #include #define MAX_ACTIVITIES 12
Explicação do código:
- Arquivos de cabeçalho / classes incluídos
- 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:
- O namespace para operações de streaming.
- Uma definição de classe para TIME
- Um carimbo de data / hora de hora.
- Um construtor padrão TIME
- A variável de horas.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};
Explicação do código:
- Uma definição de classe da atividade
- Timestamps definindo uma duração
- 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:
- Parte 1 da definição da classe do planejador.
- O índice considerado é o ponto de partida para a varredura da matriz.
- O índice de inicialização é usado para atribuir carimbos de data / hora aleatórios.
- Uma matriz de objetos de atividade é alocada dinamicamente usando o novo operador.
- O ponteiro programado define a localização da base atual para ganância.
Scheduler(){considered_index = 0;scheduled = NULL;… …
Explicação do código:
- O construtor do planejador - parte 2 da definição da classe do planejador.
- O índice considerado define o início atual da varredura atual.
- 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:
- Um loop for para inicializar as horas de início e de término de cada uma das atividades atualmente agendadas.
- Inicialização da hora de início.
- Inicialização da hora de término sempre após ou exatamente na hora de início.
- Uma instrução de depuração para imprimir durações alocadas.
public:Activity * activity_select(int);};
Explicação do código:
- Parte 4 - a última parte da definição da classe do planejador.
- 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;… …
- Usando o operador de resolução de escopo (: :), a definição da função é fornecida.
- 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 < 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:
- A lógica central- A extensão gananciosa é limitada ao número de atividades.
- As horas de início da Atividade atual são verificadas como agendáveis antes que a Atividade considerada (fornecida pelo índice considerado) termine.
- Enquanto isso for possível, uma instrução de depuração opcional é impressa.
- 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:
- As verificações condicionais se todas as atividades foram cobertas.
- 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.
- 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:
- A função principal usada para invocar o planejador.
- Um novo Scheduler é instanciado.
- 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.
Resultado:
START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity: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; na pior das hipóteses, 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 algoritmo 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 aproximação. No final, os deméritos do uso da abordagem gananciosa foram explicados.