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.