algorithm
Giriga algoritmer

Anmärkningar

Kontinuerligt ryggsäckproblem

Givet föremål som (value, weight) måste vi placera dem i en ryggsäck (behållare) med en kapacitet k . Notera! Vi kan bryta objekt för att maximera värdet!

Exempelinmatning:

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

Förväntad produktion:

maximumValueOfItemsInK = 20;

Algoritm:

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

Huffman-kod är en viss typ av optimal prefixkod som vanligtvis används för förlustfri datakomprimering. Den komprimerar data mycket effektivt och sparar från 20% till 90% minne, beroende på egenskaperna hos data som komprimeras. Vi anser att uppgifterna är en sekvens av tecken. Huffmans giriga algoritm använder en tabell som anger hur ofta varje karaktär inträffar (dvs. dess frekvens) för att bygga upp ett optimalt sätt att representera varje karaktär som en binär sträng. Huffman-koden föreslogs av David A. Huffman 1951.

Anta att vi har en 100 000-tecken datafil som vi vill lagra kompakt. Vi antar att det bara finns 6 olika tecken i den filen. Teckenens frekvens anges av:

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

Vi har många alternativ för hur du representerar en sådan informationsfil. Här överväger vi problemet med att utforma en binär karaktärskod där varje tecken representeras av en unik binär sträng, som vi kallar ett kodord .

Det konstruerade trädet kommer att ge oss:

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

Om vi använder en fast längdskod behöver vi tre bitar för att representera 6 tecken. Den här metoden kräver 300 000 bitar för att koda hela filen. Nu är frågan: kan vi göra bättre?

En kod med variabel längd kan göra betydligt bättre än en kod med fast längd genom att ge frekventa tecken korta kodord och sällsynta tecken långa kodord. Denna kod kräver: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 bitar för att representera filen, vilket sparar ungefär 25% minne.

En sak att komma ihåg, vi tar bara hänsyn till koder där inget kodord också är ett prefix för något annat kodord. Dessa kallas prefixkoder. För kodning med variabel längd kodar vi 3-teckenfilen abc som 0.101.100 = 0101100, där "." anger sammankopplingen.

Prefixkoder är önskvärda eftersom de förenklar avkodningen. Eftersom inget kodord är ett prefix för något annat är kodordet som startar en kodad fil otvetydigt. Vi kan helt enkelt identifiera det ursprungliga kodordet, översätta det tillbaka till det ursprungliga tecknet och upprepa avkodningsprocessen på resten av den kodade filen. Till exempel analyserar 001011101 unikt som 0.0.101.1101, som avkodas till aabe . Kort sagt, alla kombinationer av binära representationer är unika. Säg till exempel, om en bokstav betecknas med 110, kommer ingen annan bokstav att betecknas med 1101 eller 1100. Det beror på att du kan möta förvirring om du vill välja 110 eller fortsätta att sammanfoga nästa bit och välja den.

Komprimeringsteknik:

Tekniken fungerar genom att skapa ett binärt träd av noder. Dessa kan lagras i en vanlig grupp där storleken beror på antalet symboler, n . En nod kan antingen vara en bladnod eller en intern nod . Ursprungligen är alla noder bladnoder som innehåller själva symbolen, dess frekvens och eventuellt en länk till dess underordnade noder. Som en konvention representerar bit '0' vänster barn och bit '1' representerar höger barn. Prioritetskö används för att lagra noderna, vilket ger noden lägsta frekvens när den poppas. Processen beskrivs nedan:

1. Skapa en bladnod för varje symbol och lägg till den i prioriteringskön.
2. Medan det finns mer än en nod i kön:
   1. Ta bort de två noderna med högsta prioritet från kön.
   2. Skapa en ny intern nod med dessa två noder som barn och med en frekvens som är lika med summan av de två noderna frekvens.
   3. Lägg till den nya noden i kön.
3. Den återstående noden är rotnoden och Huffman-trädet är komplett.

För vårt exempel:

Pseudokoden ser ut som:

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

Även om linjär tid ges sorterad ingång, i allmänhet fall av godtycklig inmatning, kräver användning av denna algoritm för sortering. Eftersom sortering tar O (nlogn) tid i allmänna fall har båda metoderna därför samma komplexitet.

Eftersom n här är antalet symboler i alfabetet, som vanligtvis är mycket litet antal (jämfört med längden på meddelandet som ska kodas), är tidskomplexiteten inte så viktig för valet av denna algoritm.

Dekompressionsteknik:

Processen med dekomprimering är helt enkelt en fråga om att översätta strömmen av prefixkoder till individuellt bytevärde, vanligtvis genom att korsa Huffman-trädnoden efter nod eftersom varje bit läses från inmatningsströmmen. Att nå en bladnod avslutar nödvändigtvis sökningen efter det specifika bytevärdet. Bladvärdet representerar det önskade tecknet. Vanligtvis konstrueras Huffmanträdet med hjälp av statistiskt justerade data för varje komprimeringscykel, så rekonstruktionen är ganska enkel. Annars måste informationen för att rekonstruera trädet skickas separat. Pseudokoden:

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

Girig förklaring:
Huffman-kodning ser på förekomsten av varje tecken och lagrar den som en binär sträng på ett optimalt sätt. Tanken är att tilldela koder med variabel längd till inmatade inmatningstecken, längden på de tilldelade koderna är baserade på frekvenserna för motsvarande tecken. Vi skapar ett binärt träd och arbetar på det nedifrån och upp så att de minst två frekventa tecknen ligger så långt som möjligt från roten. På detta sätt får den vanligaste karaktären den minsta koden och den minst frekventa karaktären får den största koden.

referenser:

• Introduktion till algoritmer - Charles E. Leiserson, Clifford Stein, Ronald Rivest och Thomas H. Cormen
• Huffman Coding - Wikipedia
• Diskret matematik och dess tillämpningar - Kenneth H. Rosen

Förändringsproblem

Med ett pengarsystem är det möjligt att ge ett antal mynt och hur man hittar en minimal uppsättning mynt som motsvarar detta belopp.

Kanoniska pengarsystem. För vissa pengarsystem, som de vi använder i det verkliga livet, fungerar den "intuitiva" lösningen perfekt. Till exempel, om de olika euromynten och -räkningarna (exklusive cent) är 1 €, 2 €, 5 €, 10 €, ger det högsta myntet eller räkningen tills vi når beloppet och upprepar detta förfarande kommer att leda till den minimala uppsättningen av mynt .

Vi kan göra det rekursivt med 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

Dessa system är tillverkade så att det är enkelt att göra förändringar. Problemet blir svårare när det gäller godtyckliga pengarsystem.

Allmänt fall. Hur kan man ge 99 € med mynt på 10 €, 7 € och 5 €? Att ge mynt på 10 € tills vi sitter kvar med 9 € leder här uppenbarligen till ingen lösning. Värre än att en lösning kanske inte finns. Detta problem är i själva verket np-hårt, men acceptabla lösningar som blandar girighet och memoisering finns. Tanken är att utforska alla möjligheter och välja en med det minimala antalet mynt.

För att ge ett belopp X> 0 väljer vi ett stycke P i pengarsystemet och löser sedan delproblemet som motsvarar XP. Vi försöker detta för alla delar av systemet. Lösningen, om den finns, är då den minsta vägen som ledde till 0.

Här en rekursiv OCaml-funktion som motsvarar denna metod. Det returnerar Ingen, om ingen lösning finns.

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

Obs! Vi kan notera att den här proceduren kan beräkna flera gånger den ändring som är inställd för samma värde. I praktiken leder memoisering för att undvika dessa upprepningar till snabbare (mycket snabbare) resultat.

Aktivitetsval Problem

Problemet

Du har en uppsättning saker att göra (aktiviteter). Varje aktivitet har en starttid och en sluttid. Du får inte utföra mer än en aktivitet åt gången. Din uppgift är att hitta ett sätt att utföra maximalt antal aktiviteter.

Anta till exempel att du har ett urval av klasser att välja mellan.

Kom ihåg att du inte kan ta två klasser samtidigt. Det betyder att du inte kan ta klass 1 och 2 eftersom de delar en gemensam tid 10.30 till 11.00. Men du kan ta klass 1 och 3 eftersom de inte delar en gemensam tid. Så din uppgift är att ta maximalt antal klasser som möjligt utan överlappning. Hur kan du göra det?

Analys

Låt oss tänka efter lösningen med giriga tillvägagångssätt. För det första valde vi slumpmässigt någon metod och kontrollera att det fungerar eller inte.

• sortera aktiviteten efter starttid som betyder vilken aktivitet som startar först kommer vi att ta dem först. ta sedan först till sista från den sorterade listan och kontrollera att den kommer att korsas från tidigare aktiv aktivitet eller inte. Om den aktuella aktiviteten inte korsar den tidigare genomförda aktiviteten kommer vi att utföra aktiviteten annars utför vi inte. denna metod kommer att fungera i vissa fall som

sorteringsordningen är 4 -> 1 -> 2 -> 3. Aktiviteten 4 -> 1 -> 3 kommer att utföras och aktiviteten 2 hoppas över. den maximala 3 aktiviteten kommer att utföras. Det fungerar för denna typ av fall. men det kommer att misslyckas i vissa fall. Låter tillämpa denna metod för ärendet

Sorteringsordningen är 4 -> 1 -> 2 -> 3 och endast aktivitet 4 kommer att utföras men svaret kan vara aktivitet 1 -> 3 eller 2 -> 3 kommer att utföras. Så vår metod kommer inte att fungera för ovanstående fall. Låt oss försöka en annan strategi

• Sortera aktiviteten efter tidsvaraktighet som innebär att du utför den kortaste aktiviteten först. som kan lösa det tidigare problemet. Även om problemet inte är helt löst. Det finns fortfarande några fall som kan misslyckas med lösningen. tillämpa denna strategi på fallet.

Om vi sorterar aktiviteten efter tidsperiod kommer sorteringsordningen att vara 2 -> 3 ---> 1. och om vi utför aktivitet nr 2 först kan ingen annan aktivitet utföras. Men svaret är att utföra aktivitet 1 och sedan 3. Så vi kan utföra maximal 2 aktivitet. Så detta kan inte vara en lösning på det här problemet. Vi bör försöka en annan strategi.

Lösningen

• Sortera aktiviteten efter sluttid som betyder att aktiviteten avslutas först som kommer först. algoritmen anges nedan

1. Sortera aktiviteterna efter dess sluttid.
2. Om aktiviteten som ska utföras inte delar en gemensam tid med de aktiviteter som tidigare utförts, utför du aktiviteten.

Låter analysera det första exemplet

sortera aktiviteten efter dess sluttid, så sorteringsordning kommer att vara 1 -> 5 -> 2 -> 4 -> 3 .. svaret är 1 -> 3 dessa två aktiviteter kommer att utföras. ans det är svaret. här är sudo-koden.

1. sortera: aktiviteter
2. utför den första aktiviteten från den sorterade aktivitetslistan.
3. Set: Current_activity: = första aktivitet
4. set: end_time: = slut_tid för aktuell aktivitet
5. gå till nästa aktivitet om det finns, om inte finns avsluta.
6. om starttid för aktuell aktivitet <= sluttid: utför aktiviteten och gå till 4
7. annars: fick till 5.

se här för hjälp med kodning http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/