Greedoide
In [[combinatoria]], un '''greedoide''' è un tipo di [[insieme sistema]]. Sorge dalla nozione di [[matroide]], che è stata originariamente introdotta [[Hassler Whitney|Whitney]] nel 1935 per lo studio di [[grafi planari]] e in seguito usata da [[Jack Edmonds|Edmonds]] per caratterizzare una classe di problemi di ottimizzazione che può essere risolta mediante [[algoritmi greedy]]. Intorno al 1980, [[Bernhard Korte|Korte]] e [[László Lovász|Lovász]] introdussero il greedoide come ulteriore generalizzazione per questa caratteristica di algoritmi greedy; da qui il nome greedoide. A parte l'[[ottimizzazione matematica]], i greedoidi sono stati anche connessi alla [[teoria dei grafi]], teoria dei linguaggi, teoria [[poset]], and altre [[aree della matematica]].

==Definizioni==
Un '''insieme sistema''' (''F'', E) è una collezione ''F'' di [[sottoinsiemi]] di un insieme base E (i.e. ''F'' è un sottoinsieme dell'[[insieme potenza]] di E). Quando prendiamo in analisi un greedoide, un membro di ''F'' è chiamato un '''insieme possibile'''. Quando prendiamo in analisi un [[matroide]], un insieme possibile è anche noto come ''insieme indipendente''.

Un '''sistema insieme accessibile''' (''F'', E) è un insieme sistema in cui ogni insieme possibile non vuoto X contiene un elemento x tale che X\{x} è possibile. Questo implica che ogni insieme sistema accessibile non vuoto, [[finite set|finito]], contiene necessariamente l'[[insieme vuoto]] ∅.<ref>Si osservi che la proprietà di accessibilità è strettamente più debole della ''proprietà ereditaria'' di un [[matroide]], che richiede che ''ogni'' sottoinsieme di un insieme indipendente sia indipendente.</ref>

Un '''greedoide''' (''F'', E) è un insieme sistema accessibile che soddisfa la ''proprietà di scambio'':

* per ogni X,Y ∈ ''F'' con |X| > |Y|, esiste un qualche x ∈ X\Y tale che Y∪{x} ∈ ''F''

(Osservazione: Alcuni riservano il termine ''proprietà di scambio'' per una condizione sulle basi di un greedoide, e preferiscono chiamare la proprietà sopracitata “Proprietà Aumentata”.)

Una '''base''' di un greedoide è un insieme accettabile massimale, che significa sia un insieme accettabile, ma non contenuto in nessun altro. Una base di un sottoinsieme X di E è un insieme accettabile massimale contenuto in X.

Il '''rank''' di un greedoide è la grandezza della base.
Grazie alla proprietà di scambio, tutte le basi hanno la stessa grandezza.
Pertanto, il rank di una funzione è [[ben definito]]. Il rank di un sottoinsieme X di E è la grandezza di una base di X.

==Classi==
La maggior parte delle classi dei greedoidi hanno molte definizioni equivalenti in termini di insieme sistema, linguaggio, poset, [[simpliciale complesso]], and così via. La descrizione che segue la strada tradizionale di elencare solamente alcune delle più conosciute caratterizzazioni.

Un '''greedoide intervallo''' (''F'', E) è un greedoide che soddisfa la ''Proprietà Intervallo'':

* se A, B, C ∈ ''F'' con A ⊆ B ⊆ C, allora, per ogni x ∈ E\C,  (A∪{x} ∈ ''F'' e C∪{x} ∈ ''F'') implica B∪{x} ∈ ''F''

Equivalentemente, un greedoide intervallo è un greedoide tale che l'unione di due insiemi accettabili sia accettabile se essa è contenuta in un secondo insieme accettabile.

Un '''[[antimatroide]]''' (''F'', E) è un greedoide che soddisfa la ''Proprietà Intervallo senza Limiti Superiori (Maggioranti)'':

* se A, B ∈ ''F'' con A ⊆ B, allora, per ogni x ∈ E\B, A∪{x} ∈ ''F'' implica B∪{x} ∈ ''F''

Equivalentemente, un antimatroide è (i) un greedoide con una base unica; o (ii) un insieme sistema accessibile chiuso all'operazione di unione. È semplice vedere che un antimatroide è anche un greedoide intervallo.

Un '''[[matroide]]''' (''F'', E) è un greedoide non vuoto che soddisfa la ''Proprietà Intervallo senza Limiti Superiori (Maggioranti)'':

* se B, C ∈ ''F'' con B ⊆ C, allora, per ogni x ∈ E\C, C∪{x} ∈ ''F'' implica B∪{x} ∈ ''F''

È semplice vedere che un matroide è anche un greedoide intervallo.

==Esempi==
*Si consideri un [[Graph (discrete mathematics)|grafo]] indiretto G. Sia l'insieme base formato dagli archi di G, e siano gli insiemi accettabili formati dall'insieme di archi di ogni ''foresta'' (i.e. un sottografo sprovvisto di cicli) di G. Questo insieme sistema è chiamato il '''ciclo matroide'''. Un insieme sistema è detto essere [[matroide grafico]] se esso è il ciclo matroide di qualche grafo. (Originariamente il ciclo matroide era definito come '''circuito''', o ''insieme dipendente'' minimale. Pertanto ne segue il nome ciclo.)
*Si consideri un grafo indiretto e finito G, [[rooted graph|iniziato]] al vertice r. Sia l'insieme base formato dai vertici di G, e siano gli insiemi accettabili formati dagli insiemi di certici contenenti r che induce a sottografi connessi di G. Questo è chiamato il '''greedoide di vertice di ricerca''', ed è un tipo di antimatroide.
*Si considerti un [[grafo diretto]] e finito D iniziato a r. Sia l'insieme base formato dagli archi diretti di D, e dagli insiemi accettabili, siano gli insiemi archi di ogni sottoalbero diretto iniziato a r con tutti gli archi che puntato in altra direzione rispetto a r. Questo è chiamato '''greedoide di linea di ricerca''', o '''greedoide di branching diretti'''. Si tratta di un greeoide intervallo, ma non si tratta né di un matroide né di un antimatroide.
*Si consideri una [[Matrice (matematica)|matrice]] m-per-n M. Sia l'insieme base E formato dagli indici delle colonne da 1 a n e siano gli insiemi accettabili ''F'' = {X ⊆ E: submatrix M<sub>{1,...,|X<nowiki>|}</nowiki>,X</sub> è una [[matrice invertibile]]}. Questo è chiamato '''greeoide di eliminazione Gaussiana''' perché tale struttura richiama l'algoritmo di [[eliminazione Gaussiana]]. Esso è un greedoide, ma non un greeoide intervallo.

== Algoritmo Greedy ==

In generale, un [[algoritmo greedy]] è solamente un processo iterativo in cui la ''scelta locale migliore'', tendenzialmente un input di peso minimo, è scelto ad ogni iterazione fino a che tutte le possibili scelte vengono utilizzate.
Per descrivere una condizione basata sui greedoidi, in cui un algoritmo greedy sia ottimale, abbiamo bisogno di una terminologia comune appartenente alla teoria dei greedoidi.
[[Senza perdere di generalità]], consideriamo un greedoide G = (''F'', E) con E finito.

Un sottoinsieme X di E è '''rank accettabile''' se la più grande intersezione di X con un qualunque insieme accettabile presenta grandezza uguale al rank di X.
In un matroide, ogni sottoinsieme di E è rank accettabile.
Ma generalmente l'uguaglianza sui greedoidi non regge.

Una funzione w: E → ℝ è '''''R''-compatibile''' se {x ∈ E: w(x) ≥ c} è rank accettabile per ogni [[numero reale]] c.

Una funzione obiettiva f: 2<sup>S</sup> → ℝ è '''lineare''' su un insieme S se, per ogni X ⊆ S, abbiamo f(X) = Σ<sub>x ∈ X</sub> w(x) per una qualche [[funzione peso]] w: S → ℜ.

'''Proposizione.''' Un algoritmo greedy è ottimale per ogni funzione '''''R'''''-compatibile lineare obiettiva su un greedoide.

L'intuizione dietro questa affermazione è che, durante il processo iterativo, ogni scambio ottimale di peso minimo è reso possibile dalla proprietà di scambio, e risultati ottimali sono ottenuti da insiemi accettabili nel greedoide sottostante. Tale risultato garantisce l'ottimalità di molti ben-noti algoritmi. Per esempio, un [[minimum spanning tree]] di un [[grafo pesato]] può essere ottenuto utilizzando l'[[algoritmo di Kruskal]], che è un algoritmo greedy per un matroide cilo. L'[[algoritmo di Prim]] può essere spiegato prendendo il greedoide di vertice di ricerca, invece.

== Note ==
<references />

== Bibliografia ==
* {{Cita pubblicazione|cognome=Björner|nome=Anders|cognome2=Ziegler|nome2=Günter M.|wkautore2=Günter M. Ziegler|wkautore=Anders Björner|capitolo=8. Introduction to greedoids|serie=Encyclopedia of Mathematics and its Applications|volume=40|curatore-cognome=White|curatore-nome=Neil|editore=Cambridge University Press|città=Cambridge|anno=1992|isbn=0-521-38165-7|pp=284–357|doi=10.1017/CBO9780511662041.009|cid=harv|mr=1165537| zbl=0772.05026 |titolo=Matroid Applications}}
*{{Cita pubblicazione|cognome=Edmonds |nome=Jack |wkautore=Jack Edmonds |anno=1971 |titolo=Matroids and the greedy algorithm |rivista=Mathematical Programming |volume=1 |pp=127–136| doi=10.1007/BF01584082 | zbl=0253.90027 }}
*{{Cita pubblicazione|cognome=Helman |nome=Paul |cognome2=Moret |nome2=Bernard M. E. |cognome3=Shapiro |nome3=Henry D. |anno=1993 |titolo=An exact characterization of greedy structures |rivista=[[SIAM Journal on Discrete Mathematics]] |volume=6 |numero=2 |pp=274–283 | doi=10.1137/0406021 | zbl=0798.68061 }}
*{{Cita pubblicazione|cognome=Korte |nome=Bernhard |cognome2=Lovász |nome2=László |wkautore=Bernhard Korte |wkautore2=László Lovász |contributo=Mathematical structures underlying greedy algorithms |curatore-cognome=Gecseg |curatore-nome=Ferenc |titolo=Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, August 24–28, 1981 |serie=Lecture Notes in Computer Science |volume=117 |pp=205–209 |città=Berlin |editore=[[Springer-Verlag]] |anno=1981 | doi=10.1007/3-540-10854-8_22 | zbl=0473.68019 }}
*{{Cita pubblicazione|cognome=Korte |nome=Bernhard |cognome2=Lovász |nome2=László |wkautore2=László Lovász |cognome3=Schrader |nome3=Rainer |anno=1991 |titolo=Greedoids |città=New York, Berlin |editore=[[Springer-Verlag]] | zbl=0733.05023 |serie=Algorithms and Combinatorics |volume=4 | isbn=3-540-18190-3 }}
*{{Cita pubblicazione|cognome=Oxley |nome=James G. |wkautore= James Oxley |titolo=Matroid theory |serie=Oxford Science Publications |città=Oxford |editore=[[Oxford University Press]] |anno=1992 | isbn=0-19-853563-5 | zbl=0784.05002 }}
*{{Cita pubblicazione|cognome=Whitney |nome=Hassler |wkautore=Hassler Whitney |anno=1935 |titolo=On the abstract properties of linear independence |url=https://archive.org/details/sim_american-journal-of-mathematics_1935-07_57_3/page/509 |rivista=[[American Journal of Mathematics]] |volume=57 |numero=3 |pp=509–533 | doi=10.2307/2371182 | jstor=2371182 | zbl=0012.00404 }}

== Voci correlate ==
* [[Matroide]]
* [[Polimatroide]]

== Collegamenti esterni ==
* [https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/006PREPRINT.pdf?1397057423 Introduction to Greedoids]
* [https://parasol.tamu.edu/~welch/teaching/411.f08/greedy.pdf Theory of Greedy Algorithms] {{Webarchive|url=https://web.archive.org/web/20160304103829/https://parasol.tamu.edu/~welch/teaching/411.f08/greedy.pdf |date=4 marzo 2016 }}
* [http://www.kurims.kyoto-u.ac.jp/~fujishig/Book1a.html Submodular Functions and Optimization]
* [https://people.csail.mit.edu/nickh/PhDThesis.pdf Matchings, Matroids and Submodular Functions]

[[Categoria:Combinatoria]]