Diskussion:Backtracking
aus Wikipedia, der freien Enzyklopädie
Der Artikel beleuchtet nur den Standardfall des Backtrackings, nämlich chronologisches Backtracking. Da ist dann auch die Aussage korrekt, dass Backtracking eine Tiefensuche durchführt. Prinzipiell spricht aber nichts dagegen, bei einem Fehlschlag andere Strategien zur Bestimmung des nächsten Backtrackpunkts zu wählen. Hier liegt Breitensuche nahe, aber beliegig andere (intelligente) Suchstrategien sind denkbar. Die Fokussierung auf Tiefensuche kommt einzig und allein daher, dass Tiefensuche sehr einfach zu implementieren ist, weil zur Speicherung der Backtrackpunkte einfach der Stack der (rekursiven) Funktionsaufrufe mitverwendet werden kann. Bei einer separaten Speicherung der Backtrackpunkte (bspw. in einer Hashtabelle) können aber auch andere Strategien einfach implementiert werden.
[Bearbeiten] Versionsgeschichte der alten Version
- Aktuell) (Vorherige) 21:41, 24. Nov 2005 (rv) (bearbeiten) SteveK K (Kategorie geändert)
- (Aktuell) (Vorherige) 10:20, 21. Nov 2005 (rv) (bearbeiten) Timo Müller
- (Aktuell) (Vorherige) 20:58, 18. Okt 2005 (rv) (bearbeiten) 80.130.98.91 (→Zeitkomplexität)
- (Aktuell) (Vorherige) 08:51, 4. Sep 2005 (rv) (bearbeiten) 82.192.228.162 (→Links)
- (Aktuell) (Vorherige) 07:15, 22. Aug 2005 (rv) (bearbeiten) 84.139.212.97 (→Bedeutung)
- (Aktuell) (Vorherige) 10:21, 18. Jun 2005 (rv) (bearbeiten) Zinnmann K (gel. Kat. entf.)
- (Aktuell) (Vorherige) 14:27, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem von und mit Clemenes)
- (Aktuell) (Vorherige) 14:27, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem)
- (Aktuell) (Vorherige) 14:24, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem)
- (Aktuell) (Vorherige) 14:24, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Springerproblem)
- (Aktuell) (Vorherige) 14:23, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Springerproblem)
- (Aktuell) (Vorherige) 11:39, 10. Jun 2005 (rv) (bearbeiten) Wst K (kat)
- (Aktuell) (Vorherige) 18:14, 8. Jun 2005 (rv) (bearbeiten) 80.145.246.243 (→Allgemeiner Algorithmus)
- (Aktuell) (Vorherige) 13:22, 8. Jun 2005 (rv) (bearbeiten) 80.145.215.239 (→Problem des Handlungsreisenden)
- (Aktuell) (Vorherige) 17:46, 3. Mai 2005 (rv) (bearbeiten) 84.141.68.145 (→Problem des Handlungsreisenden)
- (Aktuell) (Vorherige) 00:08, 29. Apr 2005 (rv) (bearbeiten) 85.74.48.99 (Link hinzugefügt)
- (Aktuell) (Vorherige) 19:00, 22. Apr 2005 (rv) (bearbeiten) FlaBot K (warnfile Ergänze:it)
- (Aktuell) (Vorherige) 22:15, 9. Mär 2005 (rv) (bearbeiten) 84.135.235.117
- (Aktuell) (Vorherige) 17:29, 3. Mär 2005 (rv) (bearbeiten) 213.6.99.156
- (Aktuell) (Vorherige) 16:58, 3. Mär 2005 (rv) (bearbeiten) 62.143.131.95 (→Zeitkomplexität)
- (Aktuell) (Vorherige) 11:12, 18. Feb 2005 (rv) (bearbeiten) Mikano (Revert wegen Vandalismus)
- (Aktuell) (Vorherige) 10:01, 18. Feb 2005 (rv) (bearbeiten) 80.144.65.103 (→Springerproblem)
- (Aktuell) (Vorherige) 15:34, 25. Nov 2004 (rv) (bearbeiten) Stern
- (Aktuell) (Vorherige) 15:38, 23. Okt 2004 (rv) (bearbeiten) Klonk
- (Aktuell) (Vorherige) 20:10, 4. Okt 2004 (rv) (bearbeiten) Head (→Beispiele)
- (Aktuell) (Vorherige) 19:51, 4. Okt 2004 (rv) (bearbeiten) 212.152.166.40 (→Springerproblem)
- (Aktuell) (Vorherige) 12:37, 4. Okt 2004 (rv) (bearbeiten) Ckeen
- (Aktuell) (Vorherige) 02:23, 20. Sep 2004 (rv) (bearbeiten) 217.237.97.29 (→Bedeutung)
- (Aktuell) (Vorherige) 02:21, 20. Sep 2004 (rv) (bearbeiten) 217.237.97.29 (→Beispiele)
- (Aktuell) (Vorherige) 07:22, 12. Sep 2004 (rv) (bearbeiten) 129.13.186.1
- (Aktuell) (Vorherige) 07:20, 12. Sep 2004 (rv) (bearbeiten) 82.83.137.243 (→Zeitkomplexität - typo)
- (Aktuell) (Vorherige) 22:33, 9. Sep 2004 (rv) (bearbeiten) 143.93.17.28 (→Rucksackproblem)
- (Aktuell) (Vorherige) 08:11, 13. Jul 2004 (rv) (bearbeiten) Bizaro K
- (Aktuell) (Vorherige) 17:13, 9. Jul 2004 (rv) (bearbeiten) Orcus K (TSP und Färbeproblem waren vertauscht, Link auf TSP)
- (Aktuell) (Vorherige) 10:53, 29. Jun 2004 (rv) (bearbeiten) Martin Sebastian Panzer (Allgemeiner Algorithmus, Zeitkomplexität, Beispiele)
- (Aktuell) (Vorherige) 07:40, 16. Jun 2004 (rv) (bearbeiten) 80.135.157.91
- (Aktuell) (Vorherige) 19:40, 5. Mai 2004 (rv) (bearbeiten) Crux K (link)
- (Aktuell) (Vorherige) 18:50, 5. Mai 2004 (rv) (bearbeiten) HaSee K (Tippfehler)
- (Aktuell) (Vorherige) 18:50, 5. Mai 2004 (rv) (bearbeiten) HaSee K (Tippfehler)
- (Aktuell) (Vorherige) 18:31, 5. Mai 2004 (rv) (bearbeiten) 217.83.6.245
[Bearbeiten] Aufwand ?
Bei Tiefensuche steht, dass er eine Wortcase Laufzeit von O(|V|+|E|) hat.
Jedoch wird bei der Erklärung zum Backtracking gesagt, dass die Tiefensuche eine Laufzeit von O(z^n) hat ?
So was ist jetzt richtig ?
-
- Die Frage ist, als was z und n definiert sind. Wenn der Backtracking-Algorithmus auf einem Baum arbeitet, der den maximalen Verzweigungsgrad z und die maximale Tiefe n hat, ist die Aussage richtig. Jedoch wurde die Tiefensuche hier als Algorithmus (allgemeiner) auf einem Graph definiert. Wenn dieser zufällig ein Baum mit diesen Parametern n und z ist, dann ist |V|<=(z^n-1)/(z-1)=O(z^n) und |E|=|V|-1 ebenso. Das Problem ist nur, was man als die Problemgröße ansieht.