Comment pouvez-vous être sûr qu'un problème présente une "propriété de choix gourmande"?

Question

Je crains qu'il pourrait y avoir une situation pour laquelle le "greedy choice property" pourrait ne pas tenir.

Pour tout problème, je ne peux vérifier que les petits ensembles de données. Que faire si, pour de grands ensembles de données, la propriété échoue?

Peut-on être sûr?

Answer 1

Une façon probablement plus théorique est la preuve que votre problème a une structure Matroid. Si vous pouvez prouver que votre problème a une telle structure, il existe un algorithme glouton pour le résoudre.

Selon le livre classique "Introduction to Algorithms" un un matroïde est un couple M = (S, l) avec:

* S is a finite nonemtpy set 
* l is a nonempty family of subsets of S, such that B element of l and 
    A a subset of B than also A is element of l. l is called the independent 
    subsets of S. 
* If A and B are elements of l and A is a smaller cardinality than B, then 
    there is some element x that is in B, but not in A, so that A extended 
    by x is also element of l. That is called exchange property. 

Souvent, il y a aussi une fonction de pondération w qui attribue à chaque élément x dans S, poids.

Si vous pouvez formuler votre fonction pondérée en Matroid que le Python comme pseudo-code suivant permet de résoudre votre problème:

GREEDY(M,w): 
    (S,l) = M 
    a = {} 
    sort S into monotonically decreasing order by weight w 
    for x in S: 
     if A + {x} in l: 
     A = A + {x}