tiefensuche/breitensuche

[borg]

ich versuche grad rauszubekommen um wieviel langsamer die breitensuche gegenüber der tiefensuche ist (beim schach).
sei n die anzahl der zugmöglichkeiten, z die zugtiefe und N die anzahl der zu analysierenden partien.

dann gilt für die tiefensuche:
$N_T = n^z$

für die breitensuche gilt:
$N_B = n^0 + n^1 + n^2 + ... + n^z$

bei der breitensuche durchsuche ist jede ebene einmal, bevor ich tiefer gehe. das hat den vorteil das ich die suche zu jederzeit abbrechen kann und ich das beste bis dahin auffindbare ergebnis hab. wenn ich die tiefensuche mittendrin abbreche kann es sein das ich den offensichtlich besten zweig noch gar nicht durchsucht hab.

ich muss also bei der breitensuche
$N\_U = N\_B - N_T = n^0 + n^1 + n^2 + ... + n^{z-1}$
partien mehr analysieren.

wenn ich das jetzt ins verhältnis setze, komm ich auf
$V = \frac{N\_T}{N\_U} \approx n-1$ <<<< seh ich das richtig?

das würde bedeuten, bei n = 40 beträgt der unterschied etwa 1/39 der bei der tiefensuche zu analysierenden partien?
also die breitensuchen ist um ca. 2,5% langamer.
wo ist der denkfehler? das ist doch viel zu wenig oder?

[Jester]

Wieso genau soll denn eines der beiden langsamer sein?

Was willst Du genau vergleichen? Den Aufwand bis Du bei Suchtiefe z bist, oder bis Du alles durchsucht hast? Du mußt doch eh alle Knoten anschauen, da ist die Reihenfolge egal.

Das Hauptproblem bei Breitensuche ist eigentlich die Große Menge an Speicher, die man benötigt. Schau Dir doch mal iterative depth first search an. Da führt man erst ne Tiefensuche bis Tiefe d durch, dann bis d+1 etc.
Damit kannste auch abbrechen wenn's zu lange wird aber Du brauchst nicht so viel Speicher wie bei der Breitensuche. Dafür werden halt die Sachen mehrfach berechnet, das ist aber nicht so schlimm und macht sich nur in nem konstanten Faktor bemerkbar, da in nem Suchbaum die meisten Knoten eben in der untersten Ebene liegen.

MfG Jester

[borg]

Jester schrieb:

Schau Dir doch mal iterative depth first search an. Da führt man erst ne Tiefensuche bis Tiefe d durch, dann bis d+1 etc.

jo, das meinte ich mit breitensuche in dem fall.

Jester schrieb:

Dafür werden halt die Sachen mehrfach berechnet, das ist aber nicht so schlimm und macht sich nur in nem konstanten Faktor bemerkbar

jo, den hab ich versucht auszurechnen. konstant ist er aber nur was die suchtiefe angeht, desto mehr zugmöglichkeiten, desto kleiner ist der faktor.
für n=40 bin ich auf einen faktor von ~1,025 gekommen, die frage ist ob das sein kann? scheint mir fast zu klein.

allgemein ist der faktor laut meiner rechnerei n/(n-1).

[Jester]

Jo, das sieht eigentlich recht sinnvoll aus. Stimmt auch von der Intuition her, oder? Je größer die Verzweigung, desto mehr Knoten sitzen (im Verhältnis) in der unteresten Ebene.

[borg]

habs jetzt implementiert, es ist laut gprof nen bisschen mehr als 2% langsamer. scheint also zu stimmen, es sind durchschnittlich auch nen bisschen mehr als 40 abzweigungen
jetzt muss ichs nur noch irgendwie auf threads verteilen damit er auch jederzeit rausspringen kann.