algorithm
Algoritmi greedy

Osservazioni

Problema di zaino continuo

Dati gli articoli come (value, weight) dobbiamo metterli in uno zaino (contenitore) di una capacità k . Nota! Possiamo rompere gli oggetti per massimizzare il valore!

Esempio di input:

values[] = [1, 4, 5, 2, 10]
weights[] = [3, 2, 1, 2, 4]
k = 8

Uscita prevista:

maximumValueOfItemsInK = 20;

Algoritmo:

1) Sort values and weights by value/weight.
   values[] = [5, 10, 4, 2, 1]
   weights[] = [1, 4, 2, 2, 3]
2) currentWeight = 0; currentValue = 0;
3) FOR i = 0; currentWeight < k && i < values.length; i++ DO:
       IF k - currentWeight < weights[i] DO
           currentValue = currentValue + values[i];
           currentWeight = currentWeight + weights[i];
       ELSE
           currentValue = currentValue + values[i]*(k - currentWeight)/weights[i]
           currentWeight = currentWeight + weights[i]*(k - currentWeight)/weights[i]
       END_IF
   END_FOR
   PRINT "maximumValueOfItemsInK = " + currentValue;

Huffman Coding

Il codice di Huffman è un particolare tipo di codice di prefisso ottimale comunemente utilizzato per la compressione di dati senza perdita di dati. Comprime i dati in modo molto efficace salvando dal 20% al 90% della memoria, a seconda delle caratteristiche dei dati compressi. Consideriamo i dati come una sequenza di caratteri. L'algoritmo avido di Huffman utilizza una tabella che indica quanto spesso ogni personaggio si verifica (cioè la sua frequenza) per costruire un modo ottimale di rappresentare ogni carattere come una stringa binaria. Il codice di Huffman fu proposto da David A. Huffman nel 1951.

Supponiamo di avere un file di dati di 100.000 caratteri che desideriamo archiviare in modo compatto. Supponiamo che ci siano solo 6 caratteri diversi in quel file. La frequenza dei personaggi è data da:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
|Frequency (in thousands)|  45 |  13 |  12 |  16 |  9  |  5  |
+------------------------+-----+-----+-----+-----+-----+-----+

Abbiamo molte opzioni su come rappresentare un tale file di informazioni. Qui, consideriamo il problema della progettazione di un codice di carattere binario in cui ogni carattere è rappresentato da una stringa binaria unica, che chiamiamo codeword .

L'albero costruito ci fornirà:

+------------------------+-----+-----+-----+-----+-----+-----+
|        Character       |  a  |  b  |  c  |  d  |  e  |  f  |
+------------------------+-----+-----+-----+-----+-----+-----+
| Fixed-length Codeword  | 000 | 001 | 010 | 011 | 100 | 101 |
+------------------------+-----+-----+-----+-----+-----+-----+
|Variable-length Codeword|  0  | 101 | 100 | 111 | 1101| 1100|
+------------------------+-----+-----+-----+-----+-----+-----+

Se usiamo un codice a lunghezza fissa , abbiamo bisogno di tre bit per rappresentare 6 caratteri. Questo metodo richiede 300.000 bit per codificare l'intero file. Ora la domanda è: possiamo fare di meglio?

Un codice a lunghezza variabile può fare molto meglio di un codice a lunghezza fissa, dando ai personaggi frequenti brevi parole in codice e caratteri poco frequenti lunghi termini di codice. Questo codice richiede: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bit per rappresentare il file, che consente di risparmiare circa il 25% della memoria.

Una cosa da ricordare, qui consideriamo solo i codici in cui nessun codice è anche un prefisso di qualche altro codice. Questi sono chiamati prefissi. Per la codifica a lunghezza variabile, codifichiamo il file abc a 3 caratteri come 0.101.100 = 0101100, dove "." denota la concatenazione.

I prefissi sono desiderabili perché semplificano la decodifica. Poiché nessun codice è un prefisso di un altro, il codice che inizia un file codificato non è ambiguo. Possiamo semplicemente identificare il codice iniziale, tradurlo nel carattere originale e ripetere il processo di decodifica sul resto del file codificato. Ad esempio, 001011101 analizza in modo univoco come 0.0.101.1101, che viene decodificato su aabe . In breve, tutte le combinazioni di rappresentazioni binarie sono uniche. Per esempio, se una lettera è indicata con 110, nessuna altra lettera sarà indicata con 1101 o 1100. Questo perché potresti confondere se selezionare 110 o continuare concatenando il bit successivo e selezionarlo.

Tecnica di compressione:

La tecnica funziona creando un albero binario di nodi. Questi possono essere archiviati in una matrice normale, la cui dimensione dipende dal numero di simboli, n . Un nodo può essere un nodo foglia o un nodo interno . Inizialmente tutti i nodi sono nodi foglia, che contengono il simbolo stesso, la sua frequenza e, facoltativamente, un collegamento ai suoi nodi figli. Come convenzione, il bit '0' rappresenta il figlio sinistro e il bit '1' rappresenta il figlio destro. La coda prioritaria viene utilizzata per archiviare i nodi, che fornisce il nodo con la frequenza più bassa quando viene fatto scoppiare. Il processo è descritto di seguito:

1. Creare un nodo foglia per ogni simbolo e aggiungerlo alla coda di priorità.
2. Mentre c'è più di un nodo nella coda:
   1. Rimuovere i due nodi di massima priorità dalla coda.
   2. Creare un nuovo nodo interno con questi due nodi come figli e con frequenza uguale alla somma della frequenza dei due nodi.
   3. Aggiungi il nuovo nodo alla coda.
3. Il nodo rimanente è il nodo radice e l'albero di Huffman è completo.

Per il nostro esempio:

Lo pseudo-codice assomiglia a:

Procedure Huffman(C):     // C is the set of n characters and related information
n = C.size
Q = priority_queue()
for i = 1 to n
    n = node(C[i])
    Q.push(n)
end for
while Q.size() is not equal to 1
    Z = new node()
    Z.left = x = Q.pop
    Z.right = y = Q.pop
    Z.frequency = x.frequency + y.frequency
    Q.push(Z)
end while
Return Q

Sebbene l'input ordinato in base al tempo lineare, in generale in caso di input arbitrario, l'utilizzo di questo algoritmo richiede il pre-ordinamento. Pertanto, poiché l'ordinamento richiede O (nlogn) tempo in casi generali, entrambi i metodi hanno la stessa complessità.

Poiché n qui è il numero di simboli nell'alfabeto, che è in genere un numero molto piccolo (rispetto alla lunghezza del messaggio da codificare), la complessità del tempo non è molto importante nella scelta di questo algoritmo.

Tecnica di decompressione:

Il processo di decompressione è semplicemente una questione di traduzione del flusso di codici prefisso per il singolo valore di byte, di solito attraversando il nodo Huffman per nodo mentre ogni bit viene letto dal flusso di input. Raggiungere un nodo foglia termina necessariamente la ricerca per quel particolare valore di byte. Il valore foglia rappresenta il carattere desiderato. Di solito l'albero di Huffman è costruito usando dati aggiustati statisticamente su ogni ciclo di compressione, quindi la ricostruzione è abbastanza semplice. Altrimenti, le informazioni per ricostruire l'albero devono essere inviate separatamente. Lo pseudo-codice:

Procedure HuffmanDecompression(root, S):   // root represents the root of Huffman Tree
n := S.length                              // S refers to bit-stream to be decompressed
for i := 1 to n
    current = root
    while current.left != NULL and current.right != NULL
        if S[i] is equal to '0'
            current := current.left
        else
            current := current.right
        endif
        i := i+1
    endwhile
    print current.symbol
endfor

Spiegazione avida:
La codifica di Huffman esamina l'occorrenza di ciascun carattere e lo memorizza come una stringa binaria in modo ottimale. L'idea è di assegnare codici di lunghezza variabile ai caratteri di input input, la lunghezza dei codici assegnati si basa sulle frequenze dei caratteri corrispondenti. Creiamo un albero binario e operiamo in modo bottom-up in modo che i meno due caratteri frequenti siano il più lontano possibile dalla radice. In questo modo, il carattere più frequente ottiene il codice più piccolo e il carattere meno frequente ottiene il codice più grande.

Riferimenti:

• Introduzione agli algoritmi - Charles E. Leiserson, Clifford Stein, Ronald Rivest e Thomas H. Cormen
• Codifica Huffman - Wikipedia
• Matematica discreta e sue applicazioni - Kenneth H. Rosen

Problema di cambiamento

Dato un sistema monetario, è possibile dare una quantità di monete e come trovare una serie minima di monete corrispondente a tale importo.

Sistemi monetari canonici. Per alcuni sistemi monetari, come quelli che usiamo nella vita reale, la soluzione "intuitiva" funziona perfettamente. Ad esempio, se le diverse monete e banconote in euro (esclusi i centesimi) sono 1 €, 2 €, 5 €, 10 €, dando la moneta o il conto più alti fino a raggiungere l'importo e ripetendo questa procedura si otterrà il set minimo di monete .

Possiamo farlo in modo ricorsivo con OCaml:

(* assuming the money system is sorted in decreasing order *)
let change_make money_system amount =
  let rec loop given amount =
    if amount = 0 then given
    else 
      (* we find the first value smaller or equal to the remaining amount *)
      let coin = List.find ((>=) amount) money_system in
      loop (coin::given) (amount - coin)
  in loop [] amount

Questi sistemi sono fatti in modo che il cambiamento sia facile. Il problema diventa più difficile quando si tratta di un sistema di denaro arbitrario.

Caso generale Come dare 99 € con monete da 10 €, 7 € e 5 €? Qui, dare monete di 10 € fino a quando non ci rimane con 9 € porta ovviamente a nessuna soluzione. Peggio ancora che una soluzione potrebbe non esistere. Questo problema è in realtà np-difficile, ma esistono soluzioni accettabili che mescolano avidità e memoizzazione . L'idea è di esplorare tutte le possibilità e scegliere quella con il numero minimo di monete.

Per dare un importo X> 0, scegliamo un pezzo P nel sistema monetario, e quindi risolviamo il sotto-problema corrispondente a XP. Proviamo questo per tutti i pezzi del sistema. La soluzione, se esiste, è quindi il percorso più piccolo che porta a 0.

Qui una funzione ricorsiva OCaml corrispondente a questo metodo. Restituisce None, se non esiste alcuna soluzione.

(* option utilities *)
let optmin x y =
  match x,y with
  | None,a | a,None -> a
  | Some x, Some y-> Some (min x y)

let optsucc = function
  | Some x -> Some (x+1)
  | None -> None

(* Change-making problem*)
let change_make money_system amount =
  let rec loop n =
    let onepiece acc piece =
      match n - piece with
      | 0 -> (*problem solved with one coin*) 
             Some 1
      | x -> if x < 0 then 
               (*we don't reach 0, we discard this solution*)
               None
             else
               (*we search the smallest path different to None with the remaining pieces*) 
               optmin (optsucc (loop x)) acc
    in
    (*we call onepiece forall the pieces*)
    List.fold_left onepiece None money_system
  in loop amount

Nota : possiamo osservare che questa procedura può calcolare più volte il set di modifiche per lo stesso valore. In pratica, l'utilizzo della memoizzazione per evitare queste ripetizioni porta a risultati più rapidi (molto più veloci).

Problema di selezione dell'attività

Il problema

Hai una serie di cose da fare (attività). Ogni attività ha un'ora di inizio e un'ora di fine. Non sei autorizzato a svolgere più di un'attività alla volta. Il tuo compito è trovare un modo per eseguire il numero massimo di attività.

Ad esempio, supponiamo di avere una selezione di classi tra cui scegliere.

Ricorda, non puoi prendere due lezioni allo stesso tempo. Ciò significa che non puoi prendere lezioni di classe 1 e 2 perché condividono un orario comune dalle 10.30 alle 11.00. Tuttavia, puoi prendere lezioni di classe 1 e 3 perché non condividono un orario comune. Quindi il tuo compito è quello di prendere il massimo numero di classi possibile senza sovrapposizioni. Come puoi farlo?

Analisi

Pensiamo alla soluzione con un approccio avido. Prima di tutto abbiamo scelto a caso un approccio e verificato che funzionerà o meno.

• ordina l'attività per ora di inizio, il che significa che l'attività inizia per prima cosa le prenderemo prima. quindi prendi il primo all'ultimo dalla lista ordinata e verifica che si intersechi dall'attività precedente o meno. Se l'attività corrente non è intersecata con l'attività precedentemente svolta, eseguiremo l'attività altrimenti non eseguiremo. questo approccio funzionerà per alcuni casi come

l'ordine di selezione sarà 4 -> 1 -> 2 -> 3. L'attività 4 -> 1 -> 3 verrà eseguita e l'attività 2 verrà saltata. verrà eseguita l'attività massima 3. Funziona per questo tipo di casi. ma fallirà per alcuni casi. Applichiamo questo approccio per il caso

L'ordinamento sarà 4 -> 1 -> 2 -> 3 e verrà eseguita solo l'attività 4 ma la risposta può essere l'attività 1 -> 3 o 2 -> 3 verrà eseguita. Quindi il nostro approccio non funzionerà per il caso di cui sopra. Proviamo un altro approccio

• Ordina l'attività in base alla durata che significa eseguire prima l'attività più breve. che può risolvere il problema precedente. Anche se il problema non è completamente risolto. Ci sono ancora alcuni casi che possono fallire nella soluzione. applicare questo approccio sul caso qui sotto.

se ordiniamo l'attività in base alla durata, l'ordinamento sarà 2 -> 3 ---> 1. e se eseguiamo prima l'attività n. 2, non è possibile eseguire altre attività. Ma la risposta sarà eseguire l'attività 1 quindi eseguire 3. Quindi possiamo eseguire massimo 2 attività. Quindi questa non può essere una soluzione a questo problema. Dovremmo provare un approccio diverso.

La soluzione

• Ordina l'attività terminando il tempo che significa che l'attività termina per prima. l'algoritmo è indicato di seguito

1. Ordina le attività in base ai tempi finali.
2. Se l'attività da svolgere non condivide un tempo comune con le attività precedentemente svolte, eseguire l'attività.

Analizziamo il primo esempio

ordina l'attività in base agli orari finali, quindi l'ordinamento sarà 1 -> 5 -> 2 -> 4 -> 3 .. la risposta è 1 -> 3 queste due attività verranno eseguite. e questa è la risposta. ecco il codice sudo.

1. ordina: attività
2. eseguire la prima attività dall'elenco ordinato di attività.
3. Set: Current_activity: = prima attività
4. set: end_time: = end_time of Current activity
5. andare alla prossima attività se esistente, se non esistono terminare.
6. se start_time dell'attività corrente <= end_time: esegui l'attività e vai a 4
7. altro: arriva a 5.

vedere qui per la guida alla codifica http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/