Cos'è un algoritmo avido?
In Greedy Algorithm un insieme di risorse viene suddiviso ricorsivamente in base alla disponibilità massima e immediata di quella risorsa in una determinata fase di esecuzione.
Per risolvere un problema basato sull'approccio avido, ci sono due fasi
- Scansione dell'elenco di elementi
- Ottimizzazione
Queste fasi sono coperte parallelamente in questo tutorial sull'algoritmo Greedy, nel corso della divisione dell'array.
Per comprendere l'approccio avido, è necessario avere una conoscenza pratica della ricorsione e del cambio di contesto. Questo ti aiuta a capire come rintracciare il codice. Puoi definire il paradigma avido in termini di affermazioni necessarie e sufficienti.
Due condizioni definiscono il paradigma avido.
- Ogni soluzione graduale deve strutturare un problema verso la sua soluzione più accettata.
- È sufficiente che la strutturazione del problema possa arrestarsi in un numero finito di passi avidi.
Con la teorizzazione continuata, descriviamo la storia associata all'approccio di ricerca Greedy.
In questo tutorial sull'algoritmo Greedy imparerai:
- Storia degli algoritmi avidi
- Strategie e decisioni avide
- Caratteristiche dell'approccio avido
- Perché utilizzare l'approccio avido?
- Come risolvere il problema di selezione delle attività
- Architettura dell'approccio avido
- Svantaggi degli algoritmi avidi
Storia degli algoritmi avidi
Ecco un importante punto di riferimento degli algoritmi avidi:
- Gli algoritmi avidi sono stati concettualizzati per molti algoritmi di camminata sui grafi negli anni '50.
- Esdger Djikstra ha concettualizzato l'algoritmo per generare spanning tree minimi. Mirava ad accorciare la durata delle rotte all'interno della capitale olandese, Amsterdam.
- Nello stesso decennio, Prim e Kruskal hanno realizzato strategie di ottimizzazione basate sulla riduzione al minimo dei costi di percorso lungo percorsi pesati.
- Negli anni '70, i ricercatori americani, Cormen, Rivest e Stein hanno proposto una sottostruttura ricorsiva di soluzioni avide nella loro classica introduzione al libro degli algoritmi.
- Il paradigma di ricerca Greedy è stato registrato come un diverso tipo di strategia di ottimizzazione nei record NIST nel 2005.
- Fino ad oggi, i protocolli che eseguono il Web, come l'OSPF (open-shortest-path-first) e molti altri protocolli di commutazione di pacchetto 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 era 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 avida graduale per identificare gli host su Internet calcolando una funzione di costo. Il valore restituito dalla funzione di costo determina se il percorso successivo è "avido" o "non avido".
In breve, un algoritmo cessa di essere avido se in qualsiasi momento compie un passo che non sia avido a livello locale. I problemi degli avidi si fermano senza ulteriori margini di avidità.
Caratteristiche dell'approccio avido
Le caratteristiche importanti di un algoritmo del metodo Greedy sono:
- C'è 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.
Perché utilizzare l'approccio avido?
Ecco i motivi per utilizzare l'approccio avido:
- L'approccio avido ha alcuni compromessi, che possono renderlo adatto per l'ottimizzazione.
- Uno dei motivi principali è ottenere 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, è possibile eseguire queste attività nello stesso tempo.
- Un altro motivo è dividere un problema ricorsivamente in base a una condizione, senza la necessità di combinare tutte le soluzioni.
- Nel problema di selezione delle attività, il passaggio di "divisione ricorsiva" si ottiene scansionando un elenco di elementi una sola volta e considerando determinate attività.
Come risolvere il problema di selezione delle attività
Nell'esempio di pianificazione delle attività, c'è un tempo di "inizio" e "fine" per ogni attività. Ogni attività è indicizzata da un numero per riferimento. Esistono due categorie di attività.
- attività considerata : è l'Attività, che è il riferimento da cui si analizza la capacità di fare più di una Attività rimanente.
- attività rimanenti: attività a uno o più indici in anticipo rispetto all'attività considerata.
La durata totale indica il costo di esecuzione dell'attività. Cioè (fine - inizio) ci dà la durata come il costo di un'attività.
Imparerai che la misura avida è il numero di attività rimanenti che puoi svolgere nel tempo di un'attività considerata.
Architettura dell'approccio avido
PASSO 1)
Scansiona l'elenco dei costi dell'attività, iniziando con l'indice 0 come Indice considerato.
PASSO 2)
Quando più attività possono essere terminate entro il tempo, l'attività considerata termina, iniziare a cercare una o più attività rimanenti.
FASE 3)
Se non ci sono più attività rimanenti, l'attività rimanente corrente diventa la successiva attività considerata. Ripetere i passaggi 1 e 2, con la nuova attività considerata. Se non sono rimaste attività rimanenti, andare al passaggio 4.
FASE 4)
Restituisce l'unione degli indici considerati. Questi sono gli indici di attività che verranno utilizzati per massimizzare la produttività.
Spiegazione del codice
#include#include #include #define MAX_ACTIVITIES 12
Spiegazione del codice:
- File / classi di intestazione inclusi
- Un numero massimo di attività fornite dall'utente.
using namespace std;class TIME{public:int hours;public: TIME(){hours = 0;}};
Spiegazione del codice:
- Lo spazio dei nomi per le operazioni di streaming.
- Una definizione di classe per TIME
- Un timestamp di un'ora.
- Un costruttore predefinito TIME
- La variabile delle ore.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};
Spiegazione del codice:
- Una definizione di classe dall'attività
- Timestamp che definiscono una durata
- Tutti i timestamp vengono inizializzati su 0 nel costruttore predefinito
class Scheduler{public:int considered_index,init_index;Activity *current_activities = new Activity[MAX_ACTIVITIES];Activity *scheduled;
Spiegazione del codice:
- Parte 1 della definizione della classe scheduler.
- Considered Index è il punto di partenza per la scansione dell'array.
- L'indice di inizializzazione viene utilizzato per assegnare timestamp casuali.
- Un array di oggetti attività viene allocato dinamicamente utilizzando il nuovo operatore.
- Il puntatore programmato definisce la posizione di base corrente per l'avidità.
Scheduler(){considered_index = 0;scheduled = NULL;… …
Spiegazione del codice:
- Il costruttore dello scheduler - parte 2 della definizione della classe dello scheduler.
- L'indice considerato definisce l'inizio corrente della scansione corrente.
- L'attuale dimensione avida è indefinita 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);}… …
Spiegazione del codice:
- Un ciclo for per inizializzare le ore di inizio e di fine di ciascuna delle attività attualmente pianificate.
- Inizializzazione dell'ora di inizio.
- Inizializzazione dell'ora di fine sempre dopo o esattamente all'ora di inizio.
- Un'istruzione di debug per stampare le durate assegnate.
public:Activity * activity_select(int);};
Spiegazione del codice:
- Parte 4: l'ultima parte della definizione della classe dello scheduler.
- La funzione di selezione dell'attività prende un indice del punto di partenza come base e divide la ricerca avida in problemi secondari avidi.
Activity * Scheduler :: activity_select(int considered_index){this->considered_index = considered_index;int greedy_extent = this->considered_index + 1;… …
- Utilizzando l'operatore di risoluzione dell'ambito (: :), viene fornita la definizione della funzione.
- L'Indice considerato è l'Indice chiamato per valore. Il greedy_extent è il solo indice inizializzato 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++;}… …
Spiegazione del codice:
- La logica di base: l'estensione avida è limitata al numero di attività.
- Le ore di inizio dell'attività corrente sono verificate come programmabili prima che l'attività considerata (data dall'indice considerato) finisca.
- Finché è possibile, viene stampata un'istruzione di debug opzionale.
- Passa all'indice successivo sull'array di attività
… if ( greedy_extent <= MAX_ACTIVITIES ){return activity_select(greedy_extent);}else{return NULL;}}
Spiegazione del codice:
- Il condizionale controlla se tutte le attività sono state coperte.
- 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.
- In caso affermativo, 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:
- La funzione principale utilizzata per richiamare lo scheduler.
- Viene creata un'istanza di un nuovo Scheduler.
- La funzione di selezione dell'attività, che restituisce un puntatore di tipo activity, torna al chiamante dopo che la ricerca avida è terminata.
Produzione:
START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5
Svantaggi degli algoritmi avidi
Non è adatto per problemi Greedy in cui è richiesta una soluzione per ogni sottoproblema come l'ordinamento.
In tali problemi di pratica dell'algoritmo Greedy, il metodo Greedy può essere sbagliato; nel peggiore dei casi portano anche a una soluzione non ottimale.
Pertanto lo svantaggio degli algoritmi avidi sta nell'usare il non sapere cosa c'è davanti all'attuale stato avido.
Di seguito è una rappresentazione dello svantaggio del metodo Greedy:
Nella scansione avida mostrata qui come un albero (valore più alto maggiore avidità), è probabile che uno stato algoritmo a valore: 40, prenda 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 dei costi complessivo sarebbe 65, che è valutato 24 punti in più come decisione non ottimale.
Esempi di algoritmi avidi
La maggior parte degli algoritmi di rete utilizza l'approccio avido. Ecco un elenco di alcuni esempi di algoritmo Greedy:
- Algoritmo Minimal Spanning Tree di Prim
- Problema del commesso viaggiatore
- Grafico - Colorazione mappa
- Algoritmo Minimal Spanning Tree di Kruskal
- Algoritmo Minimal Spanning Tree di Dijkstra
- Grafico - Copertura vertice
- Problema dello zaino
- Problema di pianificazione del lavoro
Sommario:
Per riassumere, l'articolo ha definito il paradigma avido, ha mostrato come l'ottimizzazione e la ricorsione avida possono aiutarti a ottenere la soluzione migliore fino a un certo punto. L'algoritmo Greedy è ampiamente utilizzato per la risoluzione dei problemi in molti linguaggi come l'algoritmo Greedy Python, C, C #, PHP, Java, ecc. approccio. Alla fine, sono stati spiegati i demeriti dell'utilizzo dell'approccio avido.