Backtracking

[abfdx]

@Thallius viel kann ich mit deinem kommentar jetzt nicht anfangen...

 

[mihe7]

ich bin Mathematiker vom feinsten!

Ach ja, ich vergaß, Du bist der, das P=NP-Problem gelöst hat.

Ich hoffe, man versteht, was ich meine

Sagen wir mal so: wenn man genügend Phantasie und vor allem Hoffnung ins Spiel bringt, versuchst Du einen Tiefendurchlauf durch einen Baum zu machen.

 

[abfdx]

@mihe7 ich hoffe, du hast meinen Mathematiker-Kommentar vielleicht nicht allzu ernst genommen. Ansonsten, naja, danke..?
Fantasie und Hoffnung sind doch auch immer was gutes. Ne, mal kurz Spaß beiseite: Wie würdest du das in der Skizze beschriebene Verfahren denn verändern / verbessern? Er muss ja schon alle Möglichkeiten, die in Frage kommen, durchgehen..

 

[mihe7]

Ich nehme hier gar nix ernst

Er muss ja schon alle Möglichkeiten, die in Frage kommen, durchgehen..

Richtig. Schau Dir mal das Bild an. Wie groß ist der Gesamtwert, wenn wir uns bei Knoten 3 befinden? Ach, so: die Zahlen kennzeichnen einfach nur verschiedene Münzen und stellen keine Werte dar.

 

[abfdx]

@mihe7 Die Zahlen im Bild haben nichts mit dem hinterlegten Wert zu tun. Und deins ist doch eigentlich exakt das gleiche wie meins, nur etwas anders dargestellt...?

 

[mihe7]

Nicht wirklich: du versuchst, einen Algorithmus darzustellen. Ich zeige lediglich eine Datenstruktur.

Wie groß ist der Gesamtwert, wenn wir uns bei Knoten 3 befinden?

Die Frage hast Du noch nicht beantwortet.

 

[mihe7]

Nochmal, etwas ausführlicher...

In dem angefügten Bild siehst Du (nochmal) einen vollständigen binären Suchbaum für drei Münzen (die Zahlen dienen nur zur Unterscheidung der Münzen).

Der Vorteil von Bäumen ist, dass sie eine nette Eigenschaft besitzen: In einem Baum ist jeder Knoten Wurzel eines Baums (Rekursion).

Den Gesamtbaum habe ich mal gestrichelt umrahmt. Dieser hat die Wurzel 1 und zwei Kindknoten, die ihrerseits Wurzeln von Teilbäumen sind, die im Bild rot eingezeichnet sind.

Wenn Du einen Baum nach dem besten Ergebnis "fragst", wird die Frage vom Wurzelknoten beantwortet, der die Frage (ggf. zum Teil) von seinen Kinder beantworten lässt. Der gestrichelte Baum beantwortet die Frage, in dem Knoten 1 die Frage auch(!) an die roten Bäume weitergibt. Dessen Wurzelknoten geben die Frage wieder an ihre Kinder weiter usw.

Einziges Problem ist jetzt, sich zu überlegen, wie die Frage nach dem besten Ergebnis
allgemein für einen Knoten in einem solchen Suchbaum beantwortet werden kann. Dann bist Du fast fertig. Bei der Definition des "besten Ergebnis" solltest Du nicht von Anfang an zu viel wollen. Wenn Du das hast, ist es fast schon ein Kinderspiel, das in Java auf Deine Liste anzuwenden.