|
|
Produktmaximierung, Greedy, lineares Sortieren |
|
Produktmaximierung, Greedy, lineares Sortieren |
|
Sehr geehrte Damen und Herren
Ich muss mal um eure Meinung anhorchen...es geht um folgendes Problem:
Gegeben sind zwei unsortierte Mengen A, B, die n ganze Zahlen aus dem Bereich {1,...,n} enthalten.
Nun soll ich einen Weg beschreiben, die beiden Mengen zu sortieren, sodass
das Produkt von i=1 bis n über (ai^(bi)) maximiert wird. (ich hoffe das ist nicht zu bekloppt geschrieben ... wie mache ich hier denn Formeln...
Ich bin jetzt schon soweit zu sagen, dass die beiden Mengen einfach nur "gleich" sortiert sein müssen. Aufsteigend, oder absteigend, aber eben gleich, denn für das Produkt ist es am Ende egal, wie sie sortiertsind, solange sie nur GLEICH soriert sind.
Ich könnte mir auch vorstellen, dass es im Grunde ganz egal sind ob sie sortiert sind, solange die Folge B die gleiche Folge ist, wie die Folge B.
Beide enthalten ja die selben Zahlen. Und solange ai = bi ist es egal in welcher Reihenfolge, da das Produkt ja kommutativ ist.
Das ganze soll ich aber nun in O(n) sortieren. Und meine einzige Idee wäre da Radixsort. Da ich ja genau weiß, welcher Form die Elemente sind, würde ich einfach schauen, wie viele Stellen die größte Zahl, also n, hat, und dann einfach Radixsort auf beide anwenden. Radixsort läuft in O(n) und das dann halt 2 mal ... bleibt alles in O(n).
Liege ich damit sehr falsch?!
Die Überschrift auf der Aufgabe ist "Greedy Strategien", wie das zur Lösung des Problem beitragen soll ist mir ein Rästel. Greedy bedeutet doch banal "lokaes Optimum führt zu globalem Optimum" oder?! Also IM MOMENT immer gierig die beste Lösung wählen ...
__________________ I'm 71% Megatron!
|
|
21.01.2008 17:21 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ja, ich würde dir bei deinen Überlegungen Recht geben. Deine prinzipielle Beobachtung ist ja, dass die größte Basis auch den größten Exponenten bekommen soll. (Musst du das beweisen oder kannst du das voraussetzen?)
Zum Thema Greedy:
Wir können die Elemente aus A und aus B in Tupeln zusammenfassen:
Jedes Tupel kann dann gewichtet werden:
.
Die Greedy-Strategie wäre nun, die Tupel aus E nach Gewicht zu sortieren und das Produkt aus den schwersten Tupeln zu bilden. Dabei muss man natürlich aufpassen, dass man kein Tupel benutzt, das Basis und/oder Exponent enthält, die schon in unser Produkt eingeflossen sind. Damit so etwas nicht passiert, modelliert man sich Unabhängigkeitsmengen .
Jedes muss der Vorschrift genügen, dass zu jedem maximal ein Tupel existiert (und analog auch für B).
Der Greedy-Algorithmus sucht nun ein , das dein Produkt maximiert:
Dabei wird (gierig) stets nach dem schwersten Tupel x in E gesucht, das die bis dato ausgewählte Unabhängigkeitsmenge F' nicht zerstört, d.h. muss seinerseits unabhängig (also Element von U) sein. Ein Knackpunkt hier ist jedoch, dass es sich um ein Optimierungsproblem über einem Produkt handelt. Greedy-Algorithmen optimieren Summen. Das soll in diesem Fall aber der Lösung keinen Abbruch tun.
Greedy bedeutet hier also: Das Tupel aus Basis und Exponent mit den größten Zahlen wird der nächste Faktor. Ob es bessere Kombinationen gibt, ist nicht relevant, d.h. es wird keine erschöpfende Suche betrieben.
|
|
22.01.2008 15:52 |
|
|
|
Ja, gegeben sind zwei Folgen A und B mit jeweils n Elementen aus dem Bereich [1,..,n] der ganzen Zahlen....
Also haben A und B die Form
A = [1,...,n] beliebig sortiert/oder unsortiert
B = [1,...,n] beliebig sortiert/oder unsortiert
uncool. ... da sind ja auch negative dabei ....
ich glaube das muss ichnochmal überdenken ...
ach unsinn ... sind "ganze zahlen aus dem Intervall [1,...,n]
__________________ I'm 71% Megatron!
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von JROppenheimer: 22.01.2008 16:44.
|
|
22.01.2008 16:38 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Aus deinen Angaben folgt nicht, dass die Folgen jede Zahl nur einmal enthalten dürfen. Was ist z.B. damit:
(1, 2, 2, 3, 4, 5, ..., n-1)
|
|
22.01.2008 16:54 |
|
|
|
Du hast Recht, das hab ich übersehen...
Aber ist das Produkt nicht allgemein gültig am größten, wenn ich beide folgen absteigend sortiere?!
__________________ I'm 71% Megatron!
|
|
22.01.2008 23:17 |
|
|
|
|
|
|
|