logo

TechCodeview

Gierige Algorithmen

Gierige Algorithmen sind eine Klasse von Algorithmen, die machen lokal optimal Entscheidungen bei jedem Schritt mit der Hoffnung, eine zu finden globales Optimum Lösung. Bei diesen Algorithmen werden Entscheidungen auf der Grundlage der aktuell verfügbaren Informationen getroffen, ohne die Konsequenzen dieser Entscheidungen für die Zukunft zu berücksichtigen. Der Schlüsselgedanke besteht darin, bei jedem Schritt die bestmögliche Wahl zu treffen, was zu einer Lösung führt, die möglicherweise nicht immer die optimalste ist, aber für viele Probleme oft gut genug ist.

In diesem Artikel werden wir gierige Algorithmen anhand von Beispielen verstehen. Wir werden uns auch mit dem Greedy-Ansatz mit Problemen und deren Lösungen befassen.

Gierige Algorithmen



Inhaltsverzeichnis

Was ist ein Greedy-Algorithmus?

A Gieriger Algorithmus ist eine Art Optimierungsalgorithmus, der bei jedem Schritt lokal optimale Entscheidungen trifft, um eine global optimale Lösung zu finden. Es basiert auf dem Prinzip, sofort die beste Option zu wählen, ohne die langfristigen Konsequenzen zu berücksichtigen.

Um zu erfahren, was eine Greedy-Methode ist und wie man den Greedy-Ansatz verwendet, lesen Sie das folgende Tutorial zum Greedy-Algorithmus:

Schritte zum Erstellen eines Greedy-Algorithmus

Die Schritte zum Definieren eines Greedy-Algorithmus sind:

  1. Definiere das Problem: Geben Sie das zu lösende Problem und das zu optimierende Ziel klar an.
  2. Identifizieren Sie die gierige Wahl: Bestimmen Sie bei jedem Schritt die lokal optimale Wahl basierend auf dem aktuellen Zustand.
  3. Treffen Sie die gierige Wahl: Wählen Sie die gierige Option und aktualisieren Sie den aktuellen Status.
  4. Wiederholen: Treffen Sie weiterhin gierige Entscheidungen, bis eine Lösung gefunden ist.

Wenn man die angegebenen Schritte befolgt, kann man lernen, wie man mit Greedy-Algorithmen optimale Lösungen findet.

Beispiele für gierige Algorithmen

Beispiele für gierige Algorithmen sind der beste Weg, den Algorithmus zu verstehen. Einige Beispiele aus der Praxis für gierige Algorithmen sind:

  • Fraktionaler Rucksack : Optimiert den Wert von Gegenständen, die teilweise in einem Rucksack mit begrenztem Fassungsvermögen untergebracht werden können.
  • Dijkstras Algorithmus : Findet den kürzesten Weg von einem Quellscheitelpunkt zu allen anderen Scheitelpunkten in einem gewichteten Diagramm.
  • Kruskals Algorithmus : Ermittelt den minimalen Spannbaum eines gewichteten Diagramms.
  • Huffman-Codierung : Komprimiert Daten durch Zuweisung kürzerer Codes zu häufigeren Symbolen.

Anwendungen des Greedy-Algorithmus

Da sind viele Anwendungen der Greedy-Methode in DAA . Einige wichtige Anwendungen für gierige Algorithmen sind:

  • Zuweisen von Aufgaben zu Ressourcen, um Wartezeiten zu minimieren oder die Effizienz zu maximieren.
  • Auswahl der wertvollsten Gegenstände, die in einen Rucksack mit begrenztem Fassungsvermögen passen.
  • Unterteilen eines Bildes in Bereiche mit ähnlichen Eigenschaften.
  • Reduzierung der Datengröße durch Entfernen redundanter Informationen.

Nachteile/Einschränkungen der Verwendung eines Greedy-Algorithmus

Nachfolgend sind einige Nachteile des Greedy-Algorithmus aufgeführt:

  • Greedy-Algorithmen finden möglicherweise nicht immer die bestmögliche Lösung.
  • Die Reihenfolge, in der die Elemente berücksichtigt werden, kann das Ergebnis erheblich beeinflussen.
  • Greedy-Algorithmen konzentrieren sich auf lokale Optimierungen und übersehen möglicherweise bessere Lösungen, die die Berücksichtigung eines breiteren Kontexts erfordern.
  • Greedy-Algorithmen sind nicht auf Probleme anwendbar, bei denen die Greedy-Wahl nicht zu einer optimalen Lösung führt.

Grundlagen des Greedy-Algorithmus:

  • Gierige Algorithmen (allgemeine Struktur und Anwendungen)
  • Unterschied zwischen dem Greedy-Algorithmus und dem Divide and Conquer-Algorithmus
  • Gieriger Ansatz vs. dynamische Programmierung
  • Vergleich zwischen den Algorithmen Greedy, Divide and Conquer und Dynamic Programming

Standard-Greedy-Algorithmen:

  • Problem bei der Aktivitätsauswahl
  • Problem bei der Jobsequenzierung
  • Huffman-Codierung
  • Huffman-Dekodierung
  • Problem mit der Wasserverbindung
  • Mindest-Swaps für den Bracket-Balancing
  • Ägyptische Fraktion
  • Polizisten fassen Diebe
  • Problem beim Einbau der Regale
  • Weisen Sie den Löchern Mäuse zu

Gierige Probleme im Array:

  • Minimale Produktteilmenge eines Arrays
  • Maximieren Sie die Array-Summe nach K Negationen mithilfe der Sortierung
  • Minimale Summe des Produkts zweier Arrays
  • Minimale Summe der absoluten Differenz von Paaren zweier Arrays
  • Minimales Inkrement/Dekrement, damit das Array nicht wächst
  • Array mit Umkehrung um die Mitte sortieren
  • Summe der für ein Array möglichen Flächeninhalte von Rechtecken
  • Größtes lexikografisches Array mit höchstens K aufeinanderfolgenden Vertauschungen
  • Partitionieren Sie in zwei Unterarrays der Längen k und (N – k), sodass die Differenz der Summen maximal ist

Gierige Probleme im Betriebssystem:

  • First Fit-Algorithmus in der Speicherverwaltung
  • Best-Fit-Algorithmus in der Speicherverwaltung
  • Worst-Fit-Algorithmus in der Speicherverwaltung
  • Kürzeste Job-First-Planung
  • Jobplanung mit gleichzeitig zulässigen zwei Jobs
  • Programm für den optimalen Seitenersetzungsalgorithmus

Greedy-Probleme in der Grafik:

  • Kruskals minimaler Spanning Tree
  • Prims Minimum Spanning Tree
  • Boruvkas Minimum Spanning Tree
  • Dijkastras Kürzester-Weg-Algorithmus
  • Dial-Algorithmus
  • Minimale Kosten für die Verbindung aller Städte
  • Einführung in das Max-Flow-Problem
  • Anzahl der Einzelzykluskomponenten in einem ungerichteten Diagramm

Ungefährer Greedy-Algorithmus für NP Complete:

  • Cover-Problem einstellen
  • Problem mit der Behälterverpackung
  • Diagrammfärbung
  • K-Zentren-Problem
  • Kürzestes Superstring-Problem
  • Ungefähre Lösung für das Problem des Handlungsreisenden mithilfe von MST

Gierig nach Sonderfällen von DP:

  • Bruchteil-Rucksack-Problem
  • Mindestanzahl an Münzen erforderlich

Einfache Probleme bei Greedy Algorithmus :

  • Teilen Sie n in maximale zusammengesetzte Zahlen auf
  • Kaufen Sie maximale Aktien, wenn i-Aktien am i-ten Tag gekauft werden können
  • Finden Sie den Mindest- und Höchstbetrag, um alle N-Bonbons zu kaufen
  • Maximal mögliche Summe entspricht der Summe von drei Stapeln
  • Teilen Sie den Quader so in Würfel, dass die Volumensumme maximal ist
  • Maximale Anzahl an Kunden, die mit einer bestimmten Menge zufrieden sein können
  • Mindestumdrehungen zum Entriegeln eines Rundschlosses
  • Mindesträume für m Veranstaltungen von n Gruppen mit vorgegebenem Zeitplan
  • Minimale Kosten für die Array-Größe 1 durch Entfernen größerer Paare
  • Mindestkosten für den Erwerb aller Münzen, wobei für jede Münze k zusätzliche Münzen erlaubt sind
  • Minimales Inkrement um k Operationen, um alle Elemente gleich zu machen
  • Finden Sie die Mindestanzahl an Banknoten und Werten, die in der Summe einen bestimmten Betrag ergeben
  • Kleinste Teilmenge, deren Summe größer als alle anderen Elemente ist

Mittlere Probleme bei Greedy Algorithmus :

  • Maximale Anzahl an Zügen, für die ein Halt vorgesehen werden kann
  • Minimale Fibonacci-Terme mit einer Summe gleich K
  • Teilen Sie 1 bis n in zwei Gruppen mit minimaler Summendifferenz auf
  • Papier in möglichst viele Quadrate schneiden
  • Minimaler Unterschied zwischen Gruppen der Größe zwei
  • Verbinden Sie n Seile mit minimalen Kosten
  • Mindestanzahl an Bahnsteigen, die für einen Bahnhof/Busbahnhof erforderlich sind
  • Minimale Anfangseckpunkte zum Durchqueren der gesamten Matrix unter gegebenen Bedingungen
  • Größte palindromische Zahl durch Permutation von Ziffern
  • Finden Sie die kleinste Zahl mit der angegebenen Anzahl von Ziffern und Ziffernsumme
  • Lexikografisch größte Teilfolge, sodass jedes Zeichen mindestens k-mal vorkommt

Schwierige Probleme bei Greedy Algorithmus :

  • Maximale Elemente, die mit k Aktualisierungen gleich gemacht werden können
  • Minimieren Sie den Cashflow unter Freunden
  • Minimale Kosten, um ein Brett in Quadrate zu schneiden
  • Minimale Kosten für die Bearbeitung von m Aufgaben, bei denen ein Wechsel anfällt
  • Mindestzeit zum Abschluss aller Aufträge mit den gegebenen Einschränkungen
  • Minimieren Sie den maximalen Höhenunterschied zwischen den Türmen
  • Mindestkanten, die umgedreht werden müssen, um einen Pfad von einer Quelle zu einem Ziel zu erstellen
  • Finden Sie den größten Würfel, der durch Löschen der Mindestanzahl an Ziffern aus einer Zahl entsteht
  • Ordnen Sie Zeichen in einer Zeichenfolge neu an, sodass keine zwei benachbarten Zeichen gleich sind
  • Ordnen Sie eine Zeichenfolge neu an, sodass alle gleichen Zeichen einen Abstand von d haben
  • Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial
  • Die 20 häufigsten Fragen im Vorstellungsgespräch zu Greedy-Algorithmen
  • „Übungsprobleme“ zu Greedy-Algorithmen
  • „Quiz“ zu Greedy-Algorithmen