algorithm
Hebzuchtige algoritmen

Opmerkingen

Continu knapzak probleem

Gegeven items als (value, weight) we ze in een knapzak (container) met een capaciteit k . Notitie! We kunnen items breken om de waarde te maximaliseren!

Voorbeeld invoer:

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

Verwachte resultaten:

maximumValueOfItemsInK = 20;

Algoritme:

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-codering

Huffman-code is een bepaald type optimale prefixcode die vaak wordt gebruikt voor gegevenscompressie zonder verlies. Het comprimeert gegevens zeer effectief en bespaart 20% tot 90% geheugen, afhankelijk van de kenmerken van de gegevens die worden gecomprimeerd. We beschouwen de gegevens als een reeks tekens. Het hebzuchtige algoritme van Huffman gebruikt een tabel die aangeeft hoe vaak elk karakter voorkomt (dwz de frequentie ervan) om een optimale manier op te bouwen om elk karakter als een binaire string weer te geven. Huffman-code werd voorgesteld door David A. Huffman in 1951.

Stel dat we een gegevensbestand van 100.000 tekens hebben dat we compact willen opslaan. We nemen aan dat er slechts 6 verschillende tekens in dat bestand zijn. De frequentie van de tekens wordt gegeven door:

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

We hebben veel opties om zo'n bestand met informatie weer te geven. Hier beschouwen we het probleem van het ontwerpen van een binaire tekencode waarin elk teken wordt voorgesteld door een unieke binaire reeks, die we een codewoord noemen.

De geconstrueerde boom zal ons voorzien van:

+------------------------+-----+-----+-----+-----+-----+-----+
|        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|
+------------------------+-----+-----+-----+-----+-----+-----+

Als we een code met een vaste lengte gebruiken , hebben we drie bits nodig om 6 tekens te vertegenwoordigen. Deze methode vereist 300.000 bits om het hele bestand te coderen. Nu is de vraag, kunnen we het beter doen?

Een code met variabele lengte kan aanzienlijk beter doen dan een code met een vaste lengte, door frequente tekens korte codewoorden en niet-frequente tekens lange codewoorden te geven. Deze code vereist: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bits om het bestand te vertegenwoordigen, wat ongeveer 25% geheugen bespaart.

Een ding om te onthouden, we beschouwen hier alleen codes waarin geen codewoord ook een voorvoegsel is van een ander codewoord. Dit worden prefixcodes genoemd . Voor codering met variabele lengte coderen we het 3-tekensbestand abc als 0.101.100 = 0101100, waar "." geeft de aaneenschakeling aan.

Voorvoegselcodes zijn wenselijk omdat ze het decoderen vereenvoudigen. Aangezien geen codewoord een voorvoegsel van een ander is, is het codewoord dat een gecodeerd bestand begint ondubbelzinnig. We kunnen eenvoudig het initiële codewoord identificeren, het terug vertalen naar het oorspronkelijke karakter en het decodeerproces herhalen voor de rest van het gecodeerde bestand. Bijvoorbeeld, 001011101 parseert uniek als 0.0.101.1101, die decodeert naar aabe . Kortom, alle combinaties van binaire representaties zijn uniek. Stel bijvoorbeeld dat als een letter wordt aangeduid met 110, geen andere letter wordt aangeduid met 1101 of 1100. Dit komt omdat u misschien verwarring ondervindt bij het selecteren van 110 of doorgaan met het samenvoegen van het volgende bit en het selecteren van die ene.

Compressie techniek:

De techniek werkt door een binaire boomstructuur van knooppunten te maken. Deze kunnen worden opgeslagen in een normale array, waarvan de grootte afhangt van het aantal symbolen, n . Een knoop kan een bladknoop of een interne knoop zijn . Aanvankelijk zijn alle knooppunten bladknooppunten, die het symbool zelf, de frequentie ervan en optioneel een link naar de onderliggende knooppunten bevatten. Als conventie staat bit '0' voor het linkerkind en bit '1' voor het rechterkind. Prioriteitswachtrij wordt gebruikt om de knooppunten op te slaan, waardoor de knoop de laagste frequentie krijgt wanneer deze wordt geopend. Het proces wordt hieronder beschreven:

1. Maak een bladknooppunt voor elk symbool en voeg dit toe aan de prioriteitswachtrij.
2. Terwijl er meer dan één knooppunt in de wachtrij staat:
   1. Verwijder de twee knooppunten met de hoogste prioriteit uit de wachtrij.
   2. Maak een nieuw intern knooppunt met deze twee knooppunten als kinderen en met een frequentie gelijk aan de som van de frequentie van de twee knooppunten.
   3. Voeg het nieuwe knooppunt toe aan de wachtrij.
3. De resterende knoop is de wortelknoop en de Huffman-boom is voltooid.

Voor ons voorbeeld:

De pseudo-code ziet eruit als:

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

Hoewel gesorteerde invoer met lineaire tijd wordt gegeven, vereist in het algemeen gevallen van willekeurige invoer voorsortering. Omdat sorteren in het algemeen O (nlogn) tijd kost, hebben beide methoden dus dezelfde complexiteit.

Aangezien n hier het aantal symbolen in het alfabet is, wat meestal een zeer klein aantal is (vergeleken met de lengte van het te coderen bericht), is tijdcomplexiteit niet erg belangrijk bij de keuze van dit algoritme.

Decompressietechniek:

Het decompressieproces is eenvoudigweg een kwestie van het vertalen van de stroom prefixcodes naar individuele byte-waarden, meestal door de Huffman-boom knoop voor knoop te doorlopen terwijl elk bit uit de invoerstroom wordt gelezen. Als u een bladknooppunt bereikt, wordt het zoeken naar die specifieke bytewaarde noodzakelijkerwijs beëindigd. De bladwaarde vertegenwoordigt het gewenste teken. Gewoonlijk wordt de Huffman Tree gebouwd met behulp van statistisch aangepaste gegevens over elke compressiecyclus, dus de reconstructie is vrij eenvoudig. Anders moet de informatie om de boom te reconstrueren afzonderlijk worden verzonden. De pseudo-code:

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

Hebzuchtige uitleg:
Huffman-codering kijkt naar het voorkomen van elk karakter en slaat het op als een binaire string op een optimale manier. Het idee is om codes met variabele lengte toe te wijzen aan invoertekens, de lengte van de toegewezen codes is gebaseerd op de frequenties van overeenkomstige tekens. We creëren een binaire boom en werken erop op een bottom-up manier, zodat de minst twee frequente karakters zo ver mogelijk van de root verwijderd zijn. Op deze manier krijgt het meest voorkomende teken de kleinste code en krijgt het minst frequente teken de grootste code.

Referenties:

• Inleiding tot algoritmen - Charles E. Leiserson, Clifford Stein, Ronald Rivest en Thomas H. Cormen
• Huffman-codering - Wikipedia
• Discrete wiskunde en zijn toepassingen - Kenneth H. Rosen

Veranderingsprobleem

Gegeven een geldsysteem, is het mogelijk om een aantal munten te geven en hoe een minimale set munten te vinden die overeenkomt met dit bedrag.

Canonieke geldsystemen. Voor sommige geldsystemen, zoals die we in het echte leven gebruiken, werkt de "intuïtieve" oplossing perfect. Bijvoorbeeld, als de verschillende euromunten en biljetten (exclusief centen) 1 €, 2 €, 5 €, 10 € zijn, geeft de hoogste munt of rekening tot we het bedrag bereiken en deze procedure herhalen zal leiden tot de minimale set munten .

We kunnen dat recursief doen met 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

Deze systemen zijn zo gemaakt dat gemakkelijk wijzigingen kunnen worden aangebracht. Het probleem wordt moeilijker als het gaat om een willekeurig geldsysteem.

Algemene zaak. Hoe 99 € te geven met munten van 10 €, 7 € en 5 €? Hier geeft het geven van munten van 10 € tot we nog 9 € hebben duidelijk geen oplossing. Erger dan dat een oplossing misschien niet bestaat. Dit probleem is in feite np-hard, maar er bestaan acceptabele oplossingen die hebzucht en memo combineren . Het idee is om alle mogelijkheden te verkennen en degene te kiezen met het minimale aantal munten.

Om een bedrag X> 0 te geven, kiezen we een stuk P in het geldsysteem en lossen dan het subprobleem op dat overeenkomt met XP. We proberen dit voor alle onderdelen van het systeem. De oplossing, als deze bestaat, is dan het kleinste pad dat tot 0 leidde.

Hier een OCaml recursieve functie die overeenkomt met deze methode. Het geeft Geen terug, als er geen oplossing bestaat.

(* 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

Opmerking : We kunnen opmerken dat deze procedure de wijziging die voor dezelfde waarde is ingesteld, meerdere keren kan berekenen. In de praktijk leidt het gebruik van memo om deze herhalingen te voorkomen tot snellere (veel snellere) resultaten.

Activiteit selectie probleem

Het probleem

Je hebt een aantal dingen om te doen (activiteiten). Elke activiteit heeft een starttijd en een eindtijd. U mag niet meer dan één activiteit tegelijk uitvoeren. Jouw taak is om een manier te vinden om het maximale aantal activiteiten uit te voeren.

Stel bijvoorbeeld dat u een selectie klassen hebt om uit te kiezen.

Vergeet niet dat je niet twee lessen tegelijk kunt volgen. Dat betekent dat je klasse 1 en 2 niet kunt nemen omdat ze een gemeenschappelijke tijd delen 10.30 uur tot 11.00 uur. Je kunt echter klasse 1 en 3 nemen omdat ze geen gemeenschappelijke tijd delen. Het is dus uw taak om zoveel mogelijk klassen te volgen zonder overlapping. Hoe kan je dat doen?

Analyse

Laten we nadenken over de oplossing door hebzuchtige aanpak. Allereerst hebben we willekeurig gekozen voor een aanpak en controleren of die zal werken of niet.

• sorteer de activiteit op starttijd, wat betekent dat welke activiteit als eerste begint, we nemen ze eerst. neem vervolgens de eerste naar de laatste uit de gesorteerde lijst en controleer of deze de eerder genomen activiteit kruist of niet. Als de huidige activiteit niet wordt gekruist met de eerder genomen activiteit, zullen we de activiteit uitvoeren, anders zullen we niet uitvoeren. deze aanpak werkt in sommige gevallen zoals

de sorteervolgorde is 4 -> 1 -> 2 -> 3. De activiteit 4 -> 1 -> 3 wordt uitgevoerd en de activiteit 2 wordt overgeslagen. de maximale 3 activiteit zal worden uitgevoerd. Het werkt voor dit soort gevallen. maar het zal in sommige gevallen mislukken. Laten we deze aanpak toepassen op de zaak

De sorteervolgorde is 4 -> 1 -> 2 -> 3 en alleen activiteit 4 wordt uitgevoerd, maar het antwoord kan activiteit 1 -> 3 of 2 -> 3 zijn. Dus onze aanpak zal niet werken voor het bovenstaande geval. Laten we een andere aanpak proberen

• Sorteer de activiteit op tijdsduur, wat betekent dat u eerst de kortste activiteit uitvoert. dat kan het vorige probleem oplossen. Hoewel het probleem niet volledig is opgelost. Er zijn nog enkele gevallen waarin de oplossing kan mislukken. pas deze benadering toe op het geval hieronder.

Als we de activiteit sorteren op tijdsduur, is de sorteervolgorde 2 -> 3 ---> 1. en als we eerst activiteit 2 uitvoeren, kunnen er geen andere activiteiten worden uitgevoerd. Maar het antwoord zal activiteit 1 zijn en dan 3 uitvoeren. We kunnen dus maximaal 2 activiteiten uitvoeren, dus dit kan geen oplossing voor dit probleem zijn. We moeten een andere aanpak proberen.

De oplossing

• Sorteer de activiteit op eindtijd, wat betekent dat de activiteit als eerste eindigt. het algoritme wordt hieronder gegeven

1. Sorteer de activiteiten op eindtijd.
2. Als de uit te voeren activiteit geen gemeenschappelijke tijd deelt met de eerder uitgevoerde activiteiten, voert u de activiteit uit.

Laten we het eerste voorbeeld analyseren

sorteer de activiteit op de eindtijd, dus de sorteervolgorde is 1 -> 5 -> 2 -> 4 -> 3 .. het antwoord is 1 -> 3 deze twee activiteiten worden uitgevoerd. en dat is het antwoord. hier is de sudo-code.

1. sorteren: activiteiten
2. voer de eerste activiteit uit de gesorteerde lijst van activiteiten uit.
3. Set: Huidige activiteit: = eerste activiteit
4. set: end_time: = end_time van Huidige activiteit
5. ga naar volgende activiteit indien bestaan, indien niet bestaan beëindigen.
6. if start_time of current activity <= end_time: voer de activiteit uit en ga naar 4
7. anders: kreeg tot 5.

zie hier voor hulp bij codering http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/