Greedoide
În combinatorie , un greedoid este un tip de set de sisteme . Se naște din noțiunea de matroid , care a fost introdusă inițial de Whitney în 1935 pentru studiul graficelor plane și ulterior utilizată de Edmonds pentru a caracteriza o clasă de probleme de optimizare care pot fi rezolvate folosind algoritmi lacomi . În jurul anului 1980, Korte și Lovász au introdus greedoidul ca o generalizare suplimentară pentru această caracteristică a algoritmilor lacomi; de unde și numele greedoide. În afară de optimizarea matematică , greedoidele au fost, de asemenea, conectate la teoria graficelor , teoria limbajului, teoria pozetului și alte domenii ale matematicii .
Definiții
Un set de sistem ( F , E) este o colecție F de subseturi ale unui set de bază E (adică F este un subset al setului de putere al lui E). Când analizăm un greedoid, un membru al lui F se numește un set posibil . Când considerăm un matroid , un set posibil este, de asemenea, cunoscut sub numele de set independent .
Un set de sistem accesibil ( F , E) este un set de sistem în care fiecare set ne-gol posibil X conține un element x astfel încât X \ {x} este posibil. Aceasta implică faptul că orice set de sistem finit , non-gol, conține în mod necesar setul gol ∅. [1]
Un greedoid ( F , E) este un set de sistem accesibil care satisface proprietatea de schimb :
- pentru orice X, Y ∈ F cu | X | > | Y |, există unele x ∈ X \ Y astfel încât Y∪ {x} ∈ F
(Observație: Unii rezervă termenul proprietate de schimb pentru o condiție pe baza unui greedoid și preferă să numească proprietatea menționată mai sus „Proprietate augmentată”.)
O bază a greedoidului este un set maxim acceptabil, ceea ce înseamnă că este un set acceptabil, dar care nu este conținut în niciun altul. O bază a unui subset X de E este un set maxim acceptabil conținut în X.
Rangul unui greedoid este mărimea bazei. Datorită proprietății de schimb, toate bazele au aceeași dimensiune. Prin urmare, rangul unei funcții este bine definit . Rangul unui subset X al lui E este magnitudinea unei baze a lui X.
Clase
Majoritatea claselor greedoid au multe definiții echivalente în ceea ce privește sistemul de seturi, limbajul, poziția, simplicial complex și așa mai departe. Următoarea descriere urmează traseul tradițional de enumerare doar a unor caracterizări mai cunoscute.
Un interval greedoid ( F , E) este un greedoid care îndeplinește proprietatea intervalului :
- dacă A, B, C ∈ F cu A ⊆ B ⊆ C, atunci, pentru fiecare x ∈ E \ C, (A∪ {x} ∈ F și C∪ {x} ∈ F ) implică B∪ {x} ∈ F
În mod echivalent, un interval greedoid este un greedoid astfel încât unirea a două seturi acceptabile este acceptabilă dacă este conținută într-un al doilea set acceptabil.
Un antimatroid ( F , E) este un greedoid care îndeplinește proprietatea intervalului fără limite superioare (majoritare) :
- dacă A, B ∈ F cu A ⊆ B, atunci, pentru fiecare x ∈ E \ B, A∪ {x} ∈ F implică B∪ {x} ∈ F
În mod echivalent, un antimatroid este (i) un greedoid cu o singură bază; sau (ii) un întreg sistem accesibil închis operațiunii de îmbinare. Este simplu de observat că un antimatroid este, de asemenea, un greedoid de interval.
Un matroid ( F , E) este un greedoid ne-gol care îndeplinește proprietatea de interval fără limite superioare (majoritare) :
- dacă B, C ∈ F cu B ⊆ C, atunci, pentru fiecare x ∈ E \ C, C∪ {x} ∈ F implică B∪ {x} ∈ F
Este ușor de văzut că un matroid este, de asemenea, un greedoid de interval.
Exemple
- Luați în considerare un grafic indirect G. Să fie mulțimea de bază formată de marginile lui G și să fie mulțimile acceptabile formate de mulțimea marginilor fiecărei păduri (adică un subgraf fără cicluri) ale lui G. Acest sistem de mulțimi se numește ciclu matroid . Se spune că un set de sistem este un grafic matroid dacă este ciclul matroid al unui grafic. (Inițial ciclul matroid a fost definit ca un circuit sau un set minim dependent . Prin urmare, urmează numele ciclului.)
- Luați în considerare un grafic indirect și finit G, pornit de la vârful r. Să fie mulțimea de bază formată din vârfurile lui G și să fie mulțimile acceptabile formate din seturile certice care conțin r care induce subgrafe conectate ale lui G. Acest lucru se numește vârf de căutare greedoid și este un tip de antimatroid.
- Luați în considerare un grafic direct și finit D început la r. Fie atât mulțimea de bază formată din muchiile directe ale lui D, cât și de seturile acceptabile, să fie seturile de margini ale oricărui subarborel direct început cu r, cu toate muchiile îndreptate în cealaltă direcție decât r. Aceasta se numește o linie de căutare greedoid sau greedoid cu ramificare directă . Este un greeoid de interval, dar nu este nici matroid, nici antimatroid.
- Să considerăm o matrice m-per-n M. Fie mulțimea de bază E formată din indicii coloanelor de la 1 la n să fie mulțimile acceptabile F = {X ⊆ E: submatrică M {1, ..., | X |} , X este o matrice inversabilă }. Aceasta se numește greeoid de eliminare Gaussian, deoarece această structură amintește algoritmul de eliminare Gaussian . Este un greedoid, dar nu un greeoid de interval.
Algoritm lacom
În general, un algoritm lacom este doar un proces iterativ în care cea mai bună alegere locală , practic o intrare de greutate minimă, este aleasă la fiecare iterație până când sunt utilizate toate opțiunile posibile. Pentru a descrie o condiție bazată pe greedoid, în care un algoritm lacom este optim, avem nevoie de o terminologie comună aparținând teoriei greedoid. Fără a pierde generalitatea , considerăm un greedoid G = ( F , E) cu E finit.
Un subset X al lui E este un rang acceptabil dacă cea mai mare intersecție a lui X cu orice set acceptabil are o magnitudine egală cu rangul lui X. Într-un matroid, orice subset al lui E este un rang acceptabil. Dar, în general, egalitatea pe greedoids nu se menține.
O funcție w: E → ℝ este R- compatibilă dacă {x ∈ E: w (x) ≥ c} este un rang acceptabil pentru orice număr real c.
O funcție obiectivă f: 2 S → ℝ este liniară pe un set S dacă, pentru fiecare X ⊆ S, avem f (X) = Σ x ∈ X w (x) pentru o funcție de greutate w: S → ℜ.
Propoziție. Un algoritm lacom este optim pentru orice funcție obiectivă liniară R- compatibilă pe un greedoid.
Înțelegerea din spatele acestei afirmații este că, în timpul procesului iterativ, orice schimb optim de greutate minimă este posibil prin proprietatea de schimb și rezultatele optime sunt obținute din seturi acceptabile din greedoidul de bază. Acest rezultat garantează optimitatea multor algoritmi cunoscuți. De exemplu, un copac minim care se întinde pe un grafic ponderat poate fi obținut folosind algoritmul Kruskal , care este un algoritm lacom pentru un cylo matroid. Algoritmul lui Prim poate fi explicat luând în schimb vârful de căutare greedoid.
Notă
Bibliografie
- Anders Björner și Günter M. Ziegler , 8. Introducere în greedoide , în Neil White (ed.), 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 și algoritmul lacom , în Mathematical Programming , vol. 1, 1971, pp. 127–136, DOI : 10.1007 / BF01584082 , Zbl 0253.90027 .
- Paul Helman, Bernard ME Moret și Henry D. Shapiro, O caracterizare exactă a structurilor lacome , în SIAM Journal on Discrete Mathematics , vol. 6, nr. 2, 1993, pp. 274-283, DOI : 10.1137 / 0406021 , Zbl 0798.68061 .
- Bernhard Korte și László Lovász , Structuri matematice care stau la baza algoritmilor lacomi , în Ferenc Gecseg (ed.), Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, 24-28 august 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 și 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 , Despre proprietățile abstracte ale independenței liniare , în American Journal of Mathematics , vol. 57, nr. 3, 1935, pp. 509-533, DOI : 10.2307 / 2371182 , JSTOR 2371182 , Zbl 0012.00404 .