Das Springerproblem Gliederung • 1. Definition und Erläuterung des Springerproblems • 2. Geschichte und Ursprung (Hamiltonkreisproblem) • 3. Problem des Springerproblems in Bezug auf Lösbarkeit • 4. Lösungsverfahren für das Springerproblem • 4.1 Backtracking Verfahren • 4.2 Warnsdorfregel • 4.3 Das L-Verfahren. • 5. Quellen 1. Einführung • im Regelfall einen Vertreter für ein eher kombinatorisches Problem • Verallgemeinerungen besteht darin, Bretter der Größe n x m oder n-dimensionale Bretter zu verwenden • ein bekanntes Problem zur Darstellung des sogenannten Backtracking-Verfahrens • einem rekursiven Lösungsverfahren für verschiedene Suchsysteme 2.Geschichte und Ursprung • Mathematische Grundlage hierfür findet sich in einem bekannten Problem der Graphentheorie wieder • Spezialfall des sogenannten Hamiltonpfadproblems • für das Springerproblem wurden mehrere verschiede Varianten oder Techniken entwickelt • es existiert ein bekannter und effizienter Lösungsalgorythmus 3. Problem des Springerproblems in Bezug auf Lösbarkeit • ganze Reihe von Spezialfällen die Als Lösung in Frage kommen um einen bestimmten Weg zu berechnen • Möglichkeit der Wege erhöt sich exponentiel zum Wachstum des Brettes welches betrachtet werden soll • noch nicht gelöst, wie viele Wege überhaupt bei einem beliebig großen Brett existieren 4. Lösungsverfahren des Springerproblems 4.1 Das Backtracking-Verfahren • erster Ansatz für einen Algorithmus besteht darin, ein einfaches Backtracking-Verfahren (auf deutsch Rückzugverfahren) anzuwenden • mit dieser Methode findet man zu 100% eine Lösung, sofern eine existiert, es ist jedoch sehr langsam • reine Zufallsmethode um die Lösung eines Problems zu ergründen Feldgröße Laufzeit (in Sek) 5x5 21 6x6 609 7x7 8x8 38.954 Tage 9x9 10x10 Monate Jahre 4.2 Die Warnsdorffregel • Nach der Wansdorffregel zieht der Springer immer auf das Feld, von dem aus er für seinen nächsten Zug am wenigsten freie Felder zur Verfügung hat • ist kein System welches eine Lösung garantiert • Proportional zur Anzahl der Felder des Schachbretts steigt auch die Häufigkeit autretender Fehler bzw Sackgassen 4.3 Das L-Verfahren • Idee : Von einem beliebigen großen Schachbrett lässt sich ein Streifen der Breite 5 von Feldern abschneiden.Diesem Streifen kann man in 5x5 große Bretter zerlegen • 5x5-Bretter lassen sich ohne weiteres so lösen • Übrig bleiben dann nur L-förmige Bretter und ein Brett der Größe 6x6 bis 9x9 • Beweis, dass es für beliebige n x n-Bretter eine Lösung gibt • Beispiel für dieses Prinzip Vielen Dank für Ihre Aufmerksamkeit Quellen • • • • http://www.axel-conrad.de/springer/springer.html http://de.wikipedia.org/wiki/Springerproblem http://de.wikipedia.org/wiki/Heuristik http://www.hackerboard.de/thread.php?threadid=1 8267&sid= • http://www.stefanbaur.de/cs.algo.knightproblem.html
© Copyright 2024 ExpyDoc
