Bin am verzweifeln mit Algorithmen...
Hi Leute!
Ich will mein Programmierwissen mal ausweiten und mich gezielt mit der Thematik der Algorithmen beschäftigen.
Hohen Stellenwert lege ich hier auf Rekursion und Backtracking.
Im Internet habe ich bereits einige Tutorials gefunden, die mich aber mehr verwirrten als mir etwas beibrachten.
Als Beispiel für die Rekursion nahm ich "Türme von Hanoi" das Prinzip selbst hab ich verstanden nur die Umsetzung danach nicht so ganz.
Für Sharp fand ihc folgenden Code
void hanoi(int hoehe, char von, char nach, char ueber)
{
if (hoehe > 1)
{
hanoi(hoehe - 1, von, ueber, nach);
}
Console.WriteLine("Scheibe '" + von + "' nach '" + nach);
if (hoehe > 1)
{
hanoi(hoehe - 1, ueber, nach, von);
}
}
Dieser funktioniert ja wunderbar, nur verstehe ich das Prinzip nicht und kann nciht richtig nachvollziehen wie hier gearbeitet wird... Weiß nicht woran es liegt...
Zum Thema Backtracking hab ich mich mit dem "Weg aus dem Labyrinth" beschäftigt. Nur da wirklich noch gar nichts verstanden...
Wie kann ich denn da vorgehen um das zu erlernen? Ich programmiere seit 8 Jahren in sämtlichen Programmiersprachen, bin nur leider soweit nie eingestiegen und zurzeit interessiert es mich unheimlich aber ich komme irgendwie nicht ran.
HOffe es hat jemand tipps oder jemand kann mir da weiterhelfen... Verzweifel langsam daran, vorallem weil die ständigen Niederschläge sehr deprimieren 🙁
Vielen Dank schonmal!
Liebe Grüße
Ja, manchmal kann so was ganz schön schwer und nervenaufreibend sein.
Ich habe neulich in dem Artikel "Zeichnen optimieren" einen Teil eines Algorithmus gepostet der aufzeigen soll, ob ein rechteckiges Element ein anderes verdeckt. Dabei haben alle eine gleich große rechteckige Grundfläche.
Was tun?
Ich bin hingegangen und habe mir das aufgeschrieben.
Es gibt die Elemente 0-4 (also insgesamt 5).
jetzt wird überprüft:
0 -> 0,1,2,3,4
1 -> 0,1,2,3,4
2 -> 0,1,2,3,4
3 -> 0,1,2,3,4
4 -> 0,1,2,3,4
Hier wird jedes Element mit jedem überprüft. Das ist Quatsch.
Also schließe ich jedes Element aus, das gleich mit sich selbst ist. Ich brauch ja nicht überprüfen ob 1 1 verdeckt. Ist ja eh das selbe Element und erhalte:
0 -> 1,2,3,4
1 -> 0, 2,3,4
2 -> 0,1, ,3,4
3 -> 0,1,2, ,4
4 -> 0,1,2,3
sieht doch schon besser aus oder? Oh! was ist das?in der ersten Zeile wird 0 mit 1 verglichen und in der zweiten 1 mit 0? das muss ja nicht doppelt sein.
0 -> 1,2,3,4
1 -> 2,3,4
2 -> 3,4
3 -> 4
4 ->
und schon sind wir fertig.
Mach doch mal das gleiche für den Turm von Hanoi. Manche Dinge kapiert man nicht einfach so.
Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.
hm.... sei mir nicht böse, aber irgendwie kapier ich jetzt den ansatz zum vergleich nicht^^ tut mir leid
ok, geh mal hin und mach das mit den scheiben von hand durch oder auf einem Blatt papier. Vielleicht kommst du dann dahinter.
von, über, nach sind jeweils die "Spiesse" auf die die Scheiben gelegt werden können, oder etwa nicht?
jetzt der erste Teil:
if (hoehe > 1)
{
hanoi(hoehe - 1, von, ueber, nach);
}
haben wir mehr als eine Scheibe?
dann Scheibe von nach...
Haben wir mehr als eine Scheibe?
if (hoehe > 1)
{
hanoi(hoehe - 1, ueber, nach, von);
}
Spiels mal auf dem Papier durch.
Gib dir notfalls hoehe, von, nach, über aus.
Debug.WriteLine in System.Diagnostics oder per MessageBox.
Vielleicht verstehst du ja dann das Prinzip!?
Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.
Das was dr4g0n76 beschreibt ist auch eher die Idee hinter Backtracking.
Backtracking und Rekursion liegen ja relativ dicht beieinander. Mit Backtracking braucht man erst garnicht anfangen, wenn man Rekursion noch nicht so richtig versteht.
Paradebeispiele für Rekursionen findest du, wenn du dich mal mit binären Bäumen befasst. Speziell die verschiedenen Möglichkeiten durch einen Baum zu gehen.
Hier mal ein Beispiel eines sortierten Baumes.
D
/ \
B F
/ \ / \
A C E G
Die Frage: Wie bekommt man eine Sortierte Liste der Knoten aus dem Baum, wenn man als Start nur den Zeiger auf D hat?
Wie würdest du vorgehen? Du weißt, dass links alle Elemente kleiner sind als rechts. Also wenn du erstmal alle Elemente links richtig sortiert aufzählst, dann das aktuelle Element nennst, und dann alle Elemente rechts richtig sortiert aufzählst, ist das Problem erledigt. Und weil du weißt, dass diese Eigenschaft für alle Knoten gilt, kannst du das Prinzip überall anwenden. Also schreibst du erstmal diese Idee auf:
void Expandieren()
{
linkerSohn.Expandieren();
WertSchreiben();
rechterSohn.Expandieren();
}
Beispiele in dieser Art gibt es in der Graphentheorie viele. Ich denke das ist leicht genug um einen guten Einstieg in die Denkweise Rekursion zu finden.
Das Beispiel hab ich auch gebracht, weil es der Rekursion von "hanoi" ziemlich ähnlich ist. Das Muster ist offensichtlich das gleiche, man muss nur erkennen warum.
Das Grundprinzip ist ja bei beiden: verschieb das Problem erstmal zu einem anderen (dem linken Sohn), wenn der das gelöst hat, weiß ich wies weitergeht.
In dem Baumbeispiel ist es relativ einfach. Wenn alle aufgezählt wurden, die kleiner als mein aktueller Wert sind, dann brauch ich bloß noch den aktuellen Wert schreiben und dann an den nächstbesten übergeben.
Bei der hanoi Rekursion sieht das dann so aus:
Also ich starte mit n Schiben auf dem ersten Stapel (a) und will alle auf einen anderen (c) über einen Hilfsstapel (b) kriegen, und darf nur kleinere Scheiben auf größere Scheiben legen.
Wenn ich alle außer die größte Scheibe von a nach b Schieben würde, könnte ich die größte (letzte) Scheibe einfach auf c legen. Dann müsste ich bloß noch den ganzen Stapel von b wieder nach c bewegen, mit dem Hilfsstapel a. Dass bei c schon die größte Scheibe liegt stört dabei ja nicht. Und so ist der Algorithmus zu verstehen:
void hanoi(int hoehe, char von, char nach, char ueber)
{
// Ok ich hab vieleicht keine Ahnung wie ich von "von" nach "nach" komme
// aber wenn ich alle außer die letzte nach "über" kriegen würde...
// also lass ich einfach nen anderen Deppen das erledigen
hanoi(hoehe - 1, von, ueber, nach);
// Jetzt weiß ich wies weitergeht. Muss nur noch die letzte Scheibe rüberlegen
Console.WriteLine("Scheibe '" + von + "' nach '" + nach);
// so, jetzt hab ich meine unterste Scheibe auf "nach" *schweißabwisch*
// und meine restlichen Scheiben sind bei über
// da muss ja nur noch irgendwer die restlichen Scheibe von "über"
// nach "nach" bringen und ich bin fertig
hanoi(hoehe - 1, ueber, nach, von);
}
}
So, was fehlt noch? Richtig, eine Abbruchbedingung. Das ganze würde sich endlos im Kreis drehen, und da sind wir bei dem wichtigsten, das eine Rekursion erst ermöglicht: Der Trivialfall. Meistens erkennt man den als allererstes. Es ist die Menge an Problemen, für die man sofort eine Lösung hinschreiben könnte. Bei Hanoi ist das ganz einfach dann, wenn der Turm nur aus einer einzigen Scheibe besteht. Dann ist der Fall trivial, ich leg halt die Scheibe hin und muss sonst nichts mehr tun. Ich muss nur noch den Code so auslegen, dass der Trivialfall erkannt und behandelt wird. Also frage ich hab, ob "höhe" überhaupt größer als 1 ist. Und wenn nicht, ist der Trivialfall eingetreten.
e.f.q.
Aus Falschem folgt Beliebiges
Dies ist zwar auf c++ bezogen, zeigt aber sehr schön Rekursion
http://www.bw.fh-deggendorf.de/kurse/cpp/skripten/skript14.pdf
Gruß Jörg