Entwickler-Ecke :: Thema anzeigen

klabri - Fr 28.11.08 19:51
Titel: Backtracking

Hallo

Ich beschäftige mich gerade mit dem '8-Damen-Problem' und Backtracking. Lässt sich das (ich bin kein Mathematiker...)irgendwie mathematisch beweisen,dass durch das Backtracking alle Lösungen gefunden werden? Lässt sich diese Lösungssuche irgendwie graphisch darstellen, also mit Papier und Bleistift..?

Hab ich das so richtig kapiert:

es sind z.Bsp. fünf Damen richtig positioniert,
für die sechste Dame gibt es keine Lösung
das Programm macht einen Schritt zurück und sucht für die 5te Dame eine neue Position
macht dann weiter mit der 6ten Dame
wenn es immer noch keine Lösung gibt
und auch keine neue Position für die 5.Dame
dann wird die ursprüngliche Position der 5.Dame gelöscht,
für die 4.Dame eine neue Position gesucht
die 5te Dame neu gesetzt....usw.

Ist das vom Prinzip her richtig ?

Moderiert von Narses: Beitragsformatierung überarbeitet

BenBE - Fr 28.11.08 20:16

Mathematischer Beweis:
Ja, lässt es sich. Kurzfassung:
- Wenn man eine allgemeine Teillösung L kennt, so erfüllen alle daraus hergeleiteten Lösungen L* mindestens die zur Findung der Teillösung L benötigten Anforderungen.
- Ist eine spezielle Teillösung L* bekannt, so lässt sich aus dieser durch Weglassung eines Attributes eine allgemeinere Teillösung L herleiten.
- Die Problemlösung L! ist die speziellste Teillösung, die leere Lösung, ist die allgemeinste Teillösung (die nämlich immer keine Bedingungen erfüllt)

Backtracking entspricht einer Traversierung des durch die oben aufgespannten Eigenschaften aufgespannten "Lösungsbaumes".

Und ja: Deine Beschreibung ist korrekt. Auch wenn man da nicht grad in der Mitte anfängt, sondern meist mit der leeren Teillösung ;-)

BenBE - So 30.11.08 16:56

NEhmen wir mal das Beispiel alle Permutationen der Ziffern 1,2,3 ohne Wiederholung:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

()
- (1)
  - (1,1) --> cut, da keine Lösung
  - (1,2)
    - (1,2,1) --> Keine Lösung
    - (1,2,2) --> Keine Lösung
    - (1,2,3) --> Lösung 1 gefunden
  - (1,3)
    - (1,3,1) --> Keine Lösung
    - (1,3,2) --> Lösung 2 gefunden
    - (1,3,3) --> Keine Lösung
- (2)
  - (2,1)
    - (2,1,1) --> Keine Lösung
    - (2,1,2) --> Keine Lösung
    - (2,1,3) --> Lösung 3 gefunden
  - (2,2) --> cut, da keine Lösung
  - (2,3)
    - (2,3,1) --> Lösung 4 gefunden
    - (2,3,2) --> Keine Lösung
    - (2,3,3) --> Keine Lösung
- (3)
  - (3,1)
    - (3,1,1) --> Keine Lösung
    - (3,1,2) --> Lösung 5 gefunden
    - (3,1,3) --> Keine Lösung
  - (3,2)
    - (3,2,1) --> Lösung 6 gefunden
    - (3,2,2) --> Keine Lösung
    - (3,2,3) --> Keine Lösung
  - (3,3) --> cut, da keine Lösung

Ich hoffe man sieht hier auch wunderbar, die abgeschnittenen Zweige, die dadurch entstehen, dass man Möglichkeiten, von denen man weiß, dass bereits die Teillösung falsch ist, nicht weiter untersuchen muss (siehe die oben aufgeführten Regeln).

klabri - Mo 01.12.08 23:54

Hallo
http://www.google.de/search?hl=de&q=Backtracking+die+L%C3%B6sung&start=20&sa=N
unter diesem Link gibt es (find ich) eine sehr schöne Übersicht,wie die erste Lösung des 8-Dame-Problems zustande kommt, man kann das 'Backtracking' sehr gut nachvollziehen.

---Moderiert von Narses: Beiträge zusammengefasst und überflüssige Leerzeilen entfernt---

Das hier ist der richtige Link... [url]http://www.freebits.de/cpp/praktikum5/loes_prakt5.pdf[/url]

---Moderiert von Narses: Beiträge zusammengefasst---

Im Anhang eine PDF-Datei,eine Schritt-für-Schritt-Erklärung des Dame-Problems, die ich Anfänger sogar verstehe...

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!