|
---|
Hallo! Ich muss ein Poster erstellen, wo ich erklären muss wie man Greedy Algorithmen mit Matrioden verbinden kann. Leider hab ich derzeit keine Ahnung wie ich das erklären kann und dazu finde ich auch nicht so viel im Internet. Ich hoffe ihr könnt mir helfen! MfG Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
Hallo, Also ich denke, du sollst beschreiben, wie man einen Greedy-Algorithmus zu einem Optimierungsproblem bei z.B. einem gewichteten Graphen finden kann. Dazu "beschafft" man sich ein gewichtetes Matroid, das die Verhältnisse treu widerspiegelt. Zu solch einem Matroid gibt es einen Greedy-Algorithmus, der zu einer optimalen Basis des Matroids führt, z.B. den Kruskal-Algorithmus für minimal aufspannende Bäume in zusammenhängenden endlichen gewichteten Graphen. Das Erste, was zu tun wäre, ist die Matroid-Eigenschaften nachzuweisen. Im konkreten Fall der minimal aufspannenden Bäume, nehme man die Teilmengen aus Kanten, die einen kreisfreien Teilgraphen bilden, so wie der Text es beschreibt. Dabei ist (I3) der Knackpunkt ... Gruß ermanus |
|
Hier könnte z.B. http//www.cits.rub.de/imperia/md/content/may/24_matroid.pdf sehr weiterhelfen. |
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|