Greedoide
In combinatoria, un greedoide è un tipo di insieme sistema. Sorge dalla nozione di matroide, che è stata originariamente introdotta Whitney nel 1935 per lo studio di grafi planari e in seguito usata da Edmonds per caratterizzare una classe di problemi di ottimizzazione che può essere risolta mediante algoritmi greedy. Intorno al 1980, Korte e 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[modifica | modifica wikitesto]
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, finito, contiene necessariamente l'insieme vuoto ∅.[1]
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[modifica | modifica wikitesto]
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[modifica | modifica wikitesto]
- Si consideri un 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, 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 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{1,...,|X|},X è 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[modifica | modifica wikitesto]
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: 2S → ℝ è lineare su un insieme S se, per ogni X ⊆ S, abbiamo f(X) = Σx ∈ X 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[modifica | modifica wikitesto]
Bibliografia[modifica | modifica wikitesto]
- Anders Björner e Günter M. Ziegler, 8. Introduction to greedoids, in Neil White (a cura di), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge, Cambridge University Press, 1992, pp. 284–357, DOI:10.1017/CBO9780511662041.009, ISBN 0-521-38165-7, MR 1165537, Zbl 0772.05026.
- Jack Edmonds, Matroids and the greedy algorithm, in Mathematical Programming, vol. 1, 1971, pp. 127–136, DOI:10.1007/BF01584082, Zbl 0253.90027.
- Paul Helman, Bernard M. E. Moret e Henry D. Shapiro, An exact characterization of greedy structures, in SIAM Journal on Discrete Mathematics, vol. 6, n. 2, 1993, pp. 274–283, DOI:10.1137/0406021, Zbl 0798.68061.
- Bernhard Korte e László Lovász, Mathematical structures underlying greedy algorithms, in Ferenc Gecseg (a cura di), Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, August 24–28, 1981, Lecture Notes in Computer Science, vol. 117, Berlin, Springer-Verlag, 1981, pp. 205–209, DOI:10.1007/3-540-10854-8_22, Zbl 0473.68019.
- Bernhard Korte, László Lovász e Rainer Schrader, Greedoids, Algorithms and Combinatorics, vol. 4, New York, Berlin, Springer-Verlag, 1991, ISBN 3-540-18190-3, Zbl 0733.05023.
- James G. Oxley, Matroid theory, Oxford Science Publications, Oxford, Oxford University Press, 1992, ISBN 0-19-853563-5, Zbl 0784.05002.
- Hassler Whitney, On the abstract properties of linear independence, in American Journal of Mathematics, vol. 57, n. 3, 1935, pp. 509–533, DOI:10.2307/2371182, JSTOR 2371182, Zbl 0012.00404.