Problem der Wasserkrüge
Beim Problem der Wasserkrüge geht es darum, durch Umschütten von Wasser zwischen verschieden großen Krügen vorgegebene Füllmengen zu erreichen. Die Krüge haben keine Messstriche. In jedem Schritt muss Wasser umgefüllt werden, bis der Krug in den man hineinschüttet voll oder der Krug aus dem man ausschüttet leer ist.
Derartige Aufgabenstellungen lassen sich mit der Breitensuche (siehe Tiefen- und Breitensuche) lösen. Die Realisierung basiert auf einer Subklasse von breadth-first-search.
(defclass water-jug-problem (breadth-first-search))
Der Konstruktor erwartet drei gleichlange Listen als Argumente: die Größen der Krüge, die Füllstände zu Beginn und die gesuchte Aufteilung des Wassers. Die Füllstände zu Beginn und zum Schluss können natürlich nicht die Größen der Krüge übersteigen. Die Summe der Füllstände bleibt erhalten.
(defmethod initialize ((this water-jug-problem) capacities initial-levels goal-levels)
(and
(= (length capacities) (length initial-levels))
(= (length capacities) (length goal-levels))
(every? not-negative? (zip-with - capacities initial-levels))
(every? not-negative? (zip-with - capacities goal-levels))
(= (apply + initial-levels) (apply + goal-levels)))
(progn
(.= this capacities capacities)
(.= this initial-levels initial-levels)
(.= this goal-levels goal-levels)
(freeze this)))
(defproc not-negative? (a) (not (< a 0)))
Die Methode get-start-node wird so überschrieben, dass sie die Füllstände zu Beginn liefert. Diese Angabe wurde dem Konstruktor als Argument übergeben und in einer Instanzvariable gespeichert.
(defmethod get-start-node ((this water-jug-problem)) t
(. this initial-levels))
Die Methode is-goal-node? überprüft, ob die gewünschten Zielfüllmengen erreicht sind. Auch diese wurden dem Konstruktor übergeben und in einer Instanzvariable gespeichert.
(defmethod is-goal-node? ((this water-jug-problem) node) t
(with-slots-read-only (goal-levels) this
(= node goal-levels)))
Die Methode get-next-nodes liefert ausgehend von aktuellen Füllständen alle möglichen Kombinationen von Füllständen, die sich durch Umschütten von einem Krug in einen anderen ergeben können.
(defmethod get-next-nodes ((this water-jug-problem) levels) t
(let
((indices (range 0 (length levels))))
(remove nil
(map-with
(lambda (pair) (decant this (first pair) (second pair) levels))
(cartesian-product indices indices)))))
(defmethod decant ((this water-jug-problem) source destination levels)
t
(with-slots-read-only (capacities) this
(let
((amount
(min
(nth levels source)
(- (nth capacities destination) (nth levels destination)))))
(if
(or (= source destination) (zero? amount))
nil
(map-with
(lambda (actual)
(get-level-after-decanting
source
destination
actual
(nth levels actual)
amount))
(range 0 (length levels)))))))
(defproc get-level-after-decanting (source destination actual level amount)
(cond
((= source actual)
(- level amount))
((= destination actual)
(+ level amount))
(t
level)))
(defproc min (a b) (if (< a b) a b))
Mit der Methode find-path der Breitensuche kann man dann konkrete Probleme lösen:
1. Zwei Freunde haben einen Krug mit 8 Vierteln Wasser und möchten ihn gleichmäßig aufteilen. Sie haben außerdem zwei leere Krüge, einer für fünf Viertel und der andere für drei Viertel. Wie messen sie exakt vier Viertel Wasser ab?
Die Aufgabe wird wie folgt als Ausdruck dargestellt:
(find-path
(new water-jug-problem
(quote (8 5 3)) #| Größen der Krüge |#
(quote (8 0 0)) #| Füllstände zu Beginn |#
(quote (4 4 0)))) #| Füllstände zum Schluss |#
Die gefundene Lösung ist
((4 4 0) (1 4 3) (1 5 2)
(6 0 2) (6 2 0) (3 2 3)
(3 5 0) (8 0 0)),
d.h. vom großen Krug wird in den Mittleren umgeschüttet, dann vom Mittleren in den Kleinen, vom Kleinen in den Großen, vom Mittleren in den Kleinen, vom Großen in den Mittleren, vom Mittleren in den Kleinen und schließlich vom Kleinen in den Großen.
2. Drei Männer stehlen einen Behälter mit 24 Unzen Balsam. Während der Flucht kaufen sie drei Behältnisse. Als sie an einem sicheren Ort eintreffen, wollen sie die Beute gleichmäßig aufteilen - aber sie stellen fest, dass die gekauften Behälter 5, 11 und 13 Unzen aufnehmen können. Wie teilen sie die Beute gleichmäßig auf?
Das führt zu
(find-path
(new water-jug-problem
(quote (24 5 11 13))
(quote (24 0 0 0))
(quote (8 0 8 8))))
und der Lösung
((8 0 8 8) (8 5 3 8) (8 0 3 13)
(8 0 11 5) (8 5 11 0) (19 5 0 0)
(24 0 0 0)).
3. Ein Weinhändler hat einen Krug mit 9 Litern Wein. Sein Kunde möchte 3 Liter Wein kaufen. Der Händler hat aber nur zwei andere Krüge von 7 und 4 Litern. Wie misst er das gewünschte Volumen ab?
Hier ergibt sich
(find-path
(new water-jug-problem
(quote (9 7 4))
(quote (9 0 0))
(quote (6 0 3))))
mit dem Ergebnis
((6 0 3) (6 3 0) (2 3 4) (2 7 0) (9 0 0)).
Die Realisierung der Breitensuche und die Beispiele befinden sich in der unten verlinkten Datei water-jugs.sheet.xml. Die Datei kann mit dem Programm Calc angezeigt und ausgeführt werden.
Link
http://www.cut-the-knot.org/ctk/Water.shtml
Derartige Aufgabenstellungen lassen sich mit der Breitensuche (siehe Tiefen- und Breitensuche) lösen. Die Realisierung basiert auf einer Subklasse von breadth-first-search.
(defclass water-jug-problem (breadth-first-search))
Der Konstruktor erwartet drei gleichlange Listen als Argumente: die Größen der Krüge, die Füllstände zu Beginn und die gesuchte Aufteilung des Wassers. Die Füllstände zu Beginn und zum Schluss können natürlich nicht die Größen der Krüge übersteigen. Die Summe der Füllstände bleibt erhalten.
(defmethod initialize ((this water-jug-problem) capacities initial-levels goal-levels)
(and
(= (length capacities) (length initial-levels))
(= (length capacities) (length goal-levels))
(every? not-negative? (zip-with - capacities initial-levels))
(every? not-negative? (zip-with - capacities goal-levels))
(= (apply + initial-levels) (apply + goal-levels)))
(progn
(.= this capacities capacities)
(.= this initial-levels initial-levels)
(.= this goal-levels goal-levels)
(freeze this)))
(defproc not-negative? (a) (not (< a 0)))
Die Methode get-start-node wird so überschrieben, dass sie die Füllstände zu Beginn liefert. Diese Angabe wurde dem Konstruktor als Argument übergeben und in einer Instanzvariable gespeichert.
(defmethod get-start-node ((this water-jug-problem)) t
(. this initial-levels))
Die Methode is-goal-node? überprüft, ob die gewünschten Zielfüllmengen erreicht sind. Auch diese wurden dem Konstruktor übergeben und in einer Instanzvariable gespeichert.
(defmethod is-goal-node? ((this water-jug-problem) node) t
(with-slots-read-only (goal-levels) this
(= node goal-levels)))
Die Methode get-next-nodes liefert ausgehend von aktuellen Füllständen alle möglichen Kombinationen von Füllständen, die sich durch Umschütten von einem Krug in einen anderen ergeben können.
(defmethod get-next-nodes ((this water-jug-problem) levels) t
(let
((indices (range 0 (length levels))))
(remove nil
(map-with
(lambda (pair) (decant this (first pair) (second pair) levels))
(cartesian-product indices indices)))))
(defmethod decant ((this water-jug-problem) source destination levels)
t
(with-slots-read-only (capacities) this
(let
((amount
(min
(nth levels source)
(- (nth capacities destination) (nth levels destination)))))
(if
(or (= source destination) (zero? amount))
nil
(map-with
(lambda (actual)
(get-level-after-decanting
source
destination
actual
(nth levels actual)
amount))
(range 0 (length levels)))))))
(defproc get-level-after-decanting (source destination actual level amount)
(cond
((= source actual)
(- level amount))
((= destination actual)
(+ level amount))
(t
level)))
(defproc min (a b) (if (< a b) a b))
Mit der Methode find-path der Breitensuche kann man dann konkrete Probleme lösen:
1. Zwei Freunde haben einen Krug mit 8 Vierteln Wasser und möchten ihn gleichmäßig aufteilen. Sie haben außerdem zwei leere Krüge, einer für fünf Viertel und der andere für drei Viertel. Wie messen sie exakt vier Viertel Wasser ab?
Die Aufgabe wird wie folgt als Ausdruck dargestellt:
(find-path
(new water-jug-problem
(quote (8 5 3)) #| Größen der Krüge |#
(quote (8 0 0)) #| Füllstände zu Beginn |#
(quote (4 4 0)))) #| Füllstände zum Schluss |#
Die gefundene Lösung ist
((4 4 0) (1 4 3) (1 5 2)
(6 0 2) (6 2 0) (3 2 3)
(3 5 0) (8 0 0)),
d.h. vom großen Krug wird in den Mittleren umgeschüttet, dann vom Mittleren in den Kleinen, vom Kleinen in den Großen, vom Mittleren in den Kleinen, vom Großen in den Mittleren, vom Mittleren in den Kleinen und schließlich vom Kleinen in den Großen.
2. Drei Männer stehlen einen Behälter mit 24 Unzen Balsam. Während der Flucht kaufen sie drei Behältnisse. Als sie an einem sicheren Ort eintreffen, wollen sie die Beute gleichmäßig aufteilen - aber sie stellen fest, dass die gekauften Behälter 5, 11 und 13 Unzen aufnehmen können. Wie teilen sie die Beute gleichmäßig auf?
Das führt zu
(find-path
(new water-jug-problem
(quote (24 5 11 13))
(quote (24 0 0 0))
(quote (8 0 8 8))))
und der Lösung
((8 0 8 8) (8 5 3 8) (8 0 3 13)
(8 0 11 5) (8 5 11 0) (19 5 0 0)
(24 0 0 0)).
3. Ein Weinhändler hat einen Krug mit 9 Litern Wein. Sein Kunde möchte 3 Liter Wein kaufen. Der Händler hat aber nur zwei andere Krüge von 7 und 4 Litern. Wie misst er das gewünschte Volumen ab?
Hier ergibt sich
(find-path
(new water-jug-problem
(quote (9 7 4))
(quote (9 0 0))
(quote (6 0 3))))
mit dem Ergebnis
((6 0 3) (6 3 0) (2 3 4) (2 7 0) (9 0 0)).
Die Realisierung der Breitensuche und die Beispiele befinden sich in der unten verlinkten Datei water-jugs.sheet.xml. Die Datei kann mit dem Programm Calc angezeigt und ausgeführt werden.
Link
http://www.cut-the-knot.org/ctk/Water.shtml