Produktmaximierung, Greedy, lineares Sortieren

21.01.2008, 17:21

JROppenheimer

Produktmaximierung, Greedy, lineares Sortieren

Sehr geehrte Damen und Herren smile

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 ...

22.01.2008, 15:52

Auf diesen Beitrag antworten »

Tobias

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:

$[latex]E = \big\{ (a, b) \mid a \in A, \; b \in B \big\}[/latex]$

Jedes Tupel kann dann gewichtet werden:

[latex]w(a, b) = a^b[/latex]

.

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 $[latex]U \subseteq 2^E[/latex]$ .
Jedes $[latex]F \in U[/latex]$ muss der Vorschrift genügen, dass zu jedem $[latex]a \in A[/latex]$ maximal ein Tupel $[latex](a, y) \in F[/latex]$ existiert (und analog auch für B).
Der Greedy-Algorithmus sucht nun ein $[latex]F \in U[/latex]$ , das dein Produkt maximiert:
$[latex]\prod_{x \in F}w(x) \to \max[/latex]$
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. $[latex]F = F' \cup \{x\}[/latex]$ 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, 16:22

Auf diesen Beitrag antworten »

JROppenheimer

Zitat:

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?)

Da fängts ja schon an. Hätte spontan folgendes gesagt:

n^n * (n-1)^(n-1) * ... *3^3 *2^2*1^1 > n^(n-1) * (n-1)^n * ...

Das kann man doch sicher algemein mit Landau begründen sowas wie

n^n*(n-1)^(n-1)*O( (n-1)^(n-1)) > n^(n-1) * (n-1)^(n) * O((n-1^n-1))

Oder?

Wenn ich nur das zeigen muss/kann/soll, dann kann ich danach ja einfach mit Radixsort argumentieren, der ja schon bewiesen wurde...

wie mach ich denn hier latex kram???

22.01.2008, 16:32

Auf diesen Beitrag antworten »

Tobias

Kommt jede Zahl nur einmal vor?

Formeln macht man zwischen

code:
1:	[latex] [/latex]

Klammern.

22.01.2008, 16:38

Auf diesen Beitrag antworten »

JROppenheimer

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]

22.01.2008, 16:54

Auf diesen Beitrag antworten »

Tobias

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, 23:17

Auf diesen Beitrag antworten »

JROppenheimer

Du hast Recht, das hab ich übersehen...

Aber ist das Produkt nicht allgemein gültig am größten, wenn ich beide folgen absteigend sortiere?!

Neue Frage »

Antworten »

Produktmaximierung, Greedy, lineares Sortieren

Verwandte Themen