Lesson 5 greedy algo Flashcards
Was ist ein Greedy-Algorithmus?
Ein Greedy-Algorithmus trifft bei jedem Schritt eine lokale, optimale Entscheidung, in der Hoffnung, dass diese zum globalen Optimum führt. Das bedeutet, dass in jedem Moment die beste sofort verfügbare Option gewählt wird, ohne Rücksicht auf spätere Konsequenzen oder eine Gesamtstrategie. Greedy-Algorithmen sind besonders nützlich bei Problemen, bei denen eine effiziente Lösung gesucht wird, obwohl sie nicht immer die globale optimale Lösung garantieren können. Beispiele sind das Rucksack-Problem und die Huffman-Kodierung.
Was sind typische Eigenschaften von Greedy-Algorithmen?
Typische Eigenschaften von Greedy-Algorithmen umfassen:
- Lokal optimal: In jedem Schritt wird die sofort beste Lösung gewählt.
- Einfachheit: Greedy-Algorithmen sind in der Regel einfach zu implementieren.
- Effizienz: Sie haben oft eine schnelle Laufzeit, da sie keine komplexen Berechnungen oder Rückverfolgungen erfordern.
- Keine Garantie für globale Optimalität: Greedy-Algorithmen führen nicht immer zu einer global optimalen Lösung, da sie keine Rücksicht auf zukünftige Entscheidungen nehmen.
Was ist das Travelling Salesman Problem (TSP)?
Das Travelling Salesman Problem (TSP) besteht darin, die kürzeste mögliche Route zu finden, die alle Städte genau einmal besucht und zum Ausgangspunkt zurückkehrt. Dieses Problem kann als ungerichteter, gewichteter Graph modelliert werden, wobei die Knoten Städte und die Kanten die Entfernungen zwischen den Städten darstellen.
Wie kann das Travelling Salesman Problem als Graph modelliert werden?
Das TSP wird als ungerichteter, vollständiger, gewichteter Graph modelliert. Dabei repräsentiert jeder Knoten eine Stadt, und jede Kante repräsentiert die Entfernung zwischen zwei Städten. Wenn zwei Städte nicht direkt verbunden sind, wird der entsprechenden Kante ein sehr großes Gewicht zugewiesen, um diese Verbindung unattraktiv zu machen.
Was ist der Nearest-Neighbor-Algorithmus?
Der Nearest-Neighbor-Algorithmus ist ein Greedy-Algorithmus zur Annäherung an das TSP. Er beginnt an einem Startknoten und wählt immer den nächstgelegenen unbesuchten Knoten, bis alle Knoten besucht wurden. Schließlich kehrt er zum Startknoten zurück. Obwohl dieser Algorithmus eine schnelle Lösung bietet, garantiert er nicht die optimale Lösung.
Was ist das Rucksack-Problem?
Das Rucksack-Problem besteht darin, eine Auswahl von Gegenständen zu treffen, die einen maximalen Gesamtwert bieten und in einen Rucksack mit begrenztem Fassungsvermögen passen. Jeder Gegenstand hat ein Gewicht und einen Wert, und es geht darum, die Kombination zu finden, die den höchsten Gesamtwert hat, ohne die Gewichtsbeschränkung zu überschreiten.
Was ist der Profitabilitätsindex (PI) im Kontext des Rucksack-Problems?
Der Profitabilitätsindex (PI) gibt an, wie wertvoll ein Gegenstand im Verhältnis zu seinem Gewicht ist und wird berechnet als ( PI = rac{Wert}{Gewicht} ). Beim Greedy-Algorithmus für das fraktionale Rucksack-Problem werden die Gegenstände in absteigender Reihenfolge ihres PI ausgewählt.
Was ist das fraktionale Rucksack-Problem?
Beim fraktionalen Rucksack-Problem kann man Teile von Gegenständen in den Rucksack legen, anstatt nur ganze Gegenstände. Dies bedeutet, dass man, wenn der Rucksack nicht mehr genug Platz für einen ganzen Gegenstand hat, den Gegenstand aufteilen kann, um den verbleibenden Platz optimal zu nutzen.
Was ist das Rückgeld-Problem und wie wird es gelöst?
Das Rückgeld-Problem besteht darin, eine bestimmte Geldsumme mit möglichst wenigen Münzen auszuzahlen. Der Greedy-Algorithmus löst dieses Problem, indem er immer die größte verfügbare Münze wählt, die noch in den Restbetrag passt.
Was ist ein Präfix-Code?
Ein Präfix-Code ist ein Code, bei dem kein Codewort der Präfix (Anfang) eines anderen Codewortes ist. Dadurch kann der Code eindeutig dekodiert werden, ohne dass ein Trennzeichen zwischen den Codewörtern notwendig ist. Präfix-Codes werden häufig in der Datenkompression verwendet, um redundante Informationen zu eliminieren.
Was ist die Huffman-Kodierung?
Die Huffman-Kodierung ist ein Greedy-Algorithmus zur Erstellung von Präfix-Codes, der verwendet wird, um Daten auf der Grundlage ihrer Häufigkeit zu komprimieren. Häufigere Zeichen erhalten kürzere Codes, während seltenere Zeichen längere Codes erhalten. Dies führt zu einer effizienten Kodierung, die die durchschnittliche Codewortlänge minimiert.
Welche Anwendungen hat die Huffman-Kodierung?
Die Huffman-Kodierung wird häufig in der verlustfreien Datenkompression verwendet. Sie findet Anwendung in Dateiformaten wie JPEG und MP3, wo sie dazu beiträgt, die Größe von Bild- und Audiodateien zu reduzieren.
