FH-Hof

Template Pattern

Richard Göbel

FH-Hof

Motivation

Gegeben ist ein allgemeiner

Algorithmus

Anwendungen des Algorithmus

unterscheiden sich an einigen Stellen in

verschiedenen Details

An diesen Stellen sollen

unterschiedliche Methoden aufgerufen

werden

FH-Hof

Ansatz

Abstrakte Oberklasse mit

abstrakten Methodendeklarationen für die

variablen Teile des Algorithmus

einer vollständigen Definition mit dem

Algorithmus

Der Algorithmus ruft die abstrakten

Methoden der Oberklasse auf

In der Unterklasse werden die

abstrakten Methodendeklarationen

implementiert.

FH-Hof

Abstrakter Ansatz

AbstractClass

op1()op2()…

algorithmTemplate()

ConcreteClass

op1()op2()

…

…op1()…op2()…

FH-Hof

Beispiel: Lösung kombinatorischer Probleme

Gegeben

Ein Startzustand

Operationen erzeugen Folgezustände

Finde eine Sequenz von Operationen die einen Zielzustand erreichen

Best First Search

Schätze den Abstand von Zuständen zu dem Ziel

Wähle den Knoten mit dem geringsten Abstand zum Ziel und erzeuge alle Folgezustände

Überprüfe ob bereits ein Zielzustand erreicht wurde

FH-Hof

Schiebepuzzle

1 2 3

4

5

6

7 8

FH-Hof

Bewerte den Abstand zum Ziel

Zähle die falsch plazierten Steine

1 2 3

4

5

6

7 8

Falsch plazierte Steine: 3

FH-Hof

Suchbaum mit Bewertung

1 2 3

4

5

6

7 8

1

2

3

4

5

6

7 8

1 2 3

4 5 6

7 8

1 2 3

4

5

6

7 8

1 2 3

4

5

6

7 8

1 2 3

4 5 6

7 8

1 2 3

4 5 6

7 8

1 2 3

4

5

6

7 8

3

4 2 4 4

3 0 3

FH-Hof

Algorithmus

public abstract class BestFirstSearch {

private ArrayList<Node> processedNodes;

private ArrayList<Node> unprocessedNodes;

private ArrayList<Node> goalNodes;

public BestFirstSearch(Node startNode, ArrayList<Node> goalNodes) {

unprocessedNodes = new ArrayList<Node>();

processedNodes = new ArrayList<Node>();

unprocessedNodes.add(startNode);

this.goalNodes = goalNodes;

}

…

FH-Hof

Algorithmus

public abstract class BestFirstSearch {

…

abstract Node bestNode();

 

public Node search() {

while (true) {

Node best = bestNode();

if (goalNodes.contains(best)) return best;

unprocessedNodes.remove(best);

processedNodes.add(best);

unprocessedNodes.addAll(best.getChildNodes());

}

}

FH-Hof

Interface Node

interface Node {

double getEstDist ();

ArrayList<Node> getChildNodes();

Node getParentNode();

}

FH-Hof

Unterklasse für Best First Search

public class BFSGetBest extends BestFirstSearch {

public Node bestNode() {

Node best = unprocessedNodes.get(0);

for(int i=1; i<unprocessedNodes.size(); i++) {

if (best. getEstDist() < unprocessedNodes.get(i).getEstDist())

best = unprocessedNodes.get(i);

}

return best;

}

FH-Hof

Abgeleitete Duplikate finden

In einigen Aufgabenstellung können die

Nachfolgerknoten einen Vorgänger

enthalten

Ermögliche in diesen Fällen das

Aussortieren bereits vorhandener

Knoten

FH-Hof

Abstrakte Oberklasse - Duplikate

public Node search() {

while (true) {

Node best = bestNode();

if (goalNodes.contains(best)) return best;

unprocessedNodes.remove(best);

processedNodes.add(best);

ArrayList <Node> nodes = best.getChildNodes();

nodes remDups(nodes);

unprocessedNodes.addAll(nodes);

}

}

public ArrayList <Node> remDups(ArrayList<Node> nodes) {

return nodes;

}

FH-Hof

Unterklasse - Duplikate

public ArrayList<Node> remDups(ArrayList<Node> nodes) {

ArrayList<Node> result = new ArrayList<Node>();

for (Node n : nodes) {

if ( ! processedNodes.contains(n) && ! unprocessedNodes.contains(n))

result.add(n);

}

return nodes;

}

FH-Hof

Diskussion

Eigene Methoden in einen Algorithmus

einbringen

Für abstrakte Methoden müssen eigene

Methoden definiert werden

Vorhandene Methoden ("Hook") können durch

eigene Methode ersetzt werden

Welches Pattern wurde hier noch

verwendet?

Vervollständigen Sie das Suchverfahren

An welchen Stellen verwenden Sie

Templates für die Java Library?