algorithm
Gierige Algorithmen

Bemerkungen

Kontinuierliches Rucksackproblem

Gegebene Gegenstände als (value, weight) wir in einen Rucksack (Behälter) mit einer Kapazität k legen. Hinweis! Wir können Gegenstände zerbrechen, um den Wert zu maximieren!

Beispieleingabe:

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

Erwartete Ausgabe:

maximumValueOfItemsInK = 20;

Algorithmus:

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

Huffman-Code ist ein bestimmter Typ eines optimalen Präfixcodes, der üblicherweise für die verlustfreie Datenkompression verwendet wird. Es komprimiert Daten sehr effektiv und spart je nach den Eigenschaften der zu komprimierenden Daten 20% bis 90% Speicherplatz. Wir betrachten die Daten als eine Folge von Zeichen. Der gierige Algorithmus von Huffman verwendet eine Tabelle, die angibt, wie oft jedes Zeichen auftritt (dh seine Häufigkeit), um eine optimale Art der Darstellung jedes Zeichens als binäre Zeichenfolge aufzubauen. Huffman-Code wurde 1951 von David A. Huffman vorgeschlagen.

Angenommen, wir haben eine Datendatei mit 100.000 Zeichen, die wir kompakt speichern möchten. Wir gehen davon aus, dass sich in dieser Datei nur 6 verschiedene Zeichen befinden. Die Häufigkeit der Zeichen ergibt sich aus:

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

Wir haben viele Möglichkeiten, eine solche Informationsdatei darzustellen. Hier betrachten wir das Problem des Entwerfens eines binären Zeichencodes, in dem jedes Zeichen durch eine eindeutige binäre Zeichenfolge dargestellt wird, die wir ein Codewort nennen .

Der konstruierte Baum liefert uns:

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

Wenn wir einen Code mit fester Länge verwenden , benötigen wir drei Bits, um 6 Zeichen darzustellen. Diese Methode erfordert 300.000 Bits, um die gesamte Datei zu codieren. Nun ist die Frage, können wir es besser machen?

Ein Code mit variabler Länge kann erheblich besser sein als ein Code mit fester Länge, indem häufigen Zeichen kurze Codewörter und seltenen Zeichen lange Codewörter gegeben werden. Dieser Code erfordert: (45 X 1 + 13 X 3 + 12 X 3 + 16 X 3 + 9 X 4 + 5 X 4) X 1000 = 224000 Bits zur Darstellung der Datei, wodurch ca. 25% des Speichers eingespart werden.

Eine Sache zu bedenken, betrachten wir hier nur Codes, bei denen kein Codewort auch ein Präfix eines anderen Codewortes ist. Diese werden Präfixcodes genannt. Für die Codierung mit variabler Länge codieren wir die dreistellige Datei abc als 0.101.100 = 0101100, wobei "." bezeichnet die Verkettung.

Präfixcodes sind wünschenswert, weil sie die Decodierung vereinfachen. Da kein Codewort ein Präfix eines anderen ist, ist das Codewort, mit dem eine codierte Datei beginnt, eindeutig. Wir können das anfängliche Codewort einfach identifizieren, in das ursprüngliche Zeichen zurückübersetzen und den Decodierungsvorgang für den Rest der codierten Datei wiederholen. Zum Beispiel wird 001011101 eindeutig als 0.0.101.1101 analysiert, wobei aabe dekodiert wird . Kurz gesagt, alle Kombinationen von binären Darstellungen sind eindeutig. Wenn zum Beispiel ein Buchstabe mit 110 bezeichnet wird, wird kein anderer Buchstabe mit 1101 oder 1100 bezeichnet. Dies liegt daran, dass Sie verwirrt sein könnten, ob Sie 110 wählen oder das nächste Bit verketten und dieses auswählen möchten.

Kompressionstechnik:

Die Technik funktioniert durch Erstellen eines binären Knotenbaums. Diese können in einem regulären Array gespeichert werden, dessen Größe von der Anzahl der Symbole abhängt, n . Ein Knoten kann entweder ein Blattknoten oder ein interner Knoten sein . Anfänglich sind alle Knoten Blattknoten, die das Symbol selbst, seine Häufigkeit und optional eine Verknüpfung zu seinen Kindknoten enthalten. Konventionell repräsentiert Bit '0' linkes Kind und Bit '1' rechtes Kind. Die Prioritätswarteschlange wird zum Speichern der Knoten verwendet, wodurch der Knoten beim Poppen die niedrigste Häufigkeit erhält. Der Prozess wird nachfolgend beschrieben:

1. Erstellen Sie für jedes Symbol einen Blattknoten und fügen Sie es der Prioritätswarteschlange hinzu.
2. Es gibt mehr als einen Knoten in der Warteschlange:
   1. Entfernen Sie die beiden Knoten mit der höchsten Priorität aus der Warteschlange.
   2. Erstellen Sie einen neuen internen Knoten mit diesen beiden Knoten als untergeordneter Elemente und mit einer Häufigkeit, die der Summe der Frequenz der beiden Knoten entspricht.
   3. Fügen Sie den neuen Knoten der Warteschlange hinzu.
3. Der verbleibende Knoten ist der Wurzelknoten und der Huffman-Baum ist abgeschlossen.

Für unser Beispiel:

Der Pseudo-Code sieht folgendermaßen aus:

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

Obwohl für die lineare Zeit eine sortierte Eingabe gegeben ist, erfordert die Verwendung dieses Algorithmus im Allgemeinen bei einer beliebigen Eingabe eine Vorsortierung. Da die Sortierung im Allgemeinen O (nlogn) -Zeit benötigt , weisen beide Verfahren die gleiche Komplexität auf.

Da hier n die Anzahl der Symbole im Alphabet ist, die typischerweise sehr klein ist (im Vergleich zur Länge der zu codierenden Nachricht), ist die Zeitkomplexität bei der Auswahl dieses Algorithmus nicht sehr wichtig.

Dekompressionstechnik:

Der Dekomprimierungsprozess ist einfach eine Frage des Übersetzens des Präfixkodestroms in einen individuellen Bytewert, üblicherweise durch Durchlaufen des Huffman-Baumknotens für Knoten, wenn jedes Bit aus dem Eingabestrom gelesen wird. Das Erreichen eines Blattknotens beendet notwendigerweise die Suche nach diesem bestimmten Byte-Wert. Der Blattwert steht für das gewünschte Zeichen. Normalerweise wird der Huffman-Baum mit statistisch angepassten Daten für jeden Komprimierungszyklus erstellt. Daher ist die Rekonstruktion relativ einfach. Ansonsten müssen die Informationen zum Wiederherstellen des Baums separat gesendet werden. Der 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

Gierige Erklärung:
Die Huffman-Codierung untersucht das Vorkommen jedes Zeichens und speichert es optimal als binäre Zeichenfolge. Die Idee ist, den eingegebenen Zeichen Codes mit variabler Länge zuzuordnen. Die Länge der zugewiesenen Codes basiert auf den Frequenzen der entsprechenden Zeichen. Wir erstellen einen binären Baum und bearbeiten ihn von unten nach oben, sodass die wenigsten zwei häufigen Zeichen so weit wie möglich von der Wurzel entfernt sind. Auf diese Weise erhält das häufigste Zeichen den kleinsten Code und das am wenigsten häufige Zeichen den größten Code.

Verweise:

• Einführung in Algorithmen - Charles E. Leiserson, Clifford Stein, Ronald Rivest und Thomas H. Cormen
• Huffman-Kodierung - Wikipedia
• Diskrete Mathematik und ihre Anwendungen - Kenneth H. Rosen

Problem der Veränderung

Ist ein Geldsystem gegeben, ist es möglich, eine Menge von Münzen zu geben und wie man einen minimalen Satz von Münzen finden kann, der dieser Menge entspricht.

Kanonische Geldsysteme. Für einige Geldsysteme, wie wir sie im wirklichen Leben verwenden, funktioniert die "intuitive" Lösung perfekt. Wenn zum Beispiel die verschiedenen Euro-Münzen und Banknoten (außer Cents) 1 €, 2 €, 5 €, 10 € betragen, wird die höchste Münze oder Rechnung bis zum Erreichen des Betrags ausgegeben, und eine Wiederholung dieses Verfahrens führt zu einem minimalen Münzensatz .

Das können wir mit OCaml rekursiv machen:

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

Diese Systeme sind so konzipiert, dass Änderungen leicht gemacht werden können. Das Problem wird schwieriger, wenn es um ein beliebiges Geldsystem geht.

Allgemeiner Fall. Wie 99 € mit Münzen von 10 €, 7 € und 5 € geben? Wenn man Münzen von 10 € gibt, bis 9 € übrig sind, führt dies offensichtlich zu keiner Lösung. Schlimmer noch, dass es keine Lösung gibt. Dieses Problem ist in der Tat np-hart, aber es gibt akzeptable Lösungen, die Greyness und Memoisierung vermischen. Die Idee ist, alle Möglichkeiten zu erkunden und die mit der minimalen Anzahl von Münzen auszuwählen.

Um einen Betrag X> 0 zu erhalten, wählen wir ein Stück P im Geldsystem aus und lösen dann das Unterproblem, das XP entspricht. Wir versuchen dies für alle Teile des Systems. Die Lösung ist, falls vorhanden, der kleinste Pfad, der zu 0 führte.

Hier eine rekursive OCaml-Funktion, die dieser Methode entspricht. Wenn keine Lösung vorhanden ist, wird None zurückgegeben.

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

Hinweis : Wir können feststellen, dass diese Prozedur die für einen Wert festgelegte Änderung möglicherweise mehrmals berechnet. In der Praxis führt die Verwendung von Memoization zur Vermeidung dieser Wiederholungen zu schnelleren (wesentlich schnelleren) Ergebnissen.

Aktivitätsauswahlproblem

Das Problem

Sie haben eine Reihe von Aktivitäten (Aktivitäten) zu erledigen. Jede Aktivität hat eine Startzeit und eine Endzeit. Sie dürfen nicht mehr als eine Aktivität gleichzeitig ausführen. Ihre Aufgabe ist es, einen Weg zu finden, die maximale Anzahl von Aktivitäten auszuführen.

Angenommen, Sie haben eine Auswahl an Klassen zur Auswahl.

Denken Sie daran, dass Sie nicht zwei Kurse gleichzeitig besuchen können. Das bedeutet, dass Sie die Klassen 1 und 2 nicht nehmen können, weil sie eine gemeinsame Zeit von 10:30 bis 11:00 Uhr haben. Sie können jedoch die Klassen 1 und 3 nehmen, da sie keine gemeinsame Zeit haben. Ihre Aufgabe ist es daher, möglichst viele Klassen ohne Überschneidungen zu belegen. Wie kannst du das machen?

Analyse

Lassen Sie uns durch gierige Herangehensweise nachdenken. Zuerst haben wir zufällig einen Ansatz gewählt und überprüft, ob das funktioniert oder nicht.

• sortieren Sie die Aktivität nach Startzeit , dh welche Aktivität beginnt zuerst, werden wir sie zuerst nehmen. Nehmen Sie dann die erste bis letzte aus der sortierten Liste und prüfen Sie, ob sie sich mit der vorherigen Aktivität überschneiden oder nicht. Wenn sich die aktuelle Aktivität nicht mit der zuvor durchgeführten Aktivität überschneidet, führen wir die Aktivität aus. Andernfalls führen wir keine Aktivität aus. Dieser Ansatz wird in einigen Fällen funktionieren

Die Sortierreihenfolge lautet 4 -> 1 -> 2 -> 3. Die Aktivität 4 -> 1 -> 3 wird ausgeführt und die Aktivität 2 wird übersprungen. Es werden maximal 3 Aktivitäten ausgeführt. Es funktioniert für diese Art von Fällen. In einigen Fällen wird dies jedoch fehlschlagen. Wenden wir diesen Ansatz für den Fall an

Die Sortierreihenfolge lautet 4 -> 1 -> 2 -> 3 und nur die Aktivität 4 wird ausgeführt, die Antwort kann jedoch die Aktivität 1 -> 3 oder 2 -> 3 sein. Daher funktioniert unser Ansatz für den oben genannten Fall nicht. Versuchen wir einen anderen Ansatz

• Sortieren Sie die Aktivität nach der Zeitdauer , dh, führen Sie zuerst die kürzeste Aktivität aus. das kann das vorige Problem lösen. Das Problem ist zwar nicht vollständig gelöst. Es gibt noch einige Fälle, in denen die Lösung fehlschlagen kann. wenden Sie diesen Ansatz auf den folgenden Fall an.

Wenn wir die Aktivität nach Zeitdauer sortieren, lautet die Sortierreihenfolge 2 -> 3 ---> 1. und wenn wir zuerst Tätigkeit Nr. 2 ausführen, kann keine andere Tätigkeit ausgeführt werden. Die Antwort lautet jedoch: Aktivität 1 durchführen und dann 3. Wir können also maximal 2 Aktivitäten ausführen. Dies kann also keine Lösung für dieses Problem sein. Wir sollten einen anderen Ansatz versuchen.

Die Lösung

• Sortieren Sie die Aktivität nach der Endzeit. Dies bedeutet, dass die Aktivität an erster Stelle endet. Der Algorithmus ist unten angegeben

1. Sortieren Sie die Aktivitäten nach den Endzeiten.
2. Wenn die auszuführende Aktivität keine gemeinsame Zeit mit den zuvor durchgeführten Aktivitäten hat, führen Sie die Aktivität aus.

Lassen Sie uns das erste Beispiel analysieren

sortiere die Aktivität nach ihren Endzeiten. Die Sortierreihenfolge lautet also 1 -> 5 -> 2 -> 4 -> 3. Die Antwort ist 1 -> 3. Diese beiden Aktivitäten werden ausgeführt. Das ist die Antwort. Hier ist der Sudo-Code.

1. sortieren: Aktivitäten
2. Erste Aktivität aus der sortierten Liste der Aktivitäten ausführen.
3. Set: Current_activity: = erste Aktivität
4. set: end_time: = end_time der aktuellen Aktivität
5. gehe zur nächsten Aktivität, falls vorhanden, falls nicht vorhanden, abbrechen
6. Wenn start_time der aktuellen Aktivität <= end_time: Die Aktivität ausführen und mit 4 fortfahren
7. sonst: habe zu 5.

Codierungshilfe finden Sie hier http://www.geeksforgeeks.org/greedy-algorithms-set-1-activity-selection-problem/