Welcher Greedy-Algorithmus erfüllt die Greedy-Choice-Eigenschaft, hat aber keine optimale Unterstruktur?

Basierend auf dem Lehrbuch Einführung in Algorithmen erfordert die Korrektheit eines gierigen Algorithmus, dass ein Problem zwei Eigenschaften aufweist:

1. gierige Wahl Eigenschaft
2. optimale Unterkonstruktion

Es ist leicht, Gegenbeispiele zu finden, bei denen eine gierige Lösung aufgrund des Fehlens der Eigenschaft der gierigen Auswahl fehlschlägt, z. B. das 0/1-Rucksackproblem. Aber ich finde die andere Möglichkeit ziemlich schwer vorstellbar. Kann mir jemand ein Problem und einen entsprechenden gierigen Algorithmus geben, der die erste Eigenschaft erfüllt, aber nicht die zweite?

Einer der Standardschätzer in der robusten Statistik ist ein Typ des getrimmten Mittelwerts, bei dem Sie eine Mehrheitsteilmenge einer Reihe von Eingabezahlen so auswählen, dass die maximale Differenz zwischen zwei ausgewählten Zahlen minimiert wird, und dann den Mittelwert der ausgewählten Zahlen bilden Teilmenge. Es gibt einen einfachen ersten Schritt zur Auswahl von Gier: Wählen Sie den Median als Teil Ihrer Teilmenge aus. Aber wenn Sie diese Wahl getroffen haben, ist das verbleibende Problem nicht vom selben Typ (dh wir haben keine optimalen Unterstrukturen), so dass es keine offensichtliche Methode gibt, diesen Algorithmus gierig fortzusetzen. Insbesondere funktioniert es nicht, weiterhin Mediane der verbleibenden Punkte zu wählen. (Die wiederholte gierige Medianstrategie, die mit ein wenig Sorgfalt durchgeführt wird, ergibt den Interquartilmittelwert, der ebenfalls robust ist, aber nicht das gleiche Problem löst und einen niedrigeren Durchschlagspunkt aufweist.)