Algoritmo goloso con esempio: cos'è, metodo e approccio

Cos'è un algoritmo goloso?

In Algoritmo avido un insieme di risorse viene suddiviso ricorsivamente in base alla disponibilità massima e immediata di tale risorsa in una determinata fase di esecuzione.

Per risolvere un problema basato sull’approccio avido, ci sono due fasi

  1. Scansione dell'elenco degli elementi
  2. OTTIMIZZAZIONE

Queste fasi sono trattate parallelamente in questo tutorial sull'algoritmo Greedy, sul corso della divisione dell'array.

Per comprendere l'approccio greedy, è necessario avere una conoscenza pratica della ricorsione e del cambio di contesto. Questo ti aiuta a capire come tracciare il codice. Puoi definire il paradigma avido nei termini delle tue affermazioni necessarie e sufficienti.

Due condizioni definiscono il paradigma avido.

  • Ogni soluzione graduale deve strutturare un problema verso la soluzione migliore accettata.
  • È sufficiente che la strutturazione del problema possa arrestarsi in un numero finito di passi avidi.

Continuando la teoria, descriviamo la storia associata all'approccio di ricerca Greedy.

Storia dell'avido Algorithms

Ecco un importante punto di riferimento degli algoritmi greedy:

  • Gli algoritmi greedy furono concettualizzati per molti algoritmi di camminata sul grafico negli anni '1950.
  • Esdger Djikstra ha concettualizzato l'algoritmo per generare spanning tree minimi. Il suo obiettivo era ridurre la durata delle rotte all'interno della capitale olandese, Amsterdam.
  • Nello stesso decennio, Prim e Kruskal realizzarono strategie di ottimizzazione basate sulla minimizzazione dei costi di percorso lungo percorsi ponderati.
  • Negli anni '70, i ricercatori americani Cormen, Rivest e Stein proposero una sottostrutturazione ricorsiva delle soluzioni greedy nel loro classico libro di introduzione agli algoritmi.
  • Il paradigma di ricerca Greedy è stato registrato come un diverso tipo di strategia di ottimizzazione nei registri NIST nel 2005.
  • Fino ad oggi, i protocolli che gestiscono il web, come OSPF (open-shortest-path-first) e molti altri protocolli di commutazione di pacchetti di rete, utilizzano la strategia avida per ridurre al minimo il tempo trascorso su una rete.

Strategie e decisioni avide

La logica nella sua forma più semplice veniva ridotta a “avido” o “non avido”. Queste affermazioni sono state definite dall'approccio adottato per avanzare in ciascuna fase dell'algoritmo.

Ad esempio, l'algoritmo di Djikstra ha utilizzato una strategia greedy stepwise che identifica gli host su Internet calcolando una funzione di costo. Il valore restituito dalla funzione di costo determina se il percorso successivo è "greedy" o "non-greedy".

In breve, un algoritmo cessa di essere avido se in qualsiasi momento fa un passo che non è localmente avido. I problemi dell'avidità si interrompono senza ulteriori possibilità di avidità.

Caratteristiche dell'algoritmo Greedy

Le caratteristiche importanti di un algoritmo Greedy sono:

  • Esiste un elenco ordinato di risorse, con costi o attribuzioni di valore. Questi quantificano i vincoli su un sistema.
  • Prenderai la quantità massima di risorse nel tempo in cui si applica un vincolo.
  • Ad esempio, in un problema di pianificazione delle attività, i costi delle risorse sono espressi in ore e le attività devono essere eseguite in ordine seriale.

Caratteristiche dell'algoritmo Greedy

Perché utilizzare l'approccio goloso?

Ecco i motivi per utilizzare l’approccio goloso:

  • L'approccio avido presenta alcuni compromessi, che potrebbero renderlo adatto all'ottimizzazione.
  • Uno dei motivi principali è trovare immediatamente la soluzione più fattibile. Nel problema di selezione dell'attività (spiegato di seguito), se è possibile svolgere più attività prima di terminare l'attività corrente, queste attività possono essere eseguite nello stesso tempo.
  • Un altro motivo è dividere ricorsivamente un problema in base ad una condizione, senza bisogno di combinare tutte le soluzioni.
  • Nel problema di selezione delle attività, il passaggio di “divisione ricorsiva” si ottiene scansionando un elenco di elementi solo una volta e considerando determinate attività.

Come risolvere il problema della selezione delle attività

Nell'esempio di pianificazione delle attività, è presente un orario di "inizio" e di "fine" per ogni attività. Ogni attività è indicizzata da un numero di riferimento. Ci sono due categorie di attività.

  1. attività considerata: è l'Attività, che è il riferimento da cui viene analizzata la capacità di svolgere più di un'Attività rimanente.
  2. attività rimanenti: attività su uno o più indici precedenti all'attività considerata.

La durata totale indica il costo per lo svolgimento dell'attività. Cioè (fine – inizio) ci dà la durata come costo di un'attività.

Imparerai che la misura avida è il numero di attività rimanenti che puoi svolgere nel tempo di un'attività considerata.

Archistruttura dell’approccio Greedy

PASSO 1) Scansiona l'elenco dei costi delle attività, iniziando con l'indice 0 come indice considerato.

PASSO 2) Quando è possibile completare più attività prima che l'attività in questione termini, si può iniziare a cercare una o più attività rimanenti.

PASSO 3) Se non ci sono più attività rimanenti, l'attività rimanente corrente diventa la successiva attività considerata. Ripetere il passaggio 1 e il passaggio 2, con la nuova attività considerata. Se non sono rimaste attività rimanenti, vai al passaggio 4.

PASSO 4) Restituisce l'unione degli indici considerati. Questi sono gli indici di attività che verranno utilizzati per massimizzare il throughput.

Architecnica dell’Approccio Avido
Architecnica dell’Approccio Avido

Spiegazione del codice

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

#define MAX_ACTIVITIES 12

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. File/classi di intestazione inclusi
  2. Un numero massimo di attività fornite dall'utente.
using namespace std;

class TIME
{
    public:
    int hours;

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

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Lo spazio dei nomi per le operazioni di streaming.
  2. Una definizione di classe per TIME
  3. Un timestamp di un'ora.
  4. Un costruttore predefinito TIME
  5. La variabile oraria.
class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

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

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Una definizione di classe dall'attività
  2. Timestamp che definiscono una durata
  3. Tutti i timestamp sono inizializzati su 0 nel costruttore predefinito
class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Parte 1 della definizione della classe dello scheduler.
  2. L'indice considerato è il punto di partenza per la scansione del file schieramento.
  3. L'indice di inizializzazione viene utilizzato per assegnare timestamp casuali.
  4. Un array di oggetti attività viene allocato dinamicamente utilizzando l'operatore new.
  5. Il puntatore pianificato definisce la posizione base corrente per l'avidità.
Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Il costruttore dello scheduler – parte 2 della definizione della classe dello scheduler.
  2. L'indice considerato definisce l'inizio corrente della scansione corrente.
  3. L’attuale portata dell’avidità non è definita all’inizio.
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);
 }
…
…

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Un ciclo for per inizializzare le ore di inizio e di fine di ciascuna delle attività attualmente pianificate.
  2. Inizializzazione dell'ora di inizio.
  3. Inizializzazione dell'ora di fine sempre dopo o esattamente all'ora di inizio.
  4. Un'istruzione di debug per stampare le durate allocate.
	public:
   		 Activity * activity_select(int);
};

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Parte 4 – l'ultima parte della definizione della classe dello scheduler.
  2. La funzione di selezione dell'attività prende come base un indice del punto di partenza e divide la ricerca avida in sottoproblemi avidi.
Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
… 

Architecnica dell’Approccio Avido

  1. Utilizzando l'operatore di risoluzione dell'ambito (::), viene fornita la definizione della funzione.
  2. L'Indice considerato è l'Indice chiamato per valore. Il greedy_extent è inizializzato solo un indice dopo l'indice considerato.
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++;
    	}
…
...

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. La logica di base: la portata avida è limitata al numero di attività.
  2. Gli orari di inizio dell'Attività corrente vengono controllati come programmabili prima che l'Attività considerata (data dall'indice considerato) finisca.
  3. Finché ciò è possibile, viene stampata un'istruzione di debug opzionale.
  4. Avanza all'indice successivo nell'array di attività
...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. Il condizionale controlla se tutte le attività sono state coperte.
  2. In caso contrario, puoi riavviare il tuo avido con l'indice considerato come punto corrente. Questo è un passaggio ricorsivo che divide avidamente l'affermazione del problema.
  3. Se sì, ritorna al chiamante senza alcuna possibilità di estendere l'avidità.
int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Architecnica dell’Approccio Avido

Spiegazione del codice:

  1. La funzione principale utilizzata per richiamare lo scheduler.
  2. Viene creata un'istanza di un nuovo Scheduler.
  3. La funzione di selezione dell'attività, che restituisce un puntatore di tipo attività, ritorna al chiamante al termine dell'avida ricerca.

Produzione:

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

Limitazioni della tecnica golosa

Non è adatto per problemi Greedy in cui è richiesta una soluzione per ogni sottoproblema come l'ordinamento.

In tali problemi pratici con l'algoritmo Greedy, il metodo Greedy può essere sbagliato; nel peggiore dei casi portano addirittura ad una soluzione non ottimale.

Pertanto lo svantaggio degli algoritmi avidi è che non si sa cosa accadrà dopo l'attuale stato avido.

Di seguito è riportata una descrizione dello svantaggio del metodo Greedy:

Limitazioni della tecnica golosa

Nella scansione greedy mostrata qui come un albero (valore più alto, più alta avidità), uno stato dell'algoritmo al valore: 40, probabilmente prenderà 29 come valore successivo. Inoltre, la sua ricerca termina a 12. Ciò equivale a un valore di 41.

Tuttavia, se l’algoritmo ha preso un percorso non ottimale o ha adottato una strategia di conquista. quindi 25 sarebbe seguito da 40 e il miglioramento complessivo dei costi sarebbe 65, che viene valutato 24 punti in più come decisione non ottimale.

Esempi di goloso Algorithms

La maggior parte degli algoritmi di rete utilizza l'approccio greedy. Ecco un elenco di alcuni esempi di algoritmo Greedy:

  • Algoritmo dell'albero di copertura minimo di Prim
  • Problema del commesso viaggiatore
  • Grafico: colorazione della mappa
  • Algoritmo dell'albero di copertura minimo di Kruskal
  • Algoritmo dell'albero di copertura minimo di Dijkstra
  • Grafico – Copertura del vertice
  • Problema dello zaino
  • Problema di pianificazione del lavoro

Sommario

Per riassumere, l'articolo ha definito il paradigma greedy, ha mostrato come l'ottimizzazione greedy e la ricorsione possano aiutarti a ottenere la soluzione migliore fino a un certo punto. L'algoritmo Greedy è ampiamente utilizzato per la risoluzione dei problemi in molte lingue come algoritmo Greedy Python, C, C#, PHP, Java, ecc. La selezione dell'attività dell'esempio dell'algoritmo Greedy è stata descritta come un problema strategico che potrebbe ottenere il massimo rendimento utilizzando l'approccio greedy. Alla fine, sono stati spiegati i demeriti dell’utilizzo dell’approccio avido.