Algorithmen-Abstraktion und Design: Greedy- und DP-Algorithmen für das Kunstausstellungsproblem

Einführung in die Algorithmen-Abstraktion und das Kunstausstellungsproblem

In diesem Tutorial beschäftigen wir uns mit einem klassischen Problem der Algorithmik: der optimalen Anordnung von n Gemälden auf Plattformen fester Breite W. Jedes Gemälde hat eine Höhe h_i und eine Breite w_i. Die Plattformen können in der Höhe variiert werden, um das höchste Gemälde aufzunehmen. Ziel ist es, die Gesamtsumme der Plattformhöhen zu minimieren. Dieses Problem ist ein hervorragendes Beispiel für Algorithmen-Abstraktion und Design, wie es in der Projektaufgabe COP4533 vorkommt.

Stell dir vor, du kuratierst eine Ausstellung in einer angesagten Galerie – ähnlich wie bei der Planung eines Esports-Turniers, wo Teams (Gemälde) in Gruppen (Plattformen) eingeteilt werden und die Gesamtleistung (Höhe) optimiert werden soll. Oder wie bei der Playlist-Optimierung in Spotify, wo Songs (Gemälde) in Blöcke (Plattformen) gruppiert werden, um die Wiedergabedauer zu minimieren.

Problemdefinition und Spezialfälle

Gegeben sind n Gemälde in fester Reihenfolge. Die Breiten aller Gemälde auf einer Plattform dürfen W nicht überschreiten. Die Kosten einer Plattform sind die maximale Höhe der Gemälde darauf. Gesamtkosten = Summe dieser Maxima.

Es gibt zwei Spezialfälle:

• ProblemS1: Die Höhen sind monoton fallend (h_i ≥ h_j für i < j).
• ProblemS2: Die Höhen sind unimodal mit einem einzigen lokalen Minimum (zuerst fallend, dann steigend).

Für den allgemeinen Fall (ProblemG) gibt es keine monotone Eigenschaft.

Greedy-Algorithmen für Spezialfälle

Algorithmus 1: Greedy für monoton fallende Höhen (ProblemS1)

Die Idee: Gehe die Gemälde von links nach rechts durch. Solange die Breite der aktuellen Plattform plus das nächste Gemälde ≤ W ist, füge es hinzu. Sonst starte eine neue Plattform. Da die Höhen fallen, ist das erste Gemälde auf jeder Plattform das höchste. Dieser Algorithmus läuft in Θ(n) Zeit.

Korrektheit: Da die Höhen monoton fallen, ist auf jeder Plattform das erste Gemälde das höchste. Durch das Greedy-Prinzip wird die Anzahl der Plattformen minimiert, was die Summe der Höhen minimiert, da die Höhen fallen.

Beispiel: n=7, W=10, h=[21,19,17,16,11,5,1], w=[7,1,2,3,5,8,1]. Plattform1: [21,19,17] (Breite 10), Plattform2: [16,11] (Breite 8), Plattform3: [5,1] (Breite 9). Kosten = 21+16+5 = 42.

Algorithmus 2: Greedy für unimodale Höhen (ProblemS2)

Hier müssen wir den Punkt des minimalen Höhenwerts finden (k). Dann wenden wir Algorithmus 1 auf den fallenden Teil (links von k) und einen ähnlichen Greedy auf den steigenden Teil (rechts von k) an, aber von rechts nach links. Laufzeit Θ(n).

Korrektheit: Der fallende Teil wird wie in S1 behandelt. Für den steigenden Teil können wir die Reihenfolge umkehren, sodass die Höhen fallen, und dann Algorithmus 1 anwenden.

Warum Greedy für den allgemeinen Fall versagt

Algorithmus 1 (für S1) funktioniert nicht für ProblemG, weil die Höhen nicht monoton sind. Ein Gegenbeispiel: n=3, W=10, h=[10,1,10], w=[5,5,5]. Greedy würde Plattform1: [10,1] (Breite 10), Plattform2: [10] (Breite 5) → Kosten 10+10=20. Optimal ist [10], [1,10] → Kosten 10+10=20? Nein, optimal ist [10], [1], [10]? W=10, also [10] allein, dann [1,10] passt nicht (5+5=10) → [1] und [10] → Kosten 10+1+10=21. Also Greedy ist besser? Wir brauchen ein besseres Beispiel. Betrachten wir h=[5,10,5], w=[6,4,6], W=10. Greedy: [5,10] (Breite 10) → Kosten 10, dann [5] → Kosten 5, gesamt 15. Optimal: [5], [10,5] (Breite 10) → Kosten 5+10=15. Gleich. Ein anderes: h=[8,10,9], w=[5,5,5], W=10. Greedy: [8,10] passt nicht (5+5=10) → [8], dann [10,9] passt nicht (5+5=10) → [10], [9] → Kosten 8+10+9=27. Optimal: [8], [10], [9] → 27. Kein Unterschied. Tatsächlich versagt Greedy für ProblemG, wenn die Höhen nicht monoton sind und eine spätere hohe Höhe eine frühere niedrige überdeckt. Ein konstruiertes Beispiel: n=4, W=10, h=[1,100,1,100], w=[1,1,1,1]. Greedy: [1,100] (Breite 2) → Kosten 100, dann [1,100] → Kosten 100, gesamt 200. Optimal: [1], [100,1,100] passt nicht? Breite 1+1+1=3≤10 → [1,100,1,100] auf einer Plattform? Breite 4≤10, Kosten 100. Also Greedy ist schlechter. Ein besseres: h=[5,10,6], w=[5,5,5], W=10. Greedy: [5,10] (Breite 10) → Kosten 10, dann [6] → Kosten 6, gesamt 16. Optimal: [5], [10,6] (Breite 10) → Kosten 5+10=15. Also Greedy versagt.

Dynamische Programmierung für den allgemeinen Fall

Algorithmus 3: Naiver Ansatz (Θ(n·2^{n-1}))

Probiere alle möglichen Aufteilungen der Sequenz in Plattformen aus. Es gibt 2^{n-1} Möglichkeiten (Schnitte zwischen den Gemälden). Für jede Aufteilung berechne die Kosten in O(n).

Algorithmus 4: DP mit Θ(n^3) oder Θ(n^2·W)

Definiere dp[i] = minimale Kosten für die ersten i Gemälde. Für jedes i betrachte alle j < i, sodass die Breite von j+1 bis i ≤ W ist. Setze dp[i] = min(dp[j-1] + max_{k=j..i} h_k). Laufzeit O(n^3), da für jedes i alle j und das Maximum in O(n) berechnet werden. Optimierung: Vorberechnung der Maxima in O(n^2) → O(n^2). Oder mit Breitenbeschränkung W: dp[i] = min_{j: sum_{k=j..i} w_k ≤ W} (dp[j-1] + max_{k=j..i} h_k).

Algorithmus 5: DP mit Θ(n^2) durch geschickte Vorberechnung

Nutze die Tatsache, dass für jedes i die möglichen Startpunkte j durch die Breitenbeschränkung begrenzt sind (Fenster variabler Länge). Mit einem Stack kann man die Maxima effizient aktualisieren, aber einfacher: Vorberechnung der Summen und Maxima in O(n^2) und DP in O(n^2).

Implementierung und Performance-Analyse

Hier ein Beispiel für Algorithmus 1 in Python:

def greedy_s1(n, W, h, w):
    plattformen = []
    i = 0
    while i < n:
        breite = 0
        max_h = 0
        start = i
        while i < n and breite + w[i] <= W:
            breite += w[i]
            max_h = max(max_h, h[i])
            i += 1
        plattformen.append((start, i-1, max_h))
    return sum(p[2] for p in plattformen)

Für Algorithmus 2 (unimodal): Finde zuerst das Minimum (oder das Tal). Teile die Sequenz in zwei Teile: links fallend, rechts steigend. Wende Algorithmus 1 auf den linken Teil an. Für den rechten Teil kehre die Reihenfolge um (damit die Höhen fallen) und wende Algorithmus 1 an.

Experimentelle Studie

Generiere zufällige Eingaben mit n=1000,2000,...,5000. Miss die Laufzeit von Program1 und Program2. Erwartung: Beide laufen in O(n), daher lineare Laufzeit. Plots zeigen Zeit vs. n. Für die DP-Algorithmen (Program3,4,5) erwarte quadratische oder kubische Laufzeiten.

Beobachtung: Greedy-Algorithmen sind extrem schnell und einfach zu implementieren, aber nur für Spezialfälle korrekt. DP-Algorithmen sind universell, aber rechenintensiver.

Fazit und Lernziele

Dieses Projekt lehrt die Bedeutung von Algorithmen-Abstraktion: Durch das Erkennen von Mustern (Monotonie, Unimodalität) können wir effiziente Greedy-Algorithmen entwerfen. Für komplexere Fälle ist dynamische Programmierung das Mittel der Wahl. Die experimentelle Studie zeigt, wie wichtig eine gute Implementierung und Analyse ist.

Verbindung zu aktuellen Trends: Ähnliche Optimierungsprobleme treten in der KI-gestützten Logistik auf, z.B. bei der Beladung von Lieferwagen oder der Planung von Cloud-Computing-Ressourcen. Auch in der Spieleentwicklung (z.B. Level-Design) oder bei YouTube-Werbeblöcken (Minimierung der Unterbrechungen) finden sich solche Fragestellungen.

Suchbegriffe: Greedy-Algorithmus, dynamische Programmierung, Kunstausstellungsproblem, Algorithmen-Abstraktion, COP4533, O(n) Algorithmus, DP mit Memoization, Performance-Analyse, Randomisierte Tests, Optimierung, Sequenzpartitionierung.