Hat jeder gierige Algorithmus eine Matroid-Struktur?

13

Es ist bekannt, dass für jede Matroid M und jede Gewichtsfunktion w ein Algorithmus GreedyBasis(M,w) der eine maximale Gewichtsbasis von M zurückgibt . Stimmt also auch die umgekehrte Richtung? Das heißt, wenn es einen gierigen Algorithmus gibt, muss es auch eine Matroid-Struktur geben.

Jan Johannsen
quelle
Der Dijkstra-Algorithmus wird oft als gieriger Algorithmus angesehen (siehe z. B. Abschnitt 4.4 von "Algorithm Design" von Kleinberg und Tardos). Ich kenne keine matroid Interpretation der kürzesten Wege aus einer Hand.
Neal Young
Das Partitionieren einer Menge von reellen Intervallen in eine minimale Anzahl von paarweise disjunkten Teilmengen hat einen natürlichen Greedy-Algorithmus (Zählen Sie die Intervalle nach Startzeit auf, fügen Sie sie nach Möglichkeit zu einer vorhandenen Teilmenge hinzu, andernfalls starten Sie eine neue Teilmenge; siehe Kapitel 4 von Kleinberg und Tardos). Kann dieses Problem als Matroid verstanden werden?
Neal Young

Antworten:

11

Der Greedy-Algorithmus ist kein formal definiertes Konzept. Es gibt verschiedene Modelle, die versuchen, diese intuitive Vorstellung zu erfassen, aber es gibt keinen Konsens darüber, was ein gieriger Algorithmus ist. Wenn Sie keine formale Definition für den Begriff "gieriger Algorithmus" angeben, kann die Frage nicht mit "Ja" oder "Nein" beantwortet werden.

Es gibt eine Verallgemeinerung von Matroiden namens Greedoid, die von gierigen Algorithmen inspiriert ist.

Kaveh
quelle
Eine formale Definition ist nicht erforderlich, wenn wir uns auf eine Eigenschaft der Klasse der gierigen Algorithmen einigen. Wenn wir uns zum Beispiel einig wären, dass jeder gierige Algorithmus eine (formal definierte) Eigenschaft P hat, und wir zeigten, dass jeder Algorithmus, der P erfüllt, auf einer Matroid definiert werden kann, würde dies eine positive Antwort auf die Frage des OP geben. Ebenso, wenn wir uns einig wären, dass ein bestimmter Algorithmus gierig ist und wir zeigten, dass es nicht der gierige Algorithmus einer Matroide sein kann, würde dies eine negative Antwort ergeben.
Freistehendes Laconian
11

Tatsächlich ist die vollständige und allgemeine Beschreibung eines Problems, das durch einen Greedy-Algorithmus gelöst werden kann, eine Matroid-Einbettung , die sowohl das Konzept eines Matroids als auch das eines Greedoids verallgemeinert . Die Antwort ist nein - ein Problem, das durch einen gierigen Algorithmus lösbar ist, muss keine Matroid-Struktur haben, aber es wird die Struktur einer Matroid-Einbettung haben (was leider viel komplizierter ist).

Ein mentales Modell für einige davon könnte sein, minimale Spannbäume zu finden. Die von Kruskals Algorithmus verwendete Struktur ist eine Matroide, die von Prims Algorithmus (für den ein Startknoten erforderlich ist) jedoch nicht. (Es handelt sich jedoch um eine Gier - und eine Matroid-Einbettung.)

Helman et al. (1993) definieren in ihrer Arbeit Eine genaue Charakterisierung gieriger Strukturen ihren Begriff eines gierigen Algorithmus in Bezug auf Mengen-Systeme, der der gleiche Formalismus ist, der für Matroiden und Greedoiden verwendet wird. Ein Mengen-System besteht aus einer Menge S und einer Sammlung C von Teilmengen von S , den sogenannten Machbaren Mengen . Eine Basis für das Mengen-System ist eine maximal mögliche Menge, dh eine Menge, die machbar ist, aber in keiner anderen machbaren Menge enthalten ist. Eine Zielfunktion f : 2 SR(S,C)SCS f:2SRordnet jede Teilmenge von einem Wert zu. Ein Optimierungsproblem in diesem Formalismus besteht darin, eine Basis für den maximalen Zielwert für ein gegebenes Satzsystem und eine gegebene Zielfunktion zu finden.S

Der im Sinne dieses Formalismus definierte Greedy-Algorithmus ist recht einfach: Sie beginnen mit der leeren Menge und fügen nacheinander ein einzelnes Element hinzu, bis Sie zu einer Basis gelangen, wobei Sie stets sicherstellen, dass (i) Ihre Menge bei jedem Schritt durchführbar ist, und ( ii) Das Element, das Sie hinzufügen, maximiert die objektive Funktion des resultierenden Ergebnisses, z. Alle alternativen Elemente, die Sie hätten hinzufügen können. (Das heißt, Sie versuchen konzeptionell, alle möglichen Alternativen hinzuzufügen, und wählen diejenige, die den höchsten objektiven Wert ergibt.)

Sie könnten vielleicht argumentieren, dass es andere Formen von Greedy-Algorithmen geben könnte, aber es gibt mehrere Lehrbücher über Algorithmen und kombinatorische Optimierung, die diesen Algorithmus auf der Basis von Mengen-Systemen als Greedy-Algorithmus beschreiben. Das hindert Sie nicht daran, etwas zu beschreiben, das nicht passt, aber trotzdem als gierig bezeichnet werden könnte, nehme ich an. (Still, dies tut Abdeckung alles , was potenziell eine Matroid Struktur haben könnte, zum Beispiel, obwohl es viel allgemeiner.)

Was Helman et al. Sie beschreiben, wann dieser Algorithmus funktioniert. Genauer:

  1. Sie zeigen, dass für lineare Zielfunktionen (wobei der Zielwert die Summe der Elementgewichte ist) der Greedy-Algorithmus genau auf die Struktur angewendet wird, die sie als Matroid-Einbettung definieren.

  2. Sie geben eine ähnliche Charakterisierung für sogenannte Engpassziele (wobei der Zielwert einer Menge über die einzelnen Elementgewichte gleich dem Minimum ist); und

  3. Sie geben eine genaue Beschreibung, welche objektiven Funktionen (über die linearen hinaus) durch den gierigen Algorithmus bei Matroid-Einbettungen optimiert werden.

Magnus Lie Hetland
quelle
2
Können Sie erklären, wie sie einen gierigen Algorithmus definieren?
Kaveh
1
Erweitert meine Antwort, um zu erklären, was ihr Formalismus ist.
Magnus Lie Hetland
2

Berücksichtigen Sie folgende Probleme: KETTENRECHTLICHER EURO: Bezahlen Sie bei einem unendlichen Betrag von 1,2,5,10 Euro-Banknoten X Euro mit möglichst wenigen Banknoten. Dies kann durch die Verwendung eines gierigen Algorithmus gelöst werden, der die größtmögliche Beachtung findet. Bei diesem Problem gibt es jedoch keine Matroid-Struktur.

LOCHABDECKUNG: An den Positionen x_1, x_2, ..., x_n sind Löcher vorhanden. Sie haben einen Patch von 10 cm Länge. Patchen Sie die Löcher mit so wenig Patches wie möglich. Auch dies kann auf gierige Weise gelöst werden (Patch so richtig wie möglich platzieren), aber es gibt keine Matroid-Struktur.

usamec
quelle
Danke, ich hatte meinen Verdacht, war mir aber nicht sicher. Wir müssen also nach gierigen Algorithmen suchen, auch wenn es keine Matroid-Struktur gibt.
1
@ user3373748 Ich suche normalerweise nur ein dynamisches Programm. Gierig ist ein degenerierter DP.
1
(Um nicht wählerisch zu sein, aber es gibt keine 1- oder 2-Euro-Banknoten. Vielleicht möchten Sie Ihren Wertesatz in {5, 10, 20, 50, 100, 200} ändern oder umformulieren ;-))
Anthony Labarre
Beachten Sie, dass der beschriebene Münzwechselalgorithmus für {1,2,5,10} funktioniert, jedoch möglicherweise nicht die optimalen Ergebnisse für andere Werte berechnet. Beispiel: Mit {1,3,4} wäre die optimale Lösung für 6 [3,3], aber der Algorithmus würde [4,1,1] zurückgeben.
Socowi
1
Es gibt eine Matroid-Struktur für das Problem des Geldwechsels
gauss.ececs.uc.edu/Courses/C671/html/Homework/hw5_sol.html