Advanced Potion Making
Wir wollen möglichst günstig einen Zaubertrank (potion) brauen. Die Zutaten (ingredients) befinden sich in einer Kammer (pantry). Jedes mal wenn wir eine Zutat aus der Kammer entnehmen bezahlen wir den Preis dieser Zutat. In einem Zauberbuch finden wir Schritte, um aus gegebenen Zutaten eine neue Zutat zu erzeugen. Diese neue Zutat befindet sich dann nicht mehr in der Kammer sondern auf dem Tisch. Wir können sie zur Anwendung weiterer Schritte verwenden (nun ohne Kosten zu bezahlen) und hieraus wieder neue Zutaten auf dem Tisch erzeugen. Das Ende ist erreicht wenn die Zielzutat (der Zaubertrank) erzeugt wurde. Der Zaubertrank selbst ist übrigens zu Beginn nicht in der Kammer vorhanden.
Beispiel
Zauberer Severus möchte den Zaubertrank Liquid Luck brauen. Hierzu benötigt er einmal Pulver zweimal die Tinktur (Regel 4 im Zauberbuch). Weil die Kammer nur eine Tinktur enthält, stellt er sich aus Thymian und Öl eine zweite Tinktur her (3). Dies wäre sogar günstiger (Kosten 10+2=12) als eine fertige Tinktur (Kosten 25) zu verwenden, aber er besitzt kein zweites Öl um eine zweite Tinktur selbst herzustellen. Da er keinen Lorbeer besitzt, stellt er aus zwei Samen einen Lorbeer her (Schritt 1). Hieraus macht er Pulver (2) und verarbeitet Pulver und Tinkturen zu Liquid Luck (4).
Offensichtlich muss sich unser Verfahren immer entscheiden ob wir eine Zutat X direkt verwendet oder X (aus evtl. günstigeren) Zutaten herstellen. Hierbei muss beachtet werden wieviel von welcher Zutat in der Kammer vorhanden ist. Außerdem kann es mehrere mögliche Schritte geben um die gleiche Zutat herzustellen, und die gleiche Zutat ist evtl. in verschiedenen Schritten verwendbar. Sie können davon ausgehen dass Schritte zyklenfrei sind (Es wird aus A nicht B erzeugt und aus B wieder A).
Programmgerüst
In Potions.java finden Sie Basisklassen für Zutaten (Ingridient) mit Kosten und Namen, sowie für Schritte (Step) mit Eingabe- und Ausgabezutaten.
- Die Kammer ist ein Array von Zutaten:
Ingridient[] pastry.
- Das Zauberbuch ist eine Array von Schritten:
Step[] book.
Studieren Sie die Methode brew() in PotionsTest. Diese erhält ein Rezept (d.h. eine Sequenz von Schritten), stellt mit diesem Rezept einen Trank her, und gibt die entstandenen Kosten zurück. Ist das Rezept nicht durchführbar (weil Zutaten fehlen) wird -1 zurückgegeben. Vollziehen Sie den Code in brew() nach, ändern Sie aber nichts.
Greedy-Verfahren
Implementieren Sie ein Greedy-Verfahren, das ein Rezept (d.h. ein Step[]-Array) zur Erzeugung eines Tranks (goal) generiert.
- Denken Sie rückwärts: Speichern Sie in einem Array
Ingridient[] goals welche Zutaten noch fehlen. Initial befindet sich in diesem Array nur der herzustellende Zaubertrank.
- In jeder Iteration versuchen Sie die vorderste Zutat X von
goals zu beschaffen: Suchen Sie X zuerst in der Kammer. Falls X nicht vorhanden ist, suchen Sie nach dem erstmöglichen Schritt im Zauberbuch um X durch andere Zutaten zu ersetzen, und fügen diese Zutaten goals am Anfang des goals-Arrays hinzu (ohne weitere Prüfung ob die Zutaten vorhanden oder erzeugbar sind).
- Fahren Sie fort bis goals leer ist oder eine Zutat endgültig fehlt.
- Beachten Sie, dass das Ergebnis-Rezept die Schritte in der richtigen Reihenfolge der Durchführung enthalten muss.
- Wenn Ihr Verfahren keine Lösung findet, soll ein leeres Array zurückgegeben werden.
- Sie finden in PotionsTest.java einige rudimentäre Testfälle. Falls Sie sichergehen wollen dass Ihr Code das richtige tut, konstruieren Sie bei Bedarf weitere Testfälle.
Backtracking-Verfahren
- Implementieren Sie ein Backtracking-Verfahren, das die optimale Lösung findet indem in jedem Schritt alle Möglichkeiten geprüft werden.
- Ähnlich wie Greedy soll das Verfahren ein Array
goals unterhalten und in jedem Schritt versuchen die Zutat goals[0] zu besorgen. Hier werden sämtliche Alternativen getestet, nämlich das Nachschauen im Schrank und die Rückwärtsanwendung sämtlicher möglicher Schritte.
- Unterhalten Sie globale Variablen für die bisher beste gefundene Lösung und ihre Kosten. Updaten Sie diese Variablen wenn Sie ein besseres Ergebnis finden.
- Ein wichtiger Tipp: Sie werden bei rekursive Aufrufen im Backtracking häufig den aktuellen Zustand (z.B. den Inhalt der Kammer) ändern. Da hierbei nur Referenzen auf dasselbe Array übergeben werden, sollten Sie jedes Mal bevor Sie ein Array modifizieren eine Kopie erzeugen (z.B. mit clone()).
- Optimieren Sie die Laufzeit Ihres Verfahrens, indem Sie abbrechen sobald die Kosten der bisher besten Lösung überschritten werden.
- Auch hier bietet es sich an bei Bedarf weitere Testfälle zu konstruieren.
package de.hsrm.ads;
public class Potions {
public static class Ingredient {
String name;
int cost;
public Ingredient(String name, int cost) {
this.name = name;
this.cost = cost;
}
// use this method to compare two ingredients.
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || o.getClass() != this.getClass() ) {
return false;
}
Ingredient i = (Ingredient) o;
return name == i.name && cost == i.cost;
}
}
public static class Step {
Ingredient[] input; // the step's input ingredients (1:many)
Ingredient output; // the step's output ingredient (exactly 1)
public Step(Ingredient output, Ingredient[] input) {
this.output = output;
this.input = input;
}
// prints a step
public void print() {
System.out.print(" <STEP> ");
for (Ingredient i : input) {
System.out.print(i.name + ", ");
}
System.out.println(" -> " + output.name + " </STEP>");
}
// prints a sequence of steps (e.g., a recipe).
public static void print(Step[] steps) {
System.out.println("<STEPS>");
for (Step s : steps) {
s.print();
}
System.out.println("</STEPS>");
}
}
// checks if an ingredient is available on the table
// or in the pantry.
public static boolean available(Ingredient ing,
Ingredient[] place) {
for (Ingredient ing2 : place) {
if (ing.equals(ing2))
return true;
}
return false;
}
// removes an ingredient from the table or pantry.
public static Ingredient[] remove(Ingredient ing,
Ingredient[] place) {
Ingredient[] result = new Ingredient[place.length - 1];
boolean done = false;
int c = 0;
for (int i=0; i<place.length; ++i) {
if (!done && ing.equals(place[i])) {
done = true;
} else {
result[c++] = place[i];
}
}
assert(done); // assertion if ing not in place.
return result;
}
// adds a new ingredient 'ing' to the table or pantry.
public static Ingredient[] add(Ingredient ing,
Ingredient[] place) {
Ingredient[] result = new Ingredient[place.length + 1];
result[0] = ing;
for (int i=0; i<place.length; ++i) {
result[i+1] = place[i];
}
return result;
}
/*
* Create a potion recipe using a greedy strategy.
*
* @param goal : The potion to produce.
* @param book : The book containing the possible brewing steps.
* @param pantry: The reserve of available ingredients.
*/
public static Step[] greedy(Ingredient goal,
Step[] book,
Ingredient[] pantry) {
// FIXME : implement
}
/*
* Create a potion recipe using a backtracking strategy.
*
* @param goal : The potion to produce.
* @param book : The book containing the possible brewing steps.
* @param pantry: The reserve of available ingredients.
*/
public static Step[] backtracking(Ingredient goal,
Step[] rulebook,
Ingredient[] pantry) {
// FIXME: internal recursive methods are allowed!
}
}
Subato
