| Autor |
Beitrag |
klabri
Beiträge: 50
|
Verfasst: Fr 28.11.08 19:51
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
 
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: 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  _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
klabri 
Beiträge: 50
|
Verfasst: So 30.11.08 16:05
Hallo
"Backtracking entspricht einer Traversierung des durch die oben aufgespannten Eigenschaften aufgespannten "Lösungsbaumes". "
Kannst du mir mal den Anfang dieses "Lösungsbaumes" erklären?
Ich bin leider "Anfänger..."
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 30.11.08 16:56
NEhmen wir mal das Beispiel alle Permutationen der Ziffern 1,2,3 ohne Wiederholung:
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). _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
klabri
Beiträge: 50
|
Verfasst: So 30.11.08 17:13
DANKE für die schnelle Antwort,dass macht hilft mir weiter !!
Bis zur nächsten Frage ...
|
|
klabri
Beiträge: 50
|
Verfasst: Mo 01.12.08 23:54
Hallo
www.google.de/search...mp;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] www.freebits.de/cpp/...oes_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...
Einloggen, um Attachments anzusehen!
|
|
|
