Diskussion:Backtracking

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.

effizientere Verfahren

Wieso steht beim Springer-Problem "Es gibt jedoch weitaus effizientere Verfahren für die Lösung dieses Problems."? Das dürfte wohl für so ziemlich alle der genannten Probleme gelten. Und wenn man sie nicht nennt, sollte man auch nicht auf effizientere Verfahren verweisen. Es sei denn, als allgemeine Aussage. Dann aber nicht bei nur einem der genannten Beispiele.

Es fehlt sowieso ein Link auf den leider noch nicht vorhandenen Artikel Backjumping, dann hätte man sich da schön aus der Affaire ziehen können, indem man einfach darauf verweist :) --84.147.74.214 17:10, 5. Jul. 2011 (CEST)

Versionsgeschichte der alten Version

1. Aktuell) (Vorherige) 21:41, 24. Nov 2005 (rv) (bearbeiten) SteveK K (Kategorie geändert)
2. (Aktuell) (Vorherige) 10:20, 21. Nov 2005 (rv) (bearbeiten) Timo Müller
3. (Aktuell) (Vorherige) 20:58, 18. Okt 2005 (rv) (bearbeiten) 80.130.98.91 (→Zeitkomplexität)
4. (Aktuell) (Vorherige) 08:51, 4. Sep 2005 (rv) (bearbeiten) 82.192.228.162 (→Links)
5. (Aktuell) (Vorherige) 07:15, 22. Aug 2005 (rv) (bearbeiten) 84.139.212.97 (→Bedeutung)
6. (Aktuell) (Vorherige) 10:21, 18. Jun 2005 (rv) (bearbeiten) Zinnmann K (gel. Kat. entf.)
7. (Aktuell) (Vorherige) 14:27, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem von und mit Clemenes)
8. (Aktuell) (Vorherige) 14:27, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem)
9. (Aktuell) (Vorherige) 14:24, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Damenproblem)
10. (Aktuell) (Vorherige) 14:24, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Springerproblem)
11. (Aktuell) (Vorherige) 14:23, 13. Jun 2005 (rv) (bearbeiten) 193.170.118.199 (→Springerproblem)
12. (Aktuell) (Vorherige) 11:39, 10. Jun 2005 (rv) (bearbeiten) Wst K (kat)
13. (Aktuell) (Vorherige) 18:14, 8. Jun 2005 (rv) (bearbeiten) 80.145.246.243 (→Allgemeiner Algorithmus)
14. (Aktuell) (Vorherige) 13:22, 8. Jun 2005 (rv) (bearbeiten) 80.145.215.239 (→Problem des Handlungsreisenden)
15. (Aktuell) (Vorherige) 17:46, 3. Mai 2005 (rv) (bearbeiten) 84.141.68.145 (→Problem des Handlungsreisenden)
16. (Aktuell) (Vorherige) 00:08, 29. Apr 2005 (rv) (bearbeiten) 85.74.48.99 (Link hinzugefügt)
17. (Aktuell) (Vorherige) 19:00, 22. Apr 2005 (rv) (bearbeiten) FlaBot K (warnfile Ergänze:it)
18. (Aktuell) (Vorherige) 22:15, 9. Mär 2005 (rv) (bearbeiten) 84.135.235.117
19. (Aktuell) (Vorherige) 17:29, 3. Mär 2005 (rv) (bearbeiten) 213.6.99.156
20. (Aktuell) (Vorherige) 16:58, 3. Mär 2005 (rv) (bearbeiten) 62.143.131.95 (→Zeitkomplexität)
21. (Aktuell) (Vorherige) 11:12, 18. Feb 2005 (rv) (bearbeiten) Mikano (Revert wegen Vandalismus)
22. (Aktuell) (Vorherige) 10:01, 18. Feb 2005 (rv) (bearbeiten) 80.144.65.103 (→Springerproblem)
23. (Aktuell) (Vorherige) 15:34, 25. Nov 2004 (rv) (bearbeiten) Stern
24. (Aktuell) (Vorherige) 15:38, 23. Okt 2004 (rv) (bearbeiten) Klonk
25. (Aktuell) (Vorherige) 20:10, 4. Okt 2004 (rv) (bearbeiten) Head (→Beispiele)
26. (Aktuell) (Vorherige) 19:51, 4. Okt 2004 (rv) (bearbeiten) 212.152.166.40 (→Springerproblem)
27. (Aktuell) (Vorherige) 12:37, 4. Okt 2004 (rv) (bearbeiten) Ckeen
28. (Aktuell) (Vorherige) 02:23, 20. Sep 2004 (rv) (bearbeiten) 217.237.97.29 (→Bedeutung)
29. (Aktuell) (Vorherige) 02:21, 20. Sep 2004 (rv) (bearbeiten) 217.237.97.29 (→Beispiele)
30. (Aktuell) (Vorherige) 07:22, 12. Sep 2004 (rv) (bearbeiten) 129.13.186.1
31. (Aktuell) (Vorherige) 07:20, 12. Sep 2004 (rv) (bearbeiten) 82.83.137.243 (→Zeitkomplexität - typo)
32. (Aktuell) (Vorherige) 22:33, 9. Sep 2004 (rv) (bearbeiten) 143.93.17.28 (→Rucksackproblem)
33. (Aktuell) (Vorherige) 08:11, 13. Jul 2004 (rv) (bearbeiten) Bizaro K
34. (Aktuell) (Vorherige) 17:13, 9. Jul 2004 (rv) (bearbeiten) Orcus K (TSP und Färbeproblem waren vertauscht, Link auf TSP)
35. (Aktuell) (Vorherige) 10:53, 29. Jun 2004 (rv) (bearbeiten) Martin Sebastian Panzer (Allgemeiner Algorithmus, Zeitkomplexität, Beispiele)
36. (Aktuell) (Vorherige) 07:40, 16. Jun 2004 (rv) (bearbeiten) 80.135.157.91
37. (Aktuell) (Vorherige) 19:40, 5. Mai 2004 (rv) (bearbeiten) Crux K (link)
38. (Aktuell) (Vorherige) 18:50, 5. Mai 2004 (rv) (bearbeiten) HaSee K (Tippfehler)
39. (Aktuell) (Vorherige) 18:50, 5. Mai 2004 (rv) (bearbeiten) HaSee K (Tippfehler)
40. (Aktuell) (Vorherige) 18:31, 5. Mai 2004 (rv) (bearbeiten) 217.83.6.245

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.

Backtracking = Tiefensuche

Sind Backtracking und Tiefensuche dasselbe? Der Artikel lässt es vermuten, aber sagt es nicht explizit. Hier wäre eine definitive Aussage sehr hilfreich

Nun das kann man nicht sagen, wie im ersten Abschnitt dieser Seite schon zu lesen ist. Backtracking bezeichnet lediglich die Idee, Rechenschritte rückgängig zu machen, sobald klar ist, dass der aktuelle Weg nicht zum Ziel führt. Wie dieses "Rückgängigmachen" nun umgesetzt wird, ist freigestellt. Es sind verschiedene Strategien möglich: Breitensuche, Tiefensuche, iterative Vorgehensweisen etc. (nicht signierter Beitrag von 92.226.81.216 (Diskussion | Beiträge) 14:19, 18. Dez. 2009 (CET))

Gehört Backtracking nicht auch in die Kategorie Suchalgorithmus?

Gehört Backtracking nicht auch in die Kategorie Suchalgorithmus?

http://de.wikipedia.org/wiki/Kategorie:Suchalgorithmus

Danke! (nicht signierter Beitrag von 93.200.245.143 (Diskussion) 23:06, 30. Okt. 2011 (CET))