Backtracking parallelisieren?
-
Ich würde gerne einen Backtracking-Algorithmus parallelisieren. Dazu könnte ich im 1. Schritt die Fortsetzungen auf eine Anzahl von Threads verteilen. Das Problem ist, dass, wenn sich schnell herausstellt, dass alle Zweige eines Threads nicht zum Ziel führen, ich einen ganzen Thread verschenkt habe.
Wie könnte man das Problem lösen?
-
Wieso verschenkt? Erst die Berechnung führt doch zum Ergebnis das ein Teilpfad keine Lösung des Problems bieten. Wenn es möglichkeiten geben würde dies vorher zu wissen, brauchst du das ganze Backtracking ja nicht. Ist ja nicht mehr als stupides ausprobieren aller möglichkeiten. Oder hab ich jetzt an der Problemstellung was falsch verstanden?
-
Es könnte aber sein, dass Thread #1 bereits bei Suchbaumtiefe 1 herausfindet, dass es so nicht weiter geht, und Thread #2 erst nach Suchbaumtiefe 10.
-
Vielleicht ginge das:
Speichere in einer Variablen die Anzahl der unbenutzten Kerne. Wenn ein Thread alles abgesucht hat, erhöhe diese Variable um 1. Wenn diese größer als Null ist, verteile bei der nächsten Gelegenheit die Arbeit auf mehrere Threads.
Hat noch jmd einen besseren Vorschlag?
-
Gibts für sowas nicht Threadpools?
-
dssfddsf schrieb:
Vielleicht ginge das:
Speichere in einer Variablen die Anzahl der unbenutzten Kerne. Wenn ein Thread alles abgesucht hat, erhöhe diese Variable um 1. Wenn diese größer als Null ist, verteile bei der nächsten Gelegenheit die Arbeit auf mehrere Threads.
Hat noch jmd einen besseren Vorschlag?
*push*
-
Ich verstehe ehrlich gesagt das Problem nicht. Kannst Du das nochmal anders erklären? Wann und wie soll sich herausstellen, dass ein Teilbaum nicht mehr zielführend ist? Reden wir überhaupt von einem Baum?
-
Backtracking geht ja so:
Finde zum bisherigen Baum alle möglichen Fortsetzungen und wende darauf wieder denselben Algorithmus an. Wenn es keine möglichen Fortsetzungen gibt und wir nicht am Ende sind, dann ist dieser Teilbaum nicht zielführend.
-
Das gleiche Problem ergibt sich bei der Tiefensuche.
-
knivil schrieb:
Das gleiche Problem ergibt sich bei der Tiefensuche.
Welches "Problem" denn nun?
Backtracking/Tiefensuche ist mir natürlich ein Begriff. Musste schon vor 14 Jahren in der Schule per Backtracking das 8-Dame-Problem lösen.
Aber von was für einem Problem sprecht ihr? Bringt das dochmal auf'n Punkt, statt nur drum rum zu reden...
kk
-
krümelkacker schrieb:
Backtracking/Tiefensuche ist mir natürlich ein Begriff. Musste schon vor 14 Jahren in der Schule per Backtracking das 8-Dame-Problem lösen.
Da würde ich auf den Stufen 1 bis 3 in Threads verzweigen und damit maximal 8^3=512 Threads erstellen. Und die weiteren Stufen bis zu den maximal 8^8=16777216 Endstellungen normal rekursiv durchgehen.
krümelkacker schrieb:
Aber von was für einem Problem sprecht ihr?
Ja, davon hängt es ab.