Algoritmi avidi spiegati con esempi

Cos'è un algoritmo avido?

Potresti aver sentito parlare di molte tecniche di progettazione algoritmica mentre analizzi alcuni degli articoli qui. Alcuni di loro sono:

  • Forza bruta
  • Dividere e conquistare
  • Programmazione avida
  • Programmazione dinamica per citarne alcuni. In questo articolo imparerai cos'è un algoritmo avido e come puoi utilizzare questa tecnica per risolvere molti problemi di programmazione che altrimenti non sembrerebbero banali.

Immagina di fare un'escursione e il tuo obiettivo è raggiungere la vetta più alta possibile. Hai già la mappa prima di iniziare, ma ci sono migliaia di possibili percorsi mostrati sulla mappa. Sei troppo pigro e semplicemente non hai il tempo di valutarli ciascuno. Fanculo la mappa! Hai iniziato a fare escursioni con una strategia semplice: sii avido e miope. Basta prendere i sentieri che salgono di più. Questa sembra una buona strategia per l'escursionismo. Ma è sempre il migliore?

Dopo che il viaggio è finito e tutto il tuo corpo è dolorante e stanco, guardi per la prima volta la mappa escursionistica. Oh mio Dio! C'è un fiume fangoso che avrei dovuto attraversare, invece di continuare a camminare verso l'alto. Ciò significa che un algoritmo avido sceglie la migliore scelta immediata e non riconsidera mai le sue scelte. In termini di ottimizzazione di una soluzione, ciò significa semplicemente che la soluzione avida cercherà di trovare soluzioni ottimali locali - che possono essere molte - e potrebbe perdere una soluzione ottimale globale.

Definizione formale

Supponi di avere una funzione obiettivo che deve essere ottimizzata (massimizzata o minimizzata) in un dato punto. Un algoritmo Greedy fa scelte avide in ogni fase per garantire che la funzione obiettivo sia ottimizzata. L'algoritmo Greedy ha una sola possibilità per calcolare la soluzione ottimale in modo che non torni indietro e inverta la decisione.

Gli algoritmi avidi hanno alcuni vantaggi e svantaggi:

  • È abbastanza facile trovare un algoritmo avido (o anche più algoritmi avidi) per un problema. L'analisi del tempo di esecuzione per algoritmi avidi sarà generalmente molto più semplice rispetto ad altre tecniche (come Dividi e conquista). Per la tecnica Divide and conquer, non è chiaro se la tecnica sia veloce o lenta. Questo perché ad ogni livello di ricorsione la dimensione di si riduce e il numero di sottoproblemi aumenta.
  • La parte difficile è che per gli algoritmi avidi devi lavorare molto di più per comprendere i problemi di correttezza. Anche con l'algoritmo corretto, è difficile dimostrare perché è corretto. Dimostrare che un algoritmo avido è corretto è più un'arte che una scienza. Coinvolge molta creatività. Di solito, inventare un algoritmo potrebbe sembrare banale, ma provare che è effettivamente corretto, è un problema completamente diverso.

Problema di pianificazione degli intervalli

Immergiamoci in un problema interessante che puoi incontrare in quasi tutti i settori o in qualsiasi ambito della vita. Alcuni casi del problema sono i seguenti:

  • Ti viene fornita una serie di N orari di lezioni per un solo giorno all'università. Il programma per una lezione specifica è della forma ( ora s , ora f ) dove l' ora s rappresenta l'ora di inizio per quella lezione e allo stesso modo l' ora f rappresenta l'ora di fine. Dato un elenco di N pianificazioni di lezioni, dobbiamo selezionare l'insieme massimo di lezioni da tenere durante il giorno in modo tale che   nessuna delle lezioni si sovrapponga l'una all'altra, cioè se le lezioni Li e Lj sono incluse nella nostra selezione, l'ora di inizio di j > = tempo di fine di i o viceversa .
  • Il tuo amico lavora come consulente del campo ed è incaricato di organizzare attività per un gruppo di campeggiatori. Uno dei suoi piani è il seguente esercizio di mini-triathlon: ogni concorrente deve nuotare per 20 giri in una piscina, quindi pedalare per 10 miglia, quindi correre per 3 miglia.
  • Il piano è di far uscire i concorrenti in modo sfalsato, secondo la seguente regola: i concorrenti devono utilizzare la piscina uno alla volta. In altre parole, il primo concorrente nuota per i 20 giri, scende e inizia a pedalare.
  • Non appena questa prima persona è fuori dalla piscina, un secondo concorrente inizia a nuotare per i 20 giri; non appena lui o lei è fuori e inizia a pedalare, un terzo concorrente inizia a nuotare e così via.
  • Ogni concorrente ha un tempo di nuoto previsto, un tempo di ciclismo previsto e un tempo di corsa previsto. Il tuo amico vuole decidere un programma per il triathlon: un ordine in cui mettere in sequenza le partenze dei concorrenti.
  • Diciamo che il tempo di completamento di un programma è il primo momento in cui tutti i concorrenti finiranno con tutte e tre le tappe del triathlon, supponendo che le proiezioni temporali siano accurate. Qual è l'ordine migliore per mandare fuori le persone, se si vuole che l'intera competizione finisca il prima possibile? Più precisamente, fornire un algoritmo efficiente che produca una pianificazione il cui tempo di completamento è il più piccolo possibile

Il problema della pianificazione delle lezioni

Diamo un'occhiata ai vari approcci per risolvere questo problema.

Prima ora di inizio Per prima cosa, ad  esempio, selezionare l'intervallo con l'ora di inizio meno recente. Dai un'occhiata al seguente esempio che rompe questa soluzione. Questa soluzione non è riuscita perché potrebbe esserci un intervallo che inizia molto presto ma è molto lungo. Ciò significa che la prossima strategia che potremmo provare sarebbe quella di guardare prima a intervalli più piccoli.

Prima ora di inizio prima

Intervallo più piccolo Innanzitutto  si finisce per selezionare le lezioni in base al loro intervallo complessivo che non è altro che il loro   finish time - start time. Ancora una volta, questa soluzione non è corretta. Guarda il seguente caso.

Primo intervallo più breve

Puoi vedere chiaramente che la lezione con intervallo più breve è quella centrale, ma qui non è la soluzione ottimale. Diamo un'occhiata a un'altra soluzione per questo problema che deriva da questa soluzione.

Intervallo minimo di conflitto Innanzitutto,  vale a dire che dovresti esaminare gli intervalli che causano il minor numero di conflitti. Ancora una volta abbiamo un esempio in cui questo approccio non riesce a trovare una soluzione ottimale.

Primo intervallo di conflitto minimo

Il diagramma ci mostra che l'intervallo meno conflittuale è quello al centro con solo 2 conflitti. Dopodiché possiamo solo scegliere i due intervalli alle estremità con conflitti 3 ciascuno. Ma la soluzione ottimale è scegliere i 4 intervalli sul livello più alto.

Primo tempo di arrivo prima . Questo è l'approccio che ci dà sempre la soluzione più ottimale a questo problema. Abbiamo ricavato molte informazioni dagli approcci precedenti e alla fine ci siamo imbattuti in questo approccio. Ordiniamo gli intervalli in base all'ordine crescente dei loro tempi di fine e quindi iniziamo a selezionare gli intervalli dall'inizio. Guarda il seguente pseudo codice per maggiore chiarezza.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Quando usiamo Greedy Algorithms

Greedy Algorithms può aiutarti a trovare soluzioni a molti problemi apparentemente difficili. L'unico problema con loro è che potresti trovare la soluzione corretta ma potresti non essere in grado di verificare se è quella corretta. Tutti i problemi avidi condividono una proprietà comune che un ottimo locale può eventualmente portare a un minimo globale senza riconsiderare l'insieme di scelte già considerate.

Greedy Algorithms ci aiuta a risolvere molti tipi diversi di problemi, come:

Problema del percorso più breve:

Problema minimo dell'albero di copertura in un grafico

Problema di codifica di Huffman

Problema dei centri K.