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

Cos'è un algoritmo goloso?

A Algoritmo avido Divide ricorsivamente un insieme di risorse in base alla massima disponibilità immediata di tale risorsa in qualsiasi fase dell'esecuzione.

La risoluzione di un problema con l'approccio greedy si articola in due fasi:

1. Scansione dell'elenco degli elementi
2. OTTIMIZZAZIONE

Entrambe le fasi vengono eseguite in parallelo, man mano che l'array di input viene progressivamente suddiviso.

Per seguire l'approccio greedy, una conoscenza pratica della ricorsione e del cambio di contesto ti aiuta trace il codice. Il paradigma greedy può essere descritto con una coppia di affermazioni necessarie e sufficienti.

Due condizioni definiscono il paradigma avido.

• Ogni scelta graduale deve indirizzare il problema verso la soluzione più accettabile.
• La struttura del problema deve arrestarsi dopo un numero finito di passaggi greedy.

Ora che abbiamo gettato le basi teoriche, esaminiamo la storia dell'approccio di ricerca greedy.

Storia dell'avido Algorithms

Ecco le tappe fondamentali nella storia degli algoritmi greedy:

• Gli algoritmi greedy furono concettualizzati per la prima volta negli anni '1950 per gli algoritmi di attraversamento dei grafi.
• Edsger Dijkstra ha sviluppato il suo algoritmo per il percorso più breve al fine di accorciare gli itinerari nella capitale olandese, Amsterdam.
• Nello stesso decennio, Prim e Kruskal hanno sviluppato strategie di ottimizzazione che minimizzano i costi del percorso lungo itinerari ponderati per costruire alberi di copertura minimi.
• Negli anni '70, i ricercatori americani Cormen, Leiserson, Rivest e Stein descrissero la sottostrutturazione ricorsiva delle soluzioni greedy nel loro classico Introduction to Algorithms manuale.
• Il paradigma della ricerca greedy è stato catalogato come una strategia di ottimizzazione distinta nei registri del NIST nel 2005.
• Ancora oggi, protocolli web come Open Shortest Path First (OSPF) e molti protocolli di commutazione di pacchetto utilizzano la strategia greedy per minimizzare il tempo di transito su una rete.

Strategie e decisioni avide

La logica si riduce a una scelta binaria in ogni fase: "avido" o "non avido", in base alla direzione che l'algoritmo prende per avanzare.

Ad esempio, l'algoritmo di Dijkstra identifica gli host su Internet valutando una funzione di costo a ogni passaggio. Il valore restituito dalla funzione di costo determina se il percorso successivo è "avido" o "non avido".

In breve, un algoritmo smette di essere avido nel momento in cui compie un passo che non è localmente ottimale, e i problemi avidi si arrestano quando non è più possibile compiere ulteriori passi avidi.

Caratteristiche dell'algoritmo Greedy

Le caratteristiche importanti di un algoritmo Greedy sono:

• Un elenco ordinato di risorse contiene attribuzioni di costo o di valore che quantificano i vincoli sul sistema.
• L'algoritmo preleva la massima quantità di risorse entro il tempo imposto dal vincolo.
• Ad esempio, in un problema di pianificazione delle attività, i costi delle risorse sono misurati in ore e le attività devono essere eseguite in ordine sequenziale.

Perché utilizzare l'approccio avido?

Ecco i motivi per utilizzare l’approccio goloso:

• L'approccio greedy presenta dei compromessi che lo rendono particolarmente adatto all'ottimizzazione.
• La ragione più ovvia è quella di produrre immediatamente una soluzione fattibile. Nel problema di selezione delle attività discusso di seguito, se ci sono altre attività che si adattano prima che l'attività corrente termini, possono essere programmate nella stessa finestra temporale.
• Un altro motivo è che suddivide un problema in modo ricorsivo in base a una condizione, senza bisogno di unire le sottosoluzioni.
• Nel problema della selezione delle attività, la fase di divisione ricorsiva si realizza scorrendo l'elenco una sola volta e considerando solo le attività idonee.

Come risolvere il problema della selezione delle attività

Nell'esempio di pianificazione delle attività, ogni attività ha un orario di inizio e di fine ed è identificata da un numero. Esistono due categorie di attività:

1. Attività considerata: l'attività di riferimento rispetto alla quale viene misurata la capacità di inserire ulteriori attività rimanenti.
2. Attività rimanenti: attività su uno o più indici precedenti all'attività considerata.

Il costo di un'attività è la sua durata, calcolata come (fine – inizio).

L'estensione greedy è semplicemente il numero di attività rimanenti che possono essere eseguite entro il tempo di un'attività considerata.

Architecnica dell’Approccio Avido

Passo 1) Esamina l'elenco dei costi delle attività a partire dall'indice 0, considerandolo come indice di riferimento.

Passo 2) Se, al termine dell'attività in questione, è possibile completare più attività, cerca quelle rimanenti.

Passo 3) Se non è possibile programmare altre attività, l'attività rimanente al momento diventa la successiva da considerare. Ripetere i passaggi 1 e 2 con la nuova attività da considerare. Se non rimangono attività, passare al passaggio 4.

Passo 4) Restituisci l'unione degli indici considerati: questi sono gli indici di attività che massimizzano la produttività.

Architecnica dell’Approccio Avido

Code Spiegazione

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

#define MAX_ACTIVITIES 12

Spiegazione del codice:

1. File/classi di intestazione inclusi
2. Il numero massimo di attività configurabili dall'utente.

using namespace std;

class TIME
{
    public:
    int hours;

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

Spiegazione del codice:

1. Dichiara lo spazio dei nomi standard 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();
    }
};

Spiegazione del codice:

1. Definizione di una classe per Activity.
2. Timestamp che, nel loro insieme, definiscono una durata.
3. Nel costruttore predefinito, tutti i timestamp vengono inizializzati a 0.

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

Spiegazione del codice:

1. Parte 1 della definizione della classe dello scheduler.
2. considered_index è il punto di partenza per la scansione dell'array.
3. init_index viene utilizzato per assegnare timestamp casuali durante la fase di configurazione.
4. Con il nuovo operatore viene allocato dinamicamente un array di oggetti Activity.
5. Il puntatore programmato contiene il risultato greedy corrente.

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

Spiegazione del codice:

1. Il costruttore dello Scheduler: seconda parte della definizione della classe.
2. considered_index indica l'inizio della scansione corrente.
3. L'estensione dell'algoritmo greedy 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);
 }
&#8230;
&#8230;

Spiegazione del codice:

1. Un ciclo for inizializza l'ora di inizio e di fine di ogni attività programmata.
2. Inizializza l'ora di inizio.
3. Imposta l'ora di fine in modo che sia uguale o successiva all'ora di inizio.
4. Un'istruzione di debug stampa le durate allocate.

	public:
   		 Activity * activity_select(int);
};

Spiegazione del codice:

1. Parte 4 — la parte finale della definizione della classe Scheduler.
2. La funzione activity_select() prende un indice iniziale come base e divide la ricerca greedy in sottoproblemi.

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

1. L'operatore di risoluzione dell'ambito (::) collega la definizione della funzione alla classe Scheduler.
2. considered_index viene passato per valore e greedy_extent viene inizializzato all'indice immediatamente successivo.

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;
...

Spiegazione del codice:

1. La logica di base è che l'estensione greedy è limitata a MAX_ACTIVITIES.
2. L'ora di inizio dell'attività corrente viene confrontata con l'ora di fine dell'attività considerata.
3. Fintanto che la condizione è soddisfatta, viene stampato un messaggio di debug facoltativo.
4. L'estensione greedy avanza quindi all'indice successivo nell'array di attività.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Spiegazione del codice:

1. La condizione verifica se tutte le attività sono state coperte.
2. Altrimenti, l'algoritmo riavvia la ricerca avida dall'indice corrente: un passaggio ricorsivo che suddivide il problema in modo avido.
3. In caso affermativo, il controllo torna al chiamante senza 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;
}

Spiegazione del codice:

1. La funzione principale richiama lo Scheduler.
2. Viene creata una nuova istanza dell'oggetto Scheduler.
3. La funzione activity_select() restituisce un puntatore Activity al chiamante una volta terminata la ricerca greedy.

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

L'approccio greedy non è adatto a problemi che richiedono una soluzione ottimale per ogni sottoproblema, come ad esempio l'ordinamento.

In questi casi il metodo greedy può essere errato: nel peggiore dei casi produce una soluzione non ottimale.

Il principale svantaggio degli algoritmi greedy è che prendono decisioni senza sapere cosa ci aspetta dopo l'attuale stato greedy.

Il diagramma sottostante illustra questo svantaggio del metodo greedy.

Nella scansione greedy mostrata qui come un albero (un valore più alto indica una maggiore avidità), un algoritmo con valore 40 sceglierebbe 29 successivamente, per poi terminare a 12, per un totale di 41.

Al contrario, una strategia dividi et impera seguirebbe 25 con 40 per un totale di 65, che è 24 punti superiore alla scelta localmente avida.

Esempi di goloso Algorithms

La maggior parte degli algoritmi di rete si basa su un approccio greedy. Esempi comuni di algoritmi greedy includono:

• Algoritmo dell'albero di copertura minimo di Prim
• Problema del commesso viaggiatore (approssimato)
• Colorazione di mappe grafiche
• Algoritmo dell'albero di copertura minimo di Kruskal
• Algoritmo del percorso più breve di Dijkstra
• Copertura dei vertici del grafo
• Problema dello zaino
• Sequenziamento delle attività con scadenze

DOMANDE FREQUENTI