Un algorithme général pour les algorithmes gourmands

Question

J'ai rafraîchi des algorithmes gourmands en tant que technique de conception d'algorithme. J'ai lu beaucoup de sources pour une explication de ce qu'est un algorithme glouton, parce que je voudrais mettre en place un algorithme glouton général. En lisant ces sources, j'ai rassemblé tous les concepts importants pour essayer de trouver cet algorithme général pour la technique de sélection gloutonne. Par "général" je veux dire qu'il résume le comportement de la technique pour tout problème possible pour qui cette technique donnerait une solution correcte.

J'aimerais avoir des commentaires à ce sujet. Voici prenons 1:

Soit f une fonction de S à n'importe quel ensemble. L'algorithme suivant tente d'effectuer des choix cupides par chaque itération de recherche de l'élément de S, afin d'essayer venir avec le meilleur point possible pour f sur S étant donné un ensemble de contraintes C:

Select p0 from S; 
i := 1; 
Let P be a set of already chosen points from S to be initialized to {} 
Let F be the set of values of f for each element of P to be initialize to {}; 
while S != {}: 
    Make a greedy choice for p_i based on p_{i - 1}; 
    if f(p_i) is feasible based on constraints from C and has improved: 
     p_{i - 1} := p_i; 
    Add f_i := f(p_i) to F; 
    Remove p_{i - 1} from S and save it in P; 
return P, F; 

Ma question est : Jusqu'où cette première prise d'une généralisation correcte de la technique de sélection glouton pour la conception algorithmique? Après avoir poli cette approche, je voudrais voir comment l'algorithme général peut être instancié aux problèmes d'algorithmes gloutons classiques.

Cela devrait être amusant :)

Answer 1

OMI, pourrait répondre à votre question.

Il est difficile, voire impossible, de définir précisément ce que l'on entend par algorithme glouton . Un algorithme est gourmand s'il construit une solution en petites étapes. choisir une décision à chaque étape myopiquement pour optimiser certains critères sous-jacents. On peut souvent concevoir différents algorithmes gloutons pour le même problème, chacun localement, incrémentalement en optimisant une mesure différente en route vers une solution.

Algorithme Design, par Jon Kleinberg et Éva Tardos. Chapitre 4, Algorithmes Greedy.