Algoritm lacom

Un algoritm lacom este o paradigmă algoritmică , în care algoritmul caută o soluție fezabilă dintr-un punct de vedere global, alegând cea mai atractivă soluție (definită anterior de programator) pentru acel program particular la fiecare pas local. Atunci când este cazul, acești algoritmi permit să găsească soluții optime pentru anumite probleme într-un timp polinomial, în timp ce în celelalte convergența la optimul global nu este garantată.

Exemple explicative

Problema „Dați cel mai mic număr de monede de schimb folosind monede de 100, 10, 1 eurocent” este o problemă care poate fi rezolvată prin intermediul unui algoritm lacom: la fiecare pas se verifică modificarea care trebuie încă dată și moneda cu cea mai mare se adaugă suma.valoare posibilă. Deci, pentru a da o schimbare de 112 eurocenți, mașina va arunca o monedă de 100 în ordine, apoi 10, apoi 1 și, în final, 1 eurocent din nou pentru un total de 4 monede.

Problema cunoscută în mod obișnuit ca „Vânzătorul călător” , adică „având în vedere o serie de livrări și colecții cu un vehicul care are o rază maximă P, organizează călătoria care îți permite să parcurgi cei mai puțini km cu cea mai mare sarcină posibilă pentru a obține câștigul maxim ", nu este o problemă care poate fi rezolvată printr-un algoritm lacom, ci doar prin algoritmi pentru probleme NP-Complete .

Primul exemplu poate fi rezolvat grație unui algoritm lacom numai pentru seturi adecvate de valori ale monedei: de fapt, dacă ar exista și 105 monede eurocente (valori ale monedei: 105, 100, 10, 1), algoritmul lacom ar da un total de 8 monede (una din 105 și 7 din 1), în timp ce soluția optimă este cea cu 4 monede (100 + 10 + 1 + 1).

Definiție formală

În combinatorie și optimizare prin algoritm lacom, ne referim la un algoritm care permite identificarea unei baze a unui proces matroid finit într-un mod remarcabil de simplu și eficient.

Luați în considerare mulțimea E și o familie F de subseturi de E ( $F\subseteq 2^{E}$ ${\ displaystyle F \ subseteq 2 ^ {E}}$ $F \ subseteq 2 ^ E$ ) care formează un ideal de ordine în ceea ce privește relația de incluziune:

$A\in F\land B\subseteq A\to B\in F$ ${\ displaystyle A \ în F \ land B \ subseteq A \ to B \ in F}$ ${\ displaystyle A \ în F \ land B \ subseteq A \ to B \ in F}$

Perechea E, F formează un sistem de independență. Funcția de greutate w este, de asemenea, definită.

Având în vedere un sistem de independență E, F și o funcție de greutate w, obținem o mulțime M astfel încât w (M) să fie maxim.

Descrierea algoritmului

Luați în considerare un matroid independent M = ( E , I ). Algoritmul folosește un set de variabile X care este extins progresiv până la identificarea unei baze.

Setul gol este atribuit inițial setului de variabile X.
Continuăm luând în considerare elementele ulterioare x din E care nu sunt conținute în X ;
- De sine $X\cup \{x\}$ ${\ displaystyle X \ cup \ {x \}}$ $X \ cup \ {x \}$ este independent, apoi X-ul anterior se transformă prin adăugarea lui x, adică $X:=X\cup \{x\}$ ${\ displaystyle X: = X \ cup \ {x \}}$ $X: = X \ cup \ {x \}$ . În caz contrar, procesul se termină.

Rezultatul este un set independent. Mai mult, este un set maxim independent, deoarece dacă BU {x} nu ar fi independent pentru un subset B al lui X , atunci $X\cup \{x\}$ ${\ displaystyle X \ cup \ {x \}}$ $X \ cup \ {x \}$ nu ar fi independent: altfel ar merge împotriva proprietății moștenirii. Deci, dacă neglijați un element, nu veți avea ocazia să îl utilizați mai târziu.

Matroide ponderate și algoritmi lacomi

Generalizarea acestui algoritm pentru a rezolva o problemă mai dificilă.

O funcție de greutate w : E → R ⁺ pentru un matroid M = ( E , I ) atribuie o greutate strict pozitivă fiecărui element din E. Extinderea funcției la subseturi de E prin sumă; w ( A ) este suma lui w ( x ) peste x în A. Un matroid cu funcție de greutate asociată se numește matroid ponderat.

Ca un exemplu simplu, să presupunem că vrem să găsim acoperirea maximă a pădurilor unui grafic. Adică, având în vedere un grafic și o greutate pentru fiecare arc, găsiți o pădure care conține fiecare vârf și maximizează greutatea totală a arcurilor din copac. Această problemă apare în unele aplicații de clusterizare. Dacă ne uităm la definiția matroidului forestier de mai sus, vedem că acoperirea maximă a pădurii este pur și simplu subsetul independent cu greutatea totală maximă - astfel încât acoperă graficul, deoarece altfel am putea adăuga margini fără a crea cicluri. Dar cum o găsim?

Un set independent de greutate totală maximă se numește set optim . Seturile optime sunt întotdeauna elementele de bază, deoarece dacă se poate adăuga un arc, ar trebui făcut; acest lucru mărește doar greutatea totală. Se poate arăta că există un algoritm banal lacom pentru a calcula un set optim de matroid ponderat. Procedează după cum urmează:

Fie A setul gol.
Pentru fiecare x în E , luat în ordine (monoton) în scădere în greutate
- dacă AU {x} este independent, atunci A devine AU {x}.

Acest algoritm găsește o bază, deoarece este un caz special al algoritmului anterior. Alege întotdeauna cel mai greu element posibil, păstrând în același timp independența (de unde și termenul „lacom”). Aceasta produce întotdeauna un set optim: să presupunem că produce $A=\{e_{1},e_{2},\ldots ,e_{r}\}$ ${\ displaystyle A = \ {e_ {1}, e_ {2}, \ ldots, e_ {r} \}}$ $A = \ {e_1, e_2, \ ldots, e_r \}$ este asta $B=\{f_{1},f_{2},\ldots ,f_{r}\}$ ${\ displaystyle B = \ {f_ {1}, f_ {2}, \ ldots, f_ {r} \}}$ $B = \ {f_1, f_2, \ ldots, f_r \}$ . Acum pentru fiecare $k$ ${\ displaystyle k}$ $k$ cu $1\leq k\leq r$ ${\ displaystyle 1 \ leq k \ leq r}$ $1 \ le k \ le r$ , considerăm seturi deschise $O_{1}=\{e_{1},\ldots ,e_{k-1}\}$ ${\ displaystyle O_ {1} = \ {e_ {1}, \ ldots, e_ {k-1} \}}$ $O_1 = \ {e_1, \ ldots, e_ {k-1} \}$ Și $O_{2}=\{f_{1},\ldots ,f_{k}\}$ ${\ displaystyle O_ {2} = \ {f_ {1}, \ ldots, f_ {k} \}}$ $O_2 = \ {f_1, \ ldots, f_k \}$ . Având în vedere că $O_{1}$ ${\ displaystyle O_ {1}}$ $O_ {1}$ este mai mic decât $O_{2}$ ${\ displaystyle O_ {2}}$ $O_ {2}$ , există un element al $O_{2}$ ${\ displaystyle O_ {2}}$ $O_ {2}$ care poate fi pus în $O_{1}$ ${\ displaystyle O_ {1}}$ $O_ {1}$ păstrând rezultatul independent. in orice caz $e_{k}$ ${\ displaystyle e_ {k}}$ $și_k$ este un articol cu greutate maximă la care se poate adăuga $O_{1}$ ${\ displaystyle O_ {1}}$ $O_ {1}$ pentru a menține independența. Pentru care $e_{k}$ ${\ displaystyle e_ {k}}$ $și_k$ cântărește nu mai puțin decât un element al $O_{2}$ ${\ displaystyle O_ {2}}$ $O_ {2}$ , și apoi $e_{k}$ ${\ displaystyle e_ {k}}$ $și_k$ are cel puțin o greutate egală cu $f_{k}$ ${\ displaystyle f_ {k}}$ $f_ {k}$ . Deoarece acest lucru se aplică tuturor $k$ ${\ displaystyle k}$ $k$ , $LA$ ${\ displaystyle A}$ $LA$ este mai greu decât $B.$ ${\ displaystyle B}$ $B.$ .

Cel mai simplu mod de a traversa membrii lui E în ordinea dorită este să-i sortați. Aceasta necesită timp O (| E | log | E |) folosind un algoritm de sortare . De asemenea, avem nevoie de teste pentru fiecare x pentru a determina dacă AU {x} este independentă; presupunând că testul de independență necesită timp O (f (| E |)), timpul total pentru algoritm este O (| E | log | E | + | E | f (| E |)).

Dacă dorim să găsim în schimb un copac minim care se întinde, pur și simplu „inversăm” funcția de greutate scăzând-o dintr-o constantă mare. Mai exact, fii w _min ( x ) = W - w ( x ), unde W depășește greutatea totală pe toate marginile graficului. Multe alte probleme de optimizare pe diferite tipuri de matroizi și funcții de greutate pot fi rezolvate în acest mod banal, deși în multe cazuri pot fi găsiți algoritmi mai eficienți care exploatează proprietăți mai specifice.

De asemenea, rețineți că, dacă luăm un set $THE$ ${\ displaystyle I}$ $THE$ de seturi „independente”, care este un set descendent, dar nu un matroid, atunci algoritmul lacom nu va funcționa întotdeauna. Deoarece în acest caz există seturi independente $I_{1}$ ${\ displaystyle I_ {1}}$ $I_1$ Și $I_{2}$ ${\ displaystyle I_ {2}}$ $I_2$ cu $|I_{1}|<|I_{2}|$ ${\ displaystyle | I_ {1} | <| I_ {2} |}$ $| I_1 | <| I_2 |$ , dar astfel încât pentru niciunul $e\in I_{2}\setminus I_{1}$ ${\ displaystyle și \ in I_ {2} \ setminus I_ {1}}$ $și \ în I_2 \ setminus I_1$ Și $I_{1}\cup e$ ${\ displaystyle I_ {1} \ cup e}$ $I_1 \ cup e$ independent.

Să luăm un $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\ varepsilon> 0$ Și $\tau >0$ ${\ displaystyle \ tau> 0}$ $\ tau> 0$ astfel încât $(1+2\varepsilon )|I_{1}|+\tau |E|<|I_{2}|$ ${\ displaystyle (1 + 2 \ varepsilon) | I_ {1} | + \ tau | E | <| I_ {2} |}$ $(1 + 2 \ varepsilon) | I_1 | + \ tau | E | <| I_2 |$ . Ne cântărim elementele $I_{1}\cup I_{2}$ ${\ displaystyle I_ {1} \ cup I_ {2}}$ $I_1 \ cup I_2$ în intervalul de la $2$ ${\ displaystyle 2}$ $2$ la $2+2\varepsilon$ ${\ displaystyle 2 + 2 \ varepsilon}$ $2 + 2 \ varepsilon$ , elementele din $I_{1}\setminus I_{2}$ ${\ displaystyle I_ {1} \ setminus I_ {2}}$ $I_1 \ setminus I_2$ în intervalul de la $1+\varepsilon$ ${\ displaystyle 1+ \ varepsilon}$ $1+ \ varepsilon$ la $1+2\varepsilon$ ${\ displaystyle 1 + 2 \ varepsilon}$ $1 + 2 \ varepsilon$ , elementele din $I_{2}\setminus I_{1}$ ${\ displaystyle I_ {2} \ setminus I_ {1}}$ $I_2 \ setminus I_1$ în intervalul de la $1$ ${\ displaystyle 1}$ $1$ la $1+\varepsilon$ ${\ displaystyle 1+ \ varepsilon}$ $1+ \ varepsilon$ , iar restul în intervalul de la până la $\tau$ ${\ displaystyle \ tau}$ $\ tau$ . Algoritmul lacom va alege elementele $I_{1}$ ${\ displaystyle I_ {1}}$ $I_1$ , și ulterior nu va putea alege niciun element din $I_{2}\setminus I_{1}$ ${\ displaystyle I_ {2} \ setminus I_ {1}}$ $I_2 \ setminus I_1$ . În consecință, setul independent pe care îl construiește nu va cântări mai mult de $(1+2\varepsilon )|I_{1}|+\tau |E|+|I_{1}\cup I_{2}|$ ${\ displaystyle (1 + 2 \ varepsilon) | I_ {1} | + \ tau | E | + | I_ {1} \ cup I_ {2} |}$ $(1 + 2 \ varepsilon) | I_1 | + \ tau | E | + | I_1 \ cup I_2 |$ , care este mai mică decât greutatea lui $I_{2}$ ${\ displaystyle I_ {2}}$ $I_2$ .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe algoritmul lacom

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică