Quel algorithme gourmand satisfait la propriété de choix gourmand mais n'a pas de sous-structure optimale?

Basé sur le manuel Introduction to Algorithms , l'exactitude d'un algorithme gourmand nécessite qu'un problème ait deux propriétés:

1. propriété de choix gourmande
2. sous-structure optimale

Il est facile de trouver des contre-exemples pour lesquels une solution gourmande échoue en raison du manque de la propriété de choix gourmand, par exemple le problème du sac à dos 0/1. Mais je trouve l'autre possibilité assez difficile à imaginer. Quelqu'un peut-il me donner un problème et un algorithme gourmand correspondant qui satisfait la première propriété mais pas la seconde?

L'un des estimateurs standard dans les statistiques robustes est un type de moyenne tronquée où vous choisissez un sous-ensemble majoritaire d'un ensemble de nombres d'entrée de manière à minimiser la différence maximale entre deux nombres sélectionnés, puis prenez la moyenne de la valeur sélectionnée sous-ensemble. Il y a une première étape facile à choisir gourmande: choisissez la médiane dans votre sous-ensemble. Mais une fois que vous avez fait ce choix, le problème restant n'est pas du même type (c'est-à-dire que nous n'avons pas de sous-structures optimales), il n'y a donc pas de méthode évidente pour continuer cet algorithme avec gourmandise. En particulier, cela ne fonctionne pas de continuer à choisir les médianes des points restants. (La stratégie médiane gourmande répétée, faite avec un peu de soin, donne la moyenne interquartile qui est également robuste mais ne résout pas le même problème et a un point de rupture plus bas.)