Greedy-Algorithmus

Ein Greedy-Algorithmus (im Englischen als greedy algorithm bekannt), auch Greedy-Methode genannt, ist eine algorithmische Strategie, die bei jedem Schritt die beste oder optimale (d. h. günstigste) Wahl im aktuellen Zustand trifft und hofft, zu einem global besten oder optimalen Ergebnis zu führen.

Greedy-AlgorithmusWie wir oft sagen, kümmert er sich nur um unmittelbare Vorteile und berücksichtigt nicht das Gesamtoptimum; die getroffene Wahl ist nur in gewissem Sinne eine lokal optimale Lösung.

Stellen Sie sich vor, Sie haben einen Haufen Münzen unterschiedlicher Nennwerte (zum Beispiel 1 Yuan, 5 Jiao, 1 Jiao) und müssen 1.8 Yuan mit möglichst wenigen Münzen begleichen.

Eine sehr natürliche Idee ist:Immer zuerst die Münze mit dem größten Nennwert nehmen,。

Nehmen Sie zuerst eine 1-Yuan-Münze, es bleiben 0.8 Yuan; dann nehmen Sie eine 5-Jiao-Münze, es bleiben 0.3 Yuan; schließlich nehmen Sie drei 1-Jiao-Münzen.

Während des gesamten Prozesses haben wir bei jedem Schrittdie Wahl getroffen, die aktuell am besten aussiehtDas ist der Kern des Greedy-Algorithmus.

Greedy-AlgorithmusEr ist wie eine kurzsichtige, aber entschlossene Person:

  • Wahl bei jedem SchrittTreffen Sie im aktuellen Zustand die Wahl, die optimal erscheint.
  • Berücksichtigt nicht das Gesamtbild: ohne die Auswirkungen dieser Wahl auf die Zukunft zu berücksichtigen
  • Erwartetes ErgebnisHoffnung, dass die lokal optimale Wahl zu einer global optimalen Lösung führen kann.

Praxisbeispiele:

  • Münzwechsel: immer zuerst die Münze mit dem größten Nennwert verwenden
  • Hill-Climbing: immer in die steilste Richtung bewegen
  • Shopping: immer das aktuell günstigste Produkt kaufen
  • Routenauswahl: immer den aktuell kürzesten Pfad wählen

Eigenschaften des Greedy-Algorithmus

  • Greedy-AuswahleigenschaftDie optimale Lösung bei jedem Schritt kann aus den lokal optimalen Lösungen der vorherigen Schritte abgeleitet werden. Spätere Entscheidungen beeinflussen frühere Entscheidungen nicht.
  • Optimale SubstrukturDie optimale Lösung eines Problems enthält die optimalen Lösungen seiner Teilprobleme. Dies ist auch eine Eigenschaft der dynamischen Programmierung, aber ein Greedy-Algorithmus wählt bei jedem Schritt gierig die optimale Lösung eines Teilproblems.
Funktionen Beschreibung Vorteile Nachteile
Lokales Optimum Bei jedem Schritt die aktuelle optimale Lösung wählen Einfach und intuitiv Möglicherweise nicht global optimal
Irreversibel Nach der Wahl nicht bereuen können Schnelle Entscheidungsfindung Neigt dazu, in lokalen Optima festzustecken
Effizienz Hat normalerweise eine geringe Zeitkomplexität Sehr praxisnah Begrenzte Anwendbarkeit
Einfache Implementierung Die Logik ist klar und leicht verständlich Einfach zu implementieren Korrektheit muss bewiesen werden

Unterschiede zur dynamischen Programmierung

Dies ist ein Punkt, den Anfänger oft verwirrend finden. Vergleichen wir sie in einer Tabelle:

Funktionen Greedy-Algorithmus Dynamische Programmierung
Entscheidungsgrundlage Triff bei jedem Schritt die aktuell optimale Wahl,Kein Backtracking。 Die Wahl in jedem Schritt hängt von der Lösung der Teilprobleme ab, speichert Zwischenergebnisse und kann mehrere Optionen vergleichen.
Garantie der optimalen Lösung Es liefert möglicherweise nicht die globale optimale Lösung; das Problem selbst muss die Greedy-Auswahl-Eigenschaft besitzen. Üblicherweise kann die global optimale Lösung erhalten werden.
Effizienz Effizient, üblicherweise mit geringerer Zeitkomplexität. Relativ gering, da überlappende Teilprobleme gelöst werden müssen.
Anwendbare Szenarien Das Problem besitzt die Greedy-Auswahl-Eigenschaft und optimale Unterstruktur, wie bei der Huffman-Kodierung und minimalen Spannbäumen. Das Problem besitzt eine optimale Unterstruktur und überlappende Teilprobleme, wie beim Rucksackproblem und bei kürzesten Wegen.

Einfach gesagt,Dynamische Programmierung ist „erst denken, dann handeln“ und opfert unmittelbare Interessen für langfristige Vorteile; Greedy-Algorithmen sind „heute essen, trinken und fröhlich sein“ und verfolgen nur unmittelbare Vorteile.

Grundgerüst des Greedy-Algorithmus

Greedy-Algorithmen haben keine feste Codevorlage, aber ihre Idee lässt sich in den folgenden Schritten zusammenfassen:

  1. Ein mathematisches Modell erstellen: das reale Problem in ein mathematisches Problem abstrahieren.
  2. Definiere eine Greedy-StrategieBestimme das Kriterium für die Wahl der „optimalen Lösung“ bei jedem Schritt. Dies ist der Kern und die Schwierigkeit des Algorithmus.
  3. Beweise die Greedy-StrategieBeweise, dass die definierte Greedy-Strategie zu einer global optimalen Lösung führen kann (optional, aber wichtig; bei Algorithmusproblemen musst du normalerweise ihre Korrektheit verstehen).
  4. Iteratives LösenGemäß der Strategie trifft man ausgehend vom Anfangszustand Schritt für Schritt Greedy-Entscheidungen, bis eine Lösung für das Problem gefunden ist.

Ein allgemeines Pseudocode-Gerüst sieht wie folgt aus:

Beispiel

def greedy_algorithm(problem):
    # 1. Initialisierung: kann Sortieren, Erstellen eines Ergebniscontainers usw. umfassen.
    solution = []
    # 2. Über alle Optionen iterieren; normalerweise musst du zuerst nach einer Regel sortieren.
    for item in sorted(problem.items, key=Greedy-Strategie-Regel):
        # 3. Greedy-Auswahl: Wenn die aktuelle Auswahl die Bedingung erfüllt, übernimm sie.
        if is_feasible(solution, item):
            solution.append(item)
    # 4. Gib die endgültig konstruierte Lösung zurück
    return solution

Klassische Probleme und Codebeispiele

Lassen Sie uns die Anwendung von Greedy-Algorithmen anhand einiger klassischer Probleme kennenlernen. Für jedes Problem werden wir: 1) das Problem und die Greedy-Strategie analysieren; 2) vollständigen Code bereitstellen; 3) eine zeilenweise Erklärung bereitstellen.

Beispiel 1: Münzwechselproblem

Problembeschreibung: Angenommen, das Münzsystem ist [100, 50, 20, 10, 5, 1] (Einheit: Cent), und wir müssen Wechselgeld herausgebenamountCent, finden Sie die minimale Anzahl benötigter Münzen.

Greedy-Strategie：Wähle jedes Mal die größte Münze, deren Nennwert den verbleibenden Betrag nicht überschreitet.Für das RMB-Währungssystem ist diese Strategie wirksam.

Code-Implementierung：

Beispiel

def coin_change_greedy(coins, amount):
    """
Verwenden Sie den Greedy-Algorithmus, um das Münzwechselproblem zu lösen (für ein bestimmtes Münzsystem)
:param coins: list[int], Liste der Münznennwerte, sollte in absteigender Reihenfolge sortiert sein
:param amount: int, Gesamtbetrag, für den Wechselgeld herausgegeben werden soll
:return: list[int], Liste der verwendeten Münznennwerte
    """
    coins.sort(reverse=True)  # Sicherstellen, dass die Münzen nach Nennwert vom höchsten zum niedrigsten sortiert sind
    result = []  # Wird verwendet, um die Münzen für die Wechselgeldausgabe zu speichern
    remaining = amount  # Verbleibender Betrag, für den Wechselgeld benötigt wird

    for coin in coins:
        # Wenn der aktuelle Münznennwert kleiner oder gleich dem verbleibenden Betrag ist, ihn so oft wie möglich verwenden
        while remaining >= coin:
            result.append(coin)
            remaining -= coin  # Den aktuellen Münznennwert vom verbleibenden Betrag abziehen

    # Prüfen, ob das Wechselgeld exakt herausgegeben werden kann
    if remaining == 0:
        return result
    else:
        # Für Fälle, in denen exaktes Wechselgeld nicht herausgegeben werden kann (obwohl dies in diesem Münzsystem nicht vorkommen wird)
        return None

# Testdaten
test_coins = [100, 50, 20, 10, 5, 1]
test_amount = 186  # 1 yuan 8 jiao 6 fen

change = coin_change_greedy(test_coins, test_amount)
print(f"Wechselgeld für {test_amount} fen, benötigte Münzen: {change}")
print(f"Anzahl der Münzen: {len(change)}")
# Ausgabe: Wechselgeld für 186 fen, benötigte Münzen: [100, 50, 20, 10, 5, 1]
# Anzahl der Münzen: 6

Code-Erklärung：

  • Zeile 8:coins.sort(reverse=True)Dies ist die entscheidende Vorbereitung für die Greedy-Strategie und stellt sicher, dass wir immer zuerst größere Stückelungen berücksichtigen.
  • Zeilen 12-15:whileDie Schleife stellt sicher, dass wir die aktuelle Stückelung weiter verwenden, solange sie noch verwendet werden kann; dies implementiert die gierige Auswahl von "so vielen wie möglich."
  • Zeilen 18-22: Prüfe das Endergebnis, um sicherzustellen, dass der Betrag genau übereinstimmt.

Wichtiger Hinweis: Greedy-Algorithmus zur Lösung des WechselgeldproblemsErzeugt nicht immer die optimale LösungWenn das Münzsystem beispielsweise [25, 20, 10, 5, 1] ist und Sie 40 Cent herausgeben müssen, würde die Greedy-Methode 25+10+5 wählen (drei Münzen), aber die optimale Lösung ist 20+20 (zwei Münzen).Nur bei bestimmten Währungssystemen (wie RMB) ist die Greedy-Strategie effektiv.

Beispiel 2: Intervallplanungsproblem

ProblembeschreibungGegeben viele Besprechungen (jeweils mit einer Startzeit und einer Endzeit), wie sollten Sie sie anordnen, um die Anzahl der Besprechungen zu maximieren, die Sie in einem Besprechungsraum abhalten können?

Greedy-Strategie：Wählen Sie jedes Mal die Besprechung mit der frühesten EndzeitDadurch bleibt mehr Zeit für spätere Besprechungen.

Code-Implementierung：

Beispiel

def interval_scheduling(intervals):
    """
Lösen des Problems der maximalen nicht überlappenden Intervalle (Intervallplanung)
:param intervals: Liste von [start, end], Intervallliste
:return: Liste von [start, end], Liste der ausgewählten Intervalle
    """
    # 1. Nach Endzeit in aufsteigender Reihenfolge sortieren
    intervals_sorted = sorted(intervals, key=lambda x: x[1])
   
    selected = []  # Speichere die ausgewählten Intervalle
    last_end_time = -float('inf')  # Endzeit des zuletzt ausgewählten Intervalls initialisieren
   
    for interval in intervals_sorted:
        start, end = interval
        # 2. Greedy-Auswahl: Wenn die Startzeit des aktuellen Intervalls nicht früher als die Endzeit des zuvor ausgewählten Intervalls liegt, wähle es aus
        if start >= last_end_time:
            selected.append(interval)
            last_end_time = end  # Letzte Endzeit aktualisieren
   
    return selected

# Testdaten: Jede Unterliste stellt eine Besprechung [Startzeit, Endzeit] dar
test_intervals = [
    [1, 3], [2, 4], [3, 5], [4, 6], [5, 7],
    [1, 2], [2, 3], [1, 4]
]

result = interval_scheduling(test_intervals)
print(Maximale Anzahl an Besprechungen, die geplant werden können (nach Sortierung nach Endzeit):)
for meeting in result:
    print(fBesprechung [{meeting[0]}, {meeting[1]}])
print(fInsgesamt {len(result)} Besprechungen)
# Eine mögliche Ausgabe (da die Reihenfolge nach dem Sortieren abweichen kann, die Anzahl aber optimal ist):
# Besprechung [1, 2]
# Besprechung [2, 3]
# Besprechung [3, 5] oder [4, 6], usw.
# Insgesamt 4 Besprechungen

Code-Erklärung：

  • Zeile 10:sorted(intervals, key=lambda x: x[1])Dies ist der Kern der Umsetzung der Greedy-Strategie: Sortieren nach Endzeit.
  • Zeilen 16-19:if start >= last_end_timeDies ist eine Machbarkeitsprüfung, die sicherstellt, dass sich die aktuelle Besprechung nicht mit den ausgewählten Besprechungen überschneidet.
  • Die Zeitkomplexität dieses Algorithmus ist O(n log n), hauptsächlich aufgrund der Sortierung.

Beispiel 3: Huffman-Codierung – Konzept und vereinfachte Implementierung

Huffman-Codierung ist ein Greedy-Algorithmus zur verlustfreien Datenkompression. Die Kernidee ist:Zeichen mit höheren Häufigkeiten kürzere Codes und Zeichen mit niedrigeren Häufigkeiten längere Codes zuzuweisen.。

Greedy-StrategieWiederholt die beiden Knoten mit den kleinsten Häufigkeiten zusammenführen, um einen Binärbaum aufzubauen.

Da eine vollständige Implementierung recht lang ist, zeigen wir hier ihren Kernprozess des Greedy-Zusammenfügens:

Beispiel

import heapq

class Node:
    """Klasse für Huffman-Baumknoten"""
    def __init__(self, char, freq):
        self.char = char  # Zeichen (nur Blattknoten)
        self.freq = freq  # Häufigkeit
        self.left = None
        self.right = None
   
    # Um den Vergleich im Heap zu ermöglichen, Vergleichsmethoden definieren
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(char_freq):
    """
Huffman-Baum konstruieren
:param char_freq: dict, Zeichen und ihre Häufigkeiten, z. B. {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
:return: Node, der Wurzelknoten des Huffman-Baums
    """
    # 1. Initialisierung: Für jedes Zeichen einen Blattknoten erstellen und ihn in einen Min-Heap (Prioritätswarteschlange) einfügen
    heap = [Node(char, freq) for char, freq in char_freq.items()]
    heapq.heapify(heap)  # Die Liste in einen Min-Heap umwandeln
   
    # 2. Greedy-Zusammenführung: wenn mehr als ein Knoten im Heap ist
    while len(heap) > 1:
        # Die beiden Knoten mit den kleinsten Häufigkeiten entnehmen
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
       
        # Erzeuge einen neuen internen Knoten, dessen Häufigkeit die Summe der Häufigkeiten der Kinder ist
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
       
        # Schiebe den neuen Knoten zurück in den Heap
        heapq.heappush(heap, merged)
   
    # Der letzte verbleibende Knoten im Heap ist die Wurzel des Huffman-Baums
    return heap[0] if heap else None

# Testdaten
test_freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
root = build_huffman_tree(test_freq)
print("Huffman-Baum-Konstruktion abgeschlossen! Wurzelhäufigkeit =", root.freq if root else 0)
# Ausgabe: Huffman-Baum-Konstruktion abgeschlossen! Wurzelhäufigkeit = 100

Algorithmus-VisualisierungDie folgende Abbildung zeigt die ersten paar Zusammenführungsschritte beim Aufbau des Huffman-Baums unter Verwendung der obigen Testdaten:

Illustrierte ErklärungDer Algorithmus wählt stets die beiden Knoten mit den kleinsten Häufigkeiten aus allen verfügbaren Knoten aus (anfangs Blattknoten, später auch interne Knoten) und führt sie zu einem neuen internen Knoten zusammen. Dieser Vorgang wird wiederholt, bis ein vollständiger Binärbaum entstanden ist. Die Blattknoten dieses Baums entsprechen den ursprünglichen Zeichen, und der Pfad von der Wurzel zu einem Blatt (linker Zweig ist 0, rechter Zweig ist 1) ist der Huffman-Code für dieses Zeichen.

Korrektheitsbeweis des Greedy-Algorithmus

Wie stellt man fest, ob ein Problem mit einem Greedy-Algorithmus gelöst werden kann? Üblicherweise muss man die folgenden zwei Punkte beweisen:

  1. Greedy-AuswahleigenschaftDurch mathematische Induktion oder Widerspruchsbeweis kann gezeigt werden, dass die optimale Wahl im ersten Schritt in einer global optimalen Lösung enthalten ist.
  2. Optimale SubstrukturBeweisen Sie, dass das ursprüngliche Problem nach der ersten Greedy-Wahl auf ein Problem kleineren Umfangs reduziert wird.Teilprobleme desselben Typs。

mitIntervallplanungsproblemBeweisidee am Beispiel von ...:

  • Greedy-WahlDas Intervall mit der frühesten Endzeit unter allen Intervallen seii. Es existiert eine optimale Lösung, die das Intervall ... enthälti。
    • Beweis: Angenommen, eine optimale Lösung enthält es nicht.i. Das erste Intervall in dieser optimalen Lösung sei ...j. Denniendet am frühesten, also ersetze ... durch ...iersetzenjEs steht nicht in Konflikt mit anderen Intervallen, und die Größe der Lösung bleibt unverändert, also enthält sieiDie resultierende Lösung ist ebenfalls optimal.
  • Optimale Teilstruktur: Bei der Auswahl von IntervalleniDanach ist das verbleibende Problem, unter allen Intervallen, die ... mit ...idie optimale Lösung unter nicht überlappenden Intervallen zu finden. Dies stellt ein Teilproblem des ursprünglichen Problems dar.

Übungsaufgaben

Versuchen Sie jetzt, die folgenden Probleme mit dem Greedy-Algorithmus zu lösen, um Ihr Verständnis zu festigen.

Übung 1: Jump Game

Problem: Gegeben sei ein nicht-negatives Ganzzahl-ArraynumsDu befindest dich anfangs am ersten Index des Arrays. Jedes Element im Array stellt die maximale Länge dar, die du von dieser Position aus springen kannst. Bestimme, ob du den letzten Index erreichen kannst.Beispiel：nums = [2,3,1,1,4], zurückgebenTrue(Springe 1 Schritt von Index 0 zu Index 1, dann springe 3 Schritte zum letzten Index).Hinweis zur Greedy-StrategieAnstatt zu simulieren, wie weit bei jedem Schritt gesprungen wird, halte eineam weitesten erreichbare Position。

Übung 2: Kekse zuweisen

ProblemEs gibt eine Gruppe von Kindern und einen Stapel Kekse; jedes Kind hat einen Appetitwertg[i], jeder Keks hat eine Größes[j]Ein Kind ist nur zufrieden, wenn die Keksgröße >= dem Appetit des Kindes ist. Finde die maximale Anzahl an Kindern, die zufrieden gestellt werden können.Beispiel：g = [1,2,3], s = [1,1], Ausgabe1。 Hinweis zur Greedy-Strategie: Um mehr Kinder zufrieden zu stellen,verwende den kleinsten Keks, um das Kind mit dem kleinsten Appetit zufrieden zu stellen.(oder denke andersherum darüber nach).

Übung 3: Bester Zeitpunkt zum Kaufen und Verkaufen von Aktien II

Problem: Gegeben sei ein Arrayprices, wobeiprices[i]ist der ... einer gegebenen Aktie am ...iDer Preis für jeden Tag. Du darfst so viele Transaktionen abschließen, wie du möchtest (d. h. eine Aktie kaufen und verkaufen), aber du darfst nicht gleichzeitig an mehreren Transaktionen teilnehmen (du musst die vorherige Aktie verkaufen, bevor du erneut kaufst). Berechne den maximalen Gewinn, den du erzielen kannst.Beispiel：prices = [7,1,5,3,6,4], Ausgabe7(Bei 1 kaufen und bei 5 verkaufen, Gewinn 4; bei 3 kaufen und bei 6 verkaufen, Gewinn 3; Gesamtgewinn 7).Hinweis zur Greedy-StrategieDer Gewinn kann in tägliche Preisunterschiede zerlegt werden. Solangeder heutige Preis höher ist als der gestrige, nimm diese Differenz als Gewinn.。

Weitere Erweiterungen