Brute Force und Rekursion in C: Motorabschaltung mit Permutationen

Einleitung: Wenn der Motor nicht stoppt – Brute Force zur Rettung

Stell dir vor, du bist Teil eines Rettungsteams auf einem havarierten Schiff. Der Motor läuft heiß, die Notabschaltung versagt, und jede Sekunde zählt. Deine Aufgabe: Finde die Reihenfolge von Aktionen (z. B. Schaum einsprühen, Luftzufuhr kappen, Strom trennen), die die Motortemperatur maximal senkt. Dieses Szenario ist die Grundlage für das Projekt „Engine Shutdown“ aus dem Kurs COP3502c. In diesem Tutorial lernst du, wie du mit Brute Force und Rekursion in C alle möglichen Aktionsreihenfolgen durchprobierst und die beste auswählst – ein klassisches Permutationsproblem.

Das Problem verstehen: Temperaturabhängigkeiten und Reihenfolge

Gegeben sind n Aktionen (1 ≤ n ≤ 11). Jede Aktion i hat einen Basis-Temperaturänderungswert (kann positiv oder negativ sein). Zusätzlich gibt es eine n×n-Matrix D, wobei D[i][j] die zusätzliche Temperaturänderung angibt, wenn Aktion i nach Aktion j ausgeführt wird. Das Ziel: Finde die Reihenfolge (Permutation) der Aktionen, die die maximale Gesamtabkühlung erzielt. Ein Beispiel: Bei 3 Aktionen mit Basiswerten [-10, -20, 3] und bestimmten Abhängigkeiten ergibt die Reihenfolge [1,3,2] eine Abkühlung von 57 Einheiten – das Optimum.

Warum Brute Force? Die Macht der vollständigen Suche

Da n maximal 11 ist, gibt es 11! = 39.916.800 Permutationen – im heutigen Gaming-Kontext vergleichbar mit dem Durchsuchen aller möglichen Spielzüge in einem rundenbasierten Strategiespiel. Moderne Computer schaffen das in Sekunden. Brute Force ist hier der einfachste und sicherste Weg, ohne komplizierte Optimierung. In der KI-Entwicklung (z. B. bei ChatGPT oder Machine Learning) werden ähnliche exhaustive-Suchen oft als Baseline verwendet.

Rekursion in C: Permutationen generieren

Wir schreiben eine rekursive Funktion, die alle Reihenfolgen durchprobiert. Das Grundprinzip: Wähle eine noch nicht verwendete Aktion aus, füge sie an die aktuelle Reihenfolge an, rufe die Funktion rekursiv für die restlichen Aktionen auf. So entstehen alle n! Permutationen. Hier ein Code-Gerüst:

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 11

int n;
int base[MAX_N];
int dep[MAX_N][MAX_N];
int best_order[MAX_N];
int best_temp = -1000000;
bool used[MAX_N];
int current_order[MAX_N];

void permute(int pos, int current_temp) {
    if (pos == n) {
        if (current_temp > best_temp) {
            best_temp = current_temp;
            for (int i = 0; i < n; i++) best_order[i] = current_order[i];
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            current_order[pos] = i;
            int new_temp = current_temp + base[i];
            // add dependencies from previous actions to this one
            for (int j = 0; j < pos; j++) {
                new_temp += dep[i][current_order[j]];
            }
            permute(pos + 1, new_temp);
            used[i] = false;
        }
    }
}

Optimierung: Basiswerte ignorieren? Ein Trick

Im Projekt wird darauf hingewiesen, dass die Basiswerte (zweite Eingabezeile) ignoriert werden können. Warum? Weil sie in jeder Permutation gleich oft vorkommen – die Summe der Basiswerte ist konstant. Für die Optimierung reicht es, nur die Abhängigkeiten zu betrachten. Das vereinfacht den Code und spart Rechenzeit. In der Praxis (z. B. bei Finanzmodellen oder App-Entwicklung) ist es üblich, konstante Terme zu entfernen.

Vollständiges Beispiel: Eingabe und Ausgabe

Betrachten wir den ersten Sample-Input:

Die rekursive Suche liefert die optimale Reihenfolge 1 3 2 (indiziert ab 1) mit einer Gesamtabkühlung von 57. Unser Code gibt diese Reihenfolge aus.

Trendbezug: Von der Schifffahrt zum Gaming

Stell dir vor, du entwickelst ein Battle-Royale-Spiel: Jede Aktion ist eine Fähigkeit (z. B. „Feuerball“, „Heilung“), und die Abhängigkeiten sind Kombos (z. B. „Feuerball“ nach „Eis“ verursacht mehr Schaden). Die optimale Reihenfolge der Fähigkeiten maximiert den Schaden – genau wie hier die Abkühlung. Solche Permutationsprobleme tauchen auch in der KI-gestützten Spieleentwicklung auf, etwa bei der Ressourcenplanung in Strategiespielen.

Häufige Fehler und wie du sie vermeidest

Doppeltes Verwenden von Aktionen: Stelle sicher, dass du jede Aktion nur einmal verwendest. Verwende ein used[]-Array.
Falsche Indexierung: Die Aufgabenstellung verwendet 1-basierte Indizes. Achte darauf, bei der Ausgabe +1 zu addieren.
Integer-Überlauf: Temperaturen können bis ±100.000 betragen, bei 11 Aktionen maximal 11 * 100.000 = 1.100.000 – das passt in einen int (32 Bit).
Vergessen der Abhängigkeiten: Jede neue Aktion bekommt Boni von allen vorherigen Aktionen, nicht nur von der letzten.

Erweiterungen und Ausblick

Mit n ≤ 11 ist Brute Force perfekt. Für größere n bräuchtest du dynamische Programmierung (ähnlich dem Traveling Salesman Problem). In der Finanzwelt werden solche Algorithmen genutzt, um die optimale Reihenfolge von Transaktionen zu finden. In der Robotik planen Roboter ihre Bewegungen durch Permutationen von Aktionen.

Fazit

Mit Rekursion und Brute Force hast du ein mächtiges Werkzeug, um das COP3502c Engine Shutdown-Problem zu lösen. Der Schlüssel liegt im Verständnis der Permutationen und der geschickten Handhabung von Abhängigkeiten. Dieses Muster begegnet dir immer wieder – sei es in Spielen, KI oder Finanzen. Viel Erfolg beim Coden!