Wir haben ein Grundstück, auf das wir ein Gebäude bauen möchten. Dieses Grundstück ist jetzt aber keine komplett leere Fläche, sondern beinhaltet auch Hindernisse wie zum Beispiel Bäume. Da wir diese nur ungern fällen möchten, suchen wir eine möglichst große rechteckige Teilfläche, auf der wir unser Gebäude platzieren können, ohne ein Hindernis entfernen zu müssen. Es interessieren uns Koordinaten und Breite bzw. Höhe des Rechtecks.

Zuerst bekommen wir die Seitenlängen des Grundstücks als Eingabe:

Danach folgt die Eingabe der Fläche. Diese wird dabei in Form von Zeichen dargestellt. . steht für ein freies Feld, # für ein belegtes. Wir suchen nun den größten rechteckigen Block, der nur aus freien Feldern (.) besteht. Als Beispiel nehmen wir folgendes Grundstück an:

..#..#
......
......
.....#
......
#.....
......
......

Die gesamte Eingabe besteht somit aus diesen Informationen:

6 8
..#..#
......
......
.....#
......
#.....
......
......

Ein relativ einfaches, aber rechnerisch sehr aufwendiges Verfahren ist es, alle möglichen Positionen und Größen durchzuprobieren. Gestartet wird dazu an einem fixen Ausgangspunkt (z.B. links oben). Als nächstes werden verschiedene Dimensionen durchprobiert. Eine pessimistische Strategie ist es, mit einem 1×1 Bereich zu starten und diesen Schritt für Schritt zu vergrößern. Umgekehrt kann natürlich auch in einer optimistischen Variante mit der kompletten verfügbaren Fläche gestartet werden, die dann verkleinert wird. Für den ausgewählten Bereich wird schließlich überprüft, ob sich darin ein Hindernis befindet.

Beginnen wir wie beschrieben links oben mit einer minimalen Fläche:

Alle Felder des Bereichs werden einzeln auf Hindernisse überprüft. Da das einzige Feld im Bereich frei ist und wir bisher noch keine mögliche Lösung haben, speichern wir uns diesen Bereich als bisher beste Lösung. Nun wird versucht den überprüften Bereich horizontal zu vergrößern:

Wir sind abermals erfolgreich. Da der Bereich größer als die bisher bekannte beste Lösung ist, ersetzen wir diese mit dem aktuellen Bereich. Danach erweitern wir erneut horizontal:

Nachdem wir nun auf ein Hindernis gestoßen sind, brechen wir in horizontaler Richtung ab und vergrößern die überprüfte Fläche in vertikaler Richtung.

Das Verfahren wird nun wie zuvor in horizontaler Richtung weitergeführt:

Wurden alle möglichen Dimensionen von dieser Startposition durchprobiert, bewegen wir uns horizontal weiter:

Sind alle horizontalen Möglichkeiten überprüft, wechseln wir horizontal in den nächsten Bereich:

Auf diese Weise überprüfen wir die komplette Fläche mit allen möglichen Startpositionen und Dimensionen. Wir werden für das gezeigte Beispiel folgende Lösung finden:

Eine Implementierung könnte so aussehen:

n6_free_area.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
 
const char OBSTACLE_CHARACTER = '#';
 
int main()
{
    // Dimensionen des Grundstücks einlesen
    int width, height;
    scanf("%d %d\n", &width, &height);
 
    // Grundstücks einlesen
    char *area = (char *)malloc(width * height * sizeof(char));
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
            area[i * width + j] = getchar();
        // Newline ignorieren
        getchar();
    }
 
    // Noch keine passende Fläche gefunden, deshalb mit -1 vorbelegt
    int solution_x = -1, solution_y = -1, solution_w = -1, solution_h = -1;
    bool solution_found = false;
 
    // Durch alle Zeilen iterieren (y-Koordinate)
    for (int start_y = 0; start_y < height; start_y++)
    {
        // Durch alle Spalten iterieren (x-Koordinate)
        for (int start_x = 0; start_x < width; start_x++)
        {
            // Alle möglichen Höhen versuchen, beginnend bei der kleinsten
            for (int end_y = start_y; end_y < height; end_y++)
            {
                // Alle möglichen Breiten versuchen, beginnend bei der kleinsten
                for (int end_x = start_x; end_x < width; end_x++)
                {
                    // Hindernisse im ausgewählten Bereich zählen
                    unsigned int num_window_obstacles = 0;
                    for (int window_y = start_y;
                         window_y <= end_y && num_window_obstacles == 0;
                         window_y++)
                    {
                        for (int window_x = start_x;
                             window_x <= end_x && num_window_obstacles == 0;
                             window_x++)
                        {
                            if(area[window_y * width + window_x] == OBSTACLE_CHARACTER)
                                num_window_obstacles++;
                        }
                    }
 
                    // Überprüfen, ob in dem Bereich Hindernisse gefunden wurden
                    if (num_window_obstacles == 0)
                    {
                        // Prüfen, ob das neue Feld größer ist als das bisher
                        // größte gefundene. Gegebenenfalls Koordinaten und
                        // Größe speichern.
                        int candidate_w = end_x - start_x + 1;
                        int candidate_h = end_y - start_y + 1;
                        if (!solution_found || ((candidate_w * candidate_h) > (solution_w * solution_h)))
                        {
                            solution_found = true;
                            solution_x = start_x;
                            solution_y = start_y;
                            solution_w = candidate_w;
                            solution_h = candidate_h;
                        }
                    }
                    else
                    {
                        // Die Schleifen verkleinern die zu überprüfende Fläche.
                        // In der innersten Schleife kann somit keine größere Fläche
                        // mehr gefunden werden.
                        break;
                    }
                }
            }
        }
    }
 
    // Ergebnis ausgeben
    if (solution_found)
        printf("x: %d y: %d w: %d h: %d -> %d\n", solution_x,
                                                  solution_y,
                                                  solution_w,
                                                  solution_h,
                                                  solution_w * solution_h);
    else
        printf("Keine freie Flaeche gefunden");
 
    free(area);
    return 0;
}

Ausgabe:

x: 1 y: 1 w: 4 h: 7 -> 28

Das Ergebnis sieht schon mal sehr gut aus. Aber am Code fällt sofort die Verschachtelung von 6 Schleifen auf. Wir haben hier also einen Algorithmus der Ordnung O(n6), der sehr schnell anwächst.

So möchten wir unser Programm aber nicht einfach stehen lassen. Es liefert zwar die richtige Lösung, die Berechnung ist aber sehr aufwendig und der Code durch die sechs verschachtelten Schleifen schon recht unleserlich.

Die Aufsummierung der Hindernisse in einem Bereich ist eine Operation, die im Laufe der äußeren vier Iterationen immer wieder durchgeführt wird. Diesen Schritt können wir wie bereits im ersten Beispiel über die Präfixsumme in konstanter Zeit durchführen.

Anstatt für die einzelnen Felder den Status (frei bzw. belegt) zu speichern, zählen wir alle Hindernisse, die bis zu dem aktuellen Feld gefunden wurden. Dabei berücksichtigen wir das aktuelle Feld, sowie alle Felder links bzw. oberhalb des aktuellen Feldes. Sehen wir uns nochmals das ursprüngliche Beispiel an:

6 8
..#..#
......
......
.....#
......
#.....
......
......

Würden wir für das strichliert umrandete Feld an Index 3/3 abfragen, wäre das Ergebnis die Anzahl aller Hindernisse im markierten Bereich und somit 1.

Da wir ein quadratisches Iterieren für jedes einzelne Feld vermeiden wollen, nutzen wir an dieser Stelle bereits die Präfixsumme aus. Beginnt man die Summen links oben zu berechnen, sind alle Summen im rot markierten Bereich bereits bekannt.

Als Startwert sehen wir das einzelne aktuelle Feld. Befindet sich auf dem Feld ein Hindernis, merken wir uns dafür die Zahl 1, ansonsten 0. Dazu addieren wir nun Summen der Feld links bzw. oberhalb der aktuellen Position. Zur Orientierung sind in den folgenden Grafiken die Bereiche links (blau) und oben (grün) sowie das aktuell zu berechnende rote Feld eingezeichnet.

Da allerdings nun ein Teilbereich doppelt addiert wurde, müssen wir die Summe des Feldes links oberhalb (gelb) abziehen.

Hinweis: Die Felder am linken bzw. oberen Rand der Fläche haben eigentlich keine Nachbarn. Als bequeme Lösung allokiert man den Speicher für diese Bereiche und setzt alle Summen auf 0.

Die Summen zu dieser Eingabe sieht entsprechend so aus:

0 0 1 1 1 2
0 0 1 1 1 2
0 0 1 1 1 2
0 0 1 1 1 3
0 0 1 1 1 3
1 1 2 2 2 4
1 1 2 2 2 4
1 1 2 2 2 4

Mit dieser Hilfsberechnung kann ein Bereich nun in konstanter Zeit auf Hindernisse überprüft werden und die Laufzeit auf eine Ordnung von O(n4) reduziert werden. Nachdem uns nur die Abfrage auf Hindernisse interessiert, brauchen wir die ursprüngliche Eingabe nicht und können direkt die Summen berechnen.

Die Berechnung der Hindernisse kann ähnlich wie bei den Summen über Operationen mit benachbarten Summen durchgeführt werden. Wichtig ist, dass Felder links bzw. oberhalb vom zu überprüfenden Bereich abgezogen werden und mehrfache Subtraktionen korrigiert werden.

Als Beispiel sehen wir uns die Berechnung der Hindernisse der Fläche von 2/2 bis 3/4 an:

Gestartet wird mit der kompletten Fläche links oberhalb des Bereichs:

Danach ziehen wir die Bereiche seitlich der zu überprüfenden Fläche ab:

Zuletzt wird der doppelt abgezogene Bereich noch dazuaddiert:

Wir können die Operationen auch anders darstellen:

- - + =

Eine mögliche Implementierung könnte folgendermaßen aussehen:

n4_free_area.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
    // Dimensionen der Fläche einlesen
    int width, height;
    scanf("%d %d\n", &width, &height);
 
    // Fläche einlesen
    int *sum = (int *)malloc((height + 1) * (width + 1) * sizeof(int));
    memset(sum, 0, (height + 1) * (width + 1) * sizeof(int));
 
    for (int i = 1; i <= height; i++)
    {
        for (int j = 1; j <= width; j++)
        {
            int current_value = (getchar() == '#') ? 1 : 0;
            sum[i * (width + 1) + j] = current_value +
                                       sum[(i - 1) * (width + 1) + j] +
                                       sum[i * (width + 1) + j - 1] -
                                       sum[(i - 1) * (width + 1) + j - 1];
        }
        // Newline ignorieren
        getchar();
    }
 
    // Noch keine passende Fläche gefunden, deshalb mit -1 vorbelegt
    int solution_x = -1, solution_y = -1, solution_w = -1, solution_h = -1;
    bool solution_found = false;
 
    // Durch alle Zeilen iterieren (y-Koordinate)
    for (int start_y = 1; start_y <= height; start_y++)
    {
        // Durch alle Spalten iterieren (x-Koordinate)
        for (int start_x = 1; start_x <= width; start_x++)
        {
            // Alle möglichen Höhen versuchen, beginnend bei der kleinsten
            for (int end_y = start_y; end_y <= height; end_y++)
            {
                // Alle möglichen Breiten versuchen, beginnend bei der kleinsten
                for (int end_x = start_x; end_x <= width; end_x++)
                {
                    // Hindernisse im ausgewählten Bereich berechnen
                    unsigned int num_window_obstacles = sum[end_y * (width + 1) + end_x] -
                                                        sum[end_y * (width + 1) + start_x - 1] -
                                                        sum[(start_y - 1) * (width + 1) + end_x] +
                                                        sum[(start_y - 1) * (width + 1) + start_x - 1];
                    // Überprüfen, ob in dem Bereich Hindernisse gefunden wurden
                    if (num_window_obstacles == 0)
                    {
                        // Prüfen, ob das neue Feld größer ist als das bisher
                        // größte gefundene. Gegebenenfalls Koordinaten und
                        // Größe speichern.
                        int candidate_w = end_x - start_x + 1;
                        int candidate_h = end_y - start_y + 1;
                        if (!solution_found || (candidate_w * candidate_h) > (solution_w * solution_h))
                        {
                            solution_found = true;
                            solution_x = start_x - 1;
                            solution_y = start_y - 1;
                            solution_w = candidate_w;
                            solution_h = candidate_h;
                        }
                    }
                    else
                    {
                        // Die Schleifen verkleinern die zu überprüfende Fläche.
                        // In der innersten Schleife kann somit keine größere Fläche
                        // mehr gefunden werden.
                        break;
                    }
                }
            }
        }
    }
 
    // Ergebnis ausgeben
    if (solution_found)
        printf("x: %d y: %d w: %d h: %d -> %d\n", solution_x,
                                                  solution_y,
                                                  solution_w,
                                                  solution_h,
                                                  solution_w * solution_h);
    else
        printf("Keine freie Flaeche gefunden");
 
    return 0;
}

Wie bereits zuvor, möchten wir die Performance der beiden Implementierungen vergleichen und erstellen ein Programm zur zufälligen Generierung von Eingabedaten.

2d_cumulative_sum_generator.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
// Bestimmt wie wahrscheinlich ein Hindernis auftritt.
// Je größer die Zahl, desto unwahrscheinlicher treten
// Hindernisse auf.
const unsigned short OBSTACLE_FACTOR = 20;
const char OBSTACLE_SYMBOL = '#';
const char FREE_SYMBOL = '.';
 
int main(int argc, char *argv[])
{
    if (argc != 3)
    {
        printf("Usage: %s width height\n", argv[0]);
        return 1;
    }
 
    // Der Zufallsgenerator wird mit der aktuellen Zeit initialisiert.
    srand(time(NULL));
 
    // Breite und Höhe des zu generierenden Feldes werden als
    // Kommandozeilenparameter übergeben.
    int width = atoi(argv[1]),
        height = atoi(argv[2]);
 
    // Dimensionen des Grundstücks ausgeben.
    printf("%d %d\n", width, height);
    // In den Schleifen folgt die zufällige Generirung
    // und Ausgabe des Grundstücks.
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Eine Zufallszahl wird generiert. Ist sie durch
            // den konstanten Faktor teilbar, befindet sich
            // an dieser Stelle ein Hindernis.
            bool is_obstacle = rand() % OBSTACLE_FACTOR == 0;
            if (is_obstacle)
                printf("%c", OBSTACLE_SYMBOL);
            else
                printf("%c", FREE_SYMBOL);
        }
        printf("\n");
    }
 
    return 0;
}

Das Programm bekommt die gewünschte Flächengröße als Kommandozeilenparameter und schreibt die generierten Daten auf die Standardausgabe. Für reproduzierbare Testläufe empfiehlt es sich deshalb, die Ergebnisse in einer Datei zwischenzuspeichern:

$ ./2d_cumulative_sum_generator 6 8 > area_6x8.txt

Generieren wir nun ein paar größere Datensätze mit quadratischen Dimensionen, um die Performance besser einschätzen zu können.

$ for s in `seq 500 500 3000`; do ./2d_cumulative_sum_generator "$s" "$s" > "area_${s}x${s}.txt"; done

Es handelt sich bei diesen Tests um einzelne Ausführungen mit vorangestellter Zeitmessung über time. Es geht hier nicht darum eine möglichst genaue Messung zu schaffen, sondern die praktische Größenordnung des Unterschieds einschätzen zu können.

Die Performance der n⁶ Implementierung hängt auch deutlich von der Häufigkeit der Hindernisse ab. Die strengen Bedinungen in den innersten beiden Schleifen stoppen beim ersten gefundenen Hindernis. Weiters wird auch die Vergrößerung der zweiten Dimension abgebrochen, wenn ein Hindernis gefunden wurde. Treten Hindernisse häufig auf, ergeben sich dadurch weniger Schleifendurchläufe. In Extremfällen kann sich die Performance sogar an jene der n⁴ Implementierung annähern.

• Präfixsumme
• Summierung von Aktienpositionen