New Immissions/Updates:
boundless - educate - edutalab - empatico - es-ebooks - es16 - fr16 - fsfiles - hesperian - solidaria - wikipediaforschools
- wikipediaforschoolses - wikipediaforschoolsfr - wikipediaforschoolspt - worldmap -

See also: Liber Liber - Libro Parlato - Liber Musica  - Manuzio -  Liber Liber ISO Files - Alphabetical Order - Multivolume ZIP Complete Archive - PDF Files - OGG Music Files -

PROJECT GUTENBERG HTML: Volume I - Volume II - Volume III - Volume IV - Volume V - Volume VI - Volume VII - Volume VIII - Volume IX

Ascolta ""Volevo solo fare un audiolibro"" su Spreaker.
CLASSICISTRANIERI HOME PAGE - YOUTUBE CHANNEL
Privacy Policy Cookie Policy Terms and Conditions
Diskussion:Backtracking - Wikipedia

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

  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

[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.

Static Wikipedia (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2007 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2006 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu

Static Wikipedia February 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu