Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen

Ein Suchproblem ist ein Sechstupel

P = (S, s₀, A, T, G, c),

das Folgendes erfüllt:

1. S ist eine nichtleere Menge; ihre Elemente nennen wir Zustände;
2. s₀ ∈ S; diesen Zustand nennen wir den Anfangszustand;
3. A ordnet jedem Zustand s ∈ S eine endliche Menge A(s) der im Zustand s anwendbaren Aktionen zu; sei 𝒟 = {(s, a) : s ∈ S, a ∈ A(s)} die Menge aller Paare „Zustand, darin anwendbare Aktion“;
4. T : 𝒟 → S ist die Übergangsfunktion; für (s, a) ∈ 𝒟 ist der Zustand s′ = T(s, a) ein Nachfolger des Zustands s (nach der Aktion a);
5. G ⊆ S ist die Menge der Zielzustände;
6. c : 𝒟 → ℝ⁺ = (0, ∞) sind die Aktionskosten: c(s, a) > 0 sind die Kosten der Anwendung der Aktion a im Zustand s.

Das Problem sagt also genau, wo wir beginnen, welche Züge uns in jedem Zustand zur Verfügung stehen, wohin welcher Zug führt, was er kostet und wann wir am Ziel sind.

Sei P = (S, s₀, A, T, G, c) ein Suchproblem und k ∈ ℕ₀. Ein Pfad der Länge k vom Anfangszustand ist eine Folge

π = (s₀, a₁, s₁, a₂, …, a_k, s_k),

sodass für jedes i = 1, …, k gilt: a_i ∈ A(s_i−1) und s_i = T(s_i−1, a_i). (Für k = 0 ist der Pfad nur (s₀).)

Die Pfadkosten von π sind die Summe der Kosten seiner Aktionen:

g(π) = ∑_i=1^k c(s_i−1, a_i).

Ein Pfad π ist eine Lösung genau dann, wenn s_k ∈ G. Sei Π die Menge aller Lösungen. Ist Π ≠ ∅, so sind die optimalen Kosten

C* = min {g(π) : π ∈ Π}

(sofern das Minimum existiert; bei Problemen mit endlich vielen Zuständen wie unserem Labyrinth existiert es immer), und eine Lösung π ist optimal genau dann, wenn g(π) = C*. Eine optimale Lösung ist also eine Lösung, die nicht teurer ist als irgendeine andere Lösung.

Acht Plättchen und das leere Feld lassen sich auf 9! = 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362 880 Arten auf die neun Felder verteilen. Durch Züge erreichst du aber nur die Hälfte davon: Schreibst du die Plättchen zeilenweise auf (ohne das leere Feld), erhält jeder Zug, ob in dieser Reihenfolge die Zahl der Paare „größeres vor kleinerem“ gerade oder ungerade ist. Ein waagerechter Zug ändert die Reihenfolge überhaupt nicht, ein senkrechter Zug lässt ein Plättchen über zwei andere springen und ändert die Zahl solcher Paare um 0 oder um ±2. In einen Zustand mit entgegengesetzter Parität kommt man deshalb nicht. Dass genau die Hälfte der Zustände erreichbar ist (beim 15-Puzzle mit einer etwas komplizierteren Invariante, in die auch die Zeile des leeren Feldes eingeht), bewiesen W. W. Johnson und W. E. Story im Jahr 1879.

8-Puzzle: 9!/2 = 362 880/2 = 181 440 Zustände.
15-Puzzle: 16!/2 = 20 922 789 888 000/2 = 10 461 394 944 000 ≈ 1,05 · 10¹³ Zustände — über zehn Billionen.

Ein Feld schreiben wir als Paar (r, s) — Zeile r ∈ {0, …, 8}, Spalte s ∈ {0, …, 13}. Sei Z die Menge der Wände und B die Menge der Schlammfelder.

• Zustände: S = ({0, …, 8} × {0, …, 13}) ∖ Z — alle Felder außer den Wänden.
• Anfangszustand: s₀ = (0, 0). Ziel: G = {(8, 13)}.
• Verschiebungen: ↑ = (−1, 0), → = (0, 1), ↓ = (1, 0), ← = (0, −1). Im Zustand (r, s) ∈ S anwendbar sind die Aktionen, die auf ein Feld innerhalb des Gitters führen, das keine Wand ist: A((r, s)) = {(Δr, Δs) ∈ {↑, →, ↓, ←} : (r + Δr, s + Δs) ∈ S}.
• Übergang: T((r, s), (Δr, Δs)) = (r + Δr, s + Δs), z. B. T((r, s), →) = (r, s + 1).
• Kosten: c(x, a) = 5, falls T(x, a) ∈ B, sonst c(x, a) = 1 — bezahlt wird für das Feld, das man betritt.
• Aufgabe: eine Lösung mit den geringsten Kosten C* finden.

Sei P = (S, s₀, A, T, G, c) ein Suchproblem. Für einen Zustand s ∈ S bezeichnen wir die Menge seiner Nachfolger mit

N(s) = {T(s, a) : a ∈ A(s)}.

Ein Suchalgorithmus hält zu jedem Zeitpunkt seines Laufs zwei Mengen von Zuständen:

1. die Randmenge (frontier) F ⊆ S — Zustände, die der Algorithmus schon entdeckt hat (zu ihnen führt ein gefundener Pfad von s₀), aber noch nicht expandiert hat; am Anfang ist F = {s₀};
2. die geschlossenen Zustände E ⊆ S — Zustände, die er schon expandiert hat; am Anfang ist E = ∅.

Einen Zustand s ∈ F zu expandieren heißt, diese beiden Änderungen (in dieser Reihenfolge) vorzunehmen:

E ← E ∪ {s},   F ← (F ∖ {s}) ∪ (N(s) ∖ E).

Der expandierte Zustand wandert also aus der Randmenge zu den geschlossenen, und in die Randmenge kommen diejenigen seiner Nachfolger hinzu, die noch nicht expandiert wurden.

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c). Ausgabe: eine Lösung (ein Pfad von s₀ zu einem Zustand aus G) oder die Meldung „es gibt keine Lösung“.

Die Breitensuche (BFS) ist das gemeinsame Gerüst von oben, in dem die Randmenge F eine Warteschlange ist (FIFO, first in — first out):

1. F ← (s₀), E ← ∅.
2. Ist F leer, halte an: Es gibt keine Lösung.
3. Entnimm aus F den Zustand s, der als erster hineingekommen ist.
4. Ist s ∈ G, halte an und gib den Pfad von s₀ nach s zurück.
5. Expandiere s: Füge ihn zu E hinzu und reihe jeden Nachfolger s′ ∈ N(s), der weder in E noch in F ist, ans Ende von F ein. Fahre mit Schritt 2 fort.

Eigenschaften. Sei d(s) die Tiefe des Zustands s — die kleinste Länge eines Pfads von s₀ nach s. Die BFS expandiert die Zustände in nicht fallender Reihenfolge von d(s) und gibt deshalb die Lösung mit den wenigsten Aktionen zurück. Sei b = max_{s ∈ S} |A(s)| der Verzweigungsfaktor (die größte Zahl von Nachfolgern eines Zustands) und d die Tiefe der flachsten Lösung. Dann erzeugt die BFS höchstens b + b² + … + b^d = O(b^d) Zustände und hält ebenso viele im Speicher.

Der BFS-Weg hat 25 Schritte, davon 3 in den Schlamm: g = 22 · 1 + 3 · 5 = 22 + 15 = 37.

Die Größe der Welle für den Verzweigungsfaktor b = 10: In der Tiefe d = 5 sind es 10 + 100 + 1 000 + 10 000 + 100 000 = 111 110 Zustände, in der Tiefe d = 10 schon 11 111 111 110 ≈ 1,1 · 10¹⁰. Würde ein Zustand 1 kB Speicher belegen, bräuchte die Welle in der Tiefe 10 über 11 TB. Jede weitere Etage verzehnfacht das.

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c). Ausgabe: eine Lösung oder die Meldung „es gibt keine Lösung“.

Die Tiefensuche (DFS) ist das gemeinsame Gerüst von oben, in dem die Randmenge F ein Stapel ist (LIFO, last in — first out):

1. F ← (s₀), E ← ∅.
2. Ist F leer, halte an: Es gibt keine Lösung.
3. Entnimm aus F den Zustand s, der zuletzt hineingekommen ist (die Spitze des Stapels).
4. Ist s ∈ G, halte an und gib den Pfad von s₀ nach s zurück.
5. Expandiere s: Füge ihn zu E hinzu und lege jeden Nachfolger s′ ∈ N(s) ∖ E oben auf F. Fahre mit Schritt 2 fort.

Eigenschaften. Sei b der Verzweigungsfaktor und m die größte Tiefe des Zustandsraums (die größte Länge eines Pfads ohne wiederholte Zustände, gegebenenfalls ∞). In der Baumvariante (ohne die Menge E, Wiederholungen werden nur auf dem aktuellen Zweig geprüft) hält die DFS nur den aktuellen Zweig und seine Geschwister im Speicher: O(b · m) Zustände. Die Zeit beträgt im schlimmsten Fall O(b^m). Die DFS ist nicht optimal und in einem unendlichen Raum nicht einmal vollständig — sie kann endlos absteigen.

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c). Ausgabe: eine Lösung mit den wenigsten Aktionen (sofern es eine Lösung gibt).

Für ℓ ∈ ℕ₀ bezeichne DLS(ℓ) (depth-limited search) die Tiefensuche, die keine Zustände in der Tiefe ℓ oder größer expandiert — Pfade länger als ℓ untersucht sie also nicht. Iterative Vertiefung (IDDFS):

1. ℓ ← 0.
2. Starte DLS(ℓ).
3. Hat DLS(ℓ) eine Lösung gefunden, halte an und gib sie zurück.
4. ℓ ← ℓ + 1 und fahre mit Schritt 2 fort.

Abbruchbedingung: das erste ℓ, für das DLS(ℓ) eine Lösung findet; das ist genau die Tiefe d der flachsten Lösung. (Gibt es keine Lösung und ist der Raum unendlich, hält der Algorithmus nicht an.)

Eigenschaften. Sei b der Verzweigungsfaktor und d die Tiefe der flachsten Lösung. Zustände in der Tiefe i ∈ {1, …, d} werden (d − i + 1)-mal erzeugt, insgesamt ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) Zustände — genauso wie bei der BFS, aber mit einem Speicher von nur O(b · d).

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c). Ausgabe: eine Lösung mit den geringsten Kosten oder die Meldung „es gibt keine Lösung“.

Während des Laufs ordnet der Algorithmus jedem entdeckten Zustand n ∈ S eine Zahl g(n) zu — die Kosten des günstigsten bisher gefundenen Pfads von s₀ nach n. Die Randmenge F ist eine Prioritätswarteschlange, geordnet nach g. Kostengesteuerte Suche (UCS, uniform-cost search):

1. F ← {s₀}, g(s₀) ← 0, E ← ∅.
2. Ist F = ∅, halte an: Es gibt keine Lösung.
3. Entnimm aus F den Zustand n mit dem kleinsten g(n).
4. Ist n ∈ G, halte an und gib den gefundenen Pfad nach n zurück (seine Kosten sind g(n)).
5. Füge n zu E hinzu. Für jede Aktion a ∈ A(n) und n′ = T(n, a) ∉ E: Ist n′ ∉ F oder g(n) + c(n, a) < g(n′), setze g(n′) ← g(n) + c(n, a), merke dir n als Vorgänger von n′ und füge n′ in F ein. Fahre mit Schritt 2 fort.

Eigenschaften. Es gebe ein ε > 0, sodass c(s, a) ≥ ε für alle s ∈ S, a ∈ A(s). Dann expandiert die UCS die Zustände in nicht fallender Reihenfolge von g und ist deshalb vollständig und optimal. Die Zahl der expandierten Zustände ist O(b^{1 + ⌊C*/ε⌋}), wobei b der Verzweigungsfaktor und ⌊x⌋ die untere Gaußklammer (Abrundung) der Zahl x ist.

Die ersten zehn Expansionen mit dem Wert g: (0, 0) g = 0; (0, 1) g = 1; (1, 0) g = 1; (0, 2) g = 2; (2, 0) g = 2; (0, 3) g = 3; (3, 0) g = 3; (1, 3) g = 4; (4, 0) g = 4; (2, 3) g = 5. Bis sie auf Schlamm trifft, expandiert die UCS genauso wie die BFS, denn jeder Schritt kostet 1 und g ist einfach die Tiefe. Der Schlamm „verschiebt“ einen Zustand dann um 5 statt um 1 — in den Schlamm schaut die UCS erst, wenn sie alles Günstigere erschöpft hat.

Der gefundene Weg: 25 Schritte auf trockenem Boden, C* = 25 · 1 = 25. Die kleinsten Aktionskosten sind ε = 1 und der Verzweigungsfaktor b = 4, die obere Abschätzung ist also b^{1 + ⌊C*/ε⌋} = 4²⁶ ≈ 4,5 · 10¹⁵ Zustände. In Wirklichkeit hat die UCS 49 Felder expandiert: Die Abschätzung rechnet mit einem unendlichen Baum, in dem sich nichts wiederholt, während das Labyrinth nur 83 begehbare Felder hat und geschlossene Zustände nicht noch einmal expandiert werden.

Sei P = (S, s₀, A, T, G, c) ein Suchproblem. Für einen Zustand n ∈ S bezeichne h*(n) ∈ ℝ_≥0 ∪ {∞} die kleinsten Kosten (genauer das Infimum der Kosten) der Pfade vom Zustand n zu irgendeinem Zielzustand (ein Pfad ist genauso definiert wie oben, er beginnt nur in n statt in s₀; führt von n kein Pfad nach G, ist h*(n) = ∞). Eine Heuristik ist eine Funktion

h : S → ℝ_≥0  mit  ∀n ∈ G : h(n) = 0.

Den Wert h(n) verstehen wir als Schätzung von h*(n). Eine Heuristik h ist

1. zulässig (admissible) genau dann, wenn ∀n ∈ S : h(n) ≤ h*(n);
2. konsistent (monoton) genau dann, wenn ∀n ∈ S ∀a ∈ A(n) : h(n) ≤ c(n, a) + h(T(n, a)).

Eine zulässige Heuristik überschätzt die tatsächlichen Restkosten also nie; eine konsistente Heuristik sinkt nach keinem Schritt um mehr, als dieser Schritt gekostet hat. Jede konsistente Heuristik ist zulässig (Satz unten).

Sei P = (S, s₀, A, T, G, c) ein Suchproblem und h : S → ℝ_≥0 eine konsistente Heuristik. Dann ist h zulässig, d. h. h(n) ≤ h*(n) für jedes n ∈ S.

Beweis. Sei n ∈ S. Ist h*(n) = ∞, gilt die Ungleichung trivialerweise. Andernfalls nehmen wir einen beliebigen Pfad von n zum Ziel: n = n₀, n₁, …, n_k ∈ G, wobei n_i = T(n_i−1, a_i) und c_i = c(n_i−1, a_i) für i = 1, …, k. Die Konsistenz wenden wir k-mal hintereinander an:

h(n₀) ≤ c₁ + h(n₁) ≤ c₁ + c₂ + h(n₂) ≤ … ≤ c₁ + … + c_k + h(n_k).

Im Ziel ist h(n_k) = 0, also ist h(n) höchstens gleich den Kosten dieses Pfads. Das gilt für jeden Pfad von n zum Ziel, also auch für den günstigsten, dessen Kosten h*(n) sind. Also h(n) ≤ h*(n). ∎

Umgekehrt gilt das nicht: Eine zulässige Heuristik muss nicht konsistent sein.

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c) und eine Heuristik h : S → ℝ_≥0. Ausgabe: eine Lösung oder die Meldung „es gibt keine Lösung“.

Die gierige Suche (greedy best-first search) ist das gemeinsame Gerüst von oben, in dem die Randmenge F eine Prioritätswarteschlange ist nach

f(n) = h(n):

1. F ← {s₀}, E ← ∅.
2. Ist F = ∅, halte an: Es gibt keine Lösung.
3. Entnimm aus F den Zustand n mit dem kleinsten h(n) — den Zustand, der der Schätzung nach dem Ziel am nächsten ist.
4. Ist n ∈ G, halte an und gib den Pfad von s₀ nach n zurück.
5. Expandiere n: Füge ihn zu E hinzu und füge jeden Nachfolger n′ ∈ N(n), der weder in E noch in F ist, in F ein. Fahre mit Schritt 2 fort.

Die bisherigen Kosten g(n) werden nicht berücksichtigt. Eigenschaften: Die gierige Suche ist nicht optimal; mit Kontrolle wiederholter Zustände (der Menge E) ist sie in einem endlichen Raum vollständig.

Expandierte Felder mit dem Wert h: (0, 0) 21 → (0, 1) 20 → (0, 2) 19 → (0, 3) 18 → (1, 3) 17 → (2, 3) 16 → (2, 2) 17 → (3, 2) 16 → (4, 2) 15 → (4, 3) 14.

Die gierige Suche geht direkt nach rechts und unten, solange h sinkt. Im siebten Schritt steigt h kurz an (von 16 auf 17), weil von (2, 3) weder nach rechts noch nach unten ein Weg weiterführt (Wände) und in der Randmenge kein Feld mit kleinerem h mehr liegt. Zwei Schritte später betritt sie den Schlamm auf (4, 2), weil h dort wieder sinkt. Die Kosten 5 für den Schritt in den Schlamm sieht sie überhaupt nicht: Die Priorität ist nur h, kein g.

Eingabe: ein Suchproblem P = (S, s₀, A, T, G, c) und eine Heuristik h : S → ℝ_≥0. Ausgabe: eine Lösung oder die Meldung „es gibt keine Lösung“.

A* ist die UCS (Schritte 1–5 ihrer Definition oben, einschließlich der Pflege von g), in der die Randmenge F eine Prioritätswarteschlange ist nach

f(n) = g(n) + h(n)

statt nach g(n): In Schritt 3 wird aus F der Zustand mit dem kleinsten f(n) entnommen. Der Wert f(n) ist eine Schätzung der Kosten des ganzen Pfads vom Start über n zum Ziel. Der Algorithmus hält an, sobald er einen Zielzustand aus F entnimmt (oder wenn F leer ist).

Satz. Sei h eine konsistente Heuristik und seien die Aktionskosten ≥ ε für ein ε > 0. Dann fallen die Werte von f entlang jedes Pfads nie, A* expandiert die Zustände in nicht fallender Reihenfolge von f, und der erste expandierte Zielzustand liegt auf einem optimalen Pfad mit den Kosten C*. Dabei expandiert A* jeden Zustand mit f(n) < C* und keinen mit f(n) > C*.

Für h ≡ 0 ist A* dasselbe wie UCS; ohne g wäre es die gierige Suche.

Sei h eine konsistente Heuristik, f = g + h, n ∈ S, a ∈ A(n), n′ = T(n, a), und der Pfad nach n′ führe über n, sodass g(n′) = g(n) + c(n, a). Dann gilt f(n′) ≥ f(n).

Beweis. f(n′) =g(n) + c(n, a) + h(n′) ≥ g(n) + h(n) = f(n),

wobei die Ungleichung genau die Konsistenz h(n) ≤ c(n, a) + h(n′) ist. ∎

Daraus folgt (hier nur skizziert), dass A* die Zustände in nicht fallender Reihenfolge von f expandiert: Würde es später einen Zustand mit kleinerem f expandieren, müsste zu ihm von der Randmenge aus ein Zustand mit noch kleinerem f führen, der früher an der Reihe gewesen wäre. Wenn also zum ersten Mal das Ziel expandiert wird (wo h = 0 und f = g), bleibt kein günstigerer Pfad mehr übrig.

Sei 𝒜 ein Algorithmus, der als Eingabe ein Suchproblem P bekommt und eine Lösung oder die Meldung „es gibt keine Lösung“ zurückgibt. Der Algorithmus 𝒜 ist

1. vollständig genau dann, wenn 𝒜 für jedes Problem P, das mindestens eine Lösung hat (Π ≠ ∅), nach endlich vielen Schritten anhält und eine Lösung π ∈ Π zurückgibt;
2. optimal genau dann, wenn er für jedes Problem P mit Π ≠ ∅ eine Lösung π mit den Kosten g(π) = C* zurückgibt.

Die Parameter, von denen Zeit und Speicher abhängen (für ein Problem P = (S, s₀, A, T, G, c)):

1. b = max_{s ∈ S} |A(s)| — der Verzweigungsfaktor;
2. d — die Tiefe der flachsten Lösung (die kleinste Länge eines Pfads von s₀ nach G);
3. m — die größte Tiefe des Raums (die größte Länge eines Pfads von s₀ ohne wiederholte Zustände, gegebenenfalls ∞);
4. C* — die optimalen Kosten und ε > 0 — eine untere Schranke der Aktionskosten.

Für Funktionen u, v ≥ 0 dieser Parameter schreiben wir u = O(v) genau dann, wenn es Konstanten K > 0 und x₀ gibt, sodass u(x) ≤ K · v(x) für alle x ≥ x₀. O(·) gibt also an, wie Zeit (die Zahl der erzeugten Zustände) oder Speicher (die Zahl der gleichzeitig gehaltenen Zustände) mit diesen Parametern höchstens wachsen, bis auf einen konstanten Faktor.

Sei S eine nichtleere Menge von Zuständen, f : S → ℝ eine Funktion (die Zielfunktion) und N : S → 2^S eine Abbildung, die jedem Zustand s ∈ S eine endliche nichtleere Menge N(s) ⊆ S ∖ {s} zuordnet (die Nachbarschaft des Zustands s, ihre Elemente sind die Nachbarn). Das Problem der lokalen Suche besteht darin, einen Zustand

s* ∈ argmax_{s ∈ S} f(s) = {s ∈ S : ∀s′ ∈ S : f(s) ≥ f(s′)}

zu finden, oder zumindest einen Zustand mit möglichst großem Wert von f. Ein Zustand s ∈ S ist

1. ein lokales Maximum genau dann, wenn ∀s′ ∈ N(s) : f(s) ≥ f(s′);
2. ein globales Maximum genau dann, wenn ∀s′ ∈ S : f(s) ≥ f(s′).

Jedes globale Maximum ist auch ein lokales, umgekehrt gilt das nicht.

Bergsteigeralgorithmus (hill climbing). Eingabe: S, f, N wie oben und ein Anfangszustand s ∈ S. Ausgabe: ein lokales Maximum.

1. Wähle s′ ∈ argmax_{t ∈ N(s)} f(t) (den besten Nachbarn).
2. Ist f(s′) ≤ f(s), halte an und gib s zurück — es ist ein lokales Maximum.
3. Sonst s ← s′ und fahre mit Schritt 1 fort.

Ein Zustand ist eine Zahl s ∈ [0, 1], die Nachbarschaft sind die zwei Punkte 0,02 links und rechts: N(s) = {s − 0,02, s + 0,02}. Die Landschaft hat zwei Gipfel (einen lokalen bei s = 0,25, den globalen bei 0,72), und der Bergsteiger startet bei s = 0,05.

In jeder Zeile ist der rechte Nachbar der höchste, also geht es nach rechts. In der letzten Zeile sind beide Nachbarn (0,582) niedriger als f(0,25) = 0,600, und der Algorithmus hält an — auf einem lokalen Maximum, obwohl das globale Maximum f(0,72) = 0,950 hat.

Eingabe: S, f, N wie bei der lokalen Suche, ein Anfangszustand s ∈ S, eine Anfangstemperatur T₀ > 0, ein Abkühlungskoeffizient q ∈ (0, 1) und eine Mindesttemperatur T_min ∈ (0, T₀). Ausgabe: ein Zustand s ∈ S.

1. T ← T₀.
2. Ist T ≤ T_min, halte an und gib s zurück.
3. Wähle zufällig (gleichverteilt) einen Nachbarn s′ ∈ N(s) und berechne Δ = f(s′) − f(s).
4. Ist Δ > 0, setze s ← s′. Ist Δ ≤ 0, setze s ← s′ mit der Wahrscheinlichkeit exp(Δ/T), sonst behalte s.
5. T ← q · T und fahre mit Schritt 2 fort.

Die „Temperatur“ T sinkt also allmählich gegen null und mit ihr die Bereitschaft, einen schlechteren Nachbarn anzunehmen. (Die Abkühlung T ← q · T ist die gebräuchlichste Wahl, es werden auch andere Abkühlungspläne verwendet.)