Greedy-Strategie (Greedy Approach)
{"Image DocumentName": "Greedy-Strategie (Greedy Approach)", "Image ImageDescription": "Wir werden zun\u00e4chst einen generischen Algorithmus diskutieren, der die folgende Iterations-Invariante aufrechterh\u00e4lt: Wir berechnen iterativ eine Kantenmenge A f\u00fcr die gilt: Invariante: Vor und nach jeder Iteration ist A eine Teilmenge. der Kanten eines MST. Falls also die Kantenmenge A nach einer gewissen Zahl von Iterationen einen aufspannenden Baum bildet, so haben wir einen MST berechnet. Die Algorithmen zur Berechnung eines MST verwenden die sogenannte Greedy-Strategie (Greedy Approach) (greedy = gierig, gefr\u00e4\u00dfig, habgierig). In jedem Schritt des Algorithmus hat man die Wahl zwischen mehreren Kanten. Die Greedy-Strategie w\u00e4hlt die Kante, die in diesem Moment die (scheinbar) beste Wahl darstellt. In vielen Anwendungen liefern Greedy-Strategien nur suboptimale Resultate und nicht die (globale) optimale L\u00f6sung. Es existieren jedoch Greedy-Algorithmen, die die optimale L\u00f6sung des MST-Problem berechnen.", "Image XResolution": "37", "Image YResolution": "37", "Image ResolutionUnit": "Pixels/Centimeter", "Image Software": "SlidePlayer", "Image YCbCrPositioning": "Centered"}