Unabhängigkeitssystem, Rucksackproblem und Greedy |
15.01.2017, 11:49 | Nena678 | Auf diesen Beitrag antworten » |
Unabhängigkeitssystem, Rucksackproblem und Greedy Hallo, der Einfachheitshalber hab ich die Aufgabe als Bild angehängt. Nach ein bisschen im Internet forschen hab ich raus gefunden dass es verschiedene Knapsackprobleme (Rucksackprobleme) gibt. Nämlich 0-1 und etwas anderes, aber hier gehts nur um das 0-1 Problem also immer das Gewicht und nicht nur einen Teil des Gewichtes. Def. Maximierungsproblem Ein Max.prob. über einem US U=(E,I) ist gegeben durch eine Gewichtsfunktion und die Aufgabe: Finde A* in I sodass mit c(A*) = max c(A). (also A* so groß wie möglich mit A* in I) Meine Ideen: a) Also Grundsätzlich würde ich mal einen Graphen G aufstellen, bei dem ich als Knoten nehme und jeden mit jedem Verbinde. Also G=(V,E) vollständiger Graph. Was irgendwie ja auch sinvoll ist, da ich nach jedem Gegenstand der in den Rucksack kommt jeden beliebigen als nächstes nehmen kann. Das t brauche ich dafür das falls beim Algorithmus in b) alle G in den Rucksack passen und ich dann einen Kreis hätte was nicht mehr in I liegen würde. Anschließend würde ich mein Unabhängigkeitssystem(US) wie folgt aufstellen: mit E Kantenmenge von G und Damit ist nach Vorlesung U ein Matroid und somit ein US. Nun muss ich unter maximieren unter der Berücksichtigung der Gewichte. Damit habe ich ein Maxiemierungsproblem. b) , wobei der Wert von und , R ... max. Rucksackgewicht ___________________________________________________________________________ _____ Input: , ,, R Output: BEGIN sortiere E*, sodass <- b <- 0 B <- FOR i=1 to n DO (b <- b + B <- IF b>R DO b <- b - B <- B\ ) k <- |B| FOR i=1 to k-1 DO ( <- ) <- END ___________________________________________________________________________ ___________ dabei sind die Kanten die Kante von nach und die Letzte Kante ist immer zu t C) unter Rang, oberer Rang und Rangquotient alle 1 da U Monoid (wurde in VL gezeigt) d) Da weiß ich nicht genau was ich machen soll das ja jedes Beispiel das Minimum des Rangquotienten erreicht (hab ich voher etwas falsch gemacht?) genau so weiß ich nicht wirklich etwas mit dem wort Performance anzufangen |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|