Publication Date:
2017-11-15
Description:
Pattern Datenbanken (PDBs) werden in der heuristischen Suche eingesetzt, um irrelevante Pfade in der Suche auszuschließen. Da die Leistung einer PDB mit ihrer Größe steigt und für die effektive heuristische Suche in großen Zustandsräumen große PDBs nötig sind, ist ein paralleler Ansatz notwendig, um sehr große PDBs zu erzeugen. Diese Arbeit erweitert einen, auf MapReduce basierenden, Algorithmus von Reinefeld und Schütt (2009) zur massiv-parallelen Breitensuche so, dass damit sehr große PDBs erzeugt werden können. So entsteht die erste vollständige 8+8+8 PDB für das 24er-Puzzle. Reinefeld und Schütt implementieren ebenfalls das heuristische Suchverfahren BFIDA* für MapReduce. In dieser Arbeit wird dieser Implementation ein Speedup von 857 bei 2039 Kernen nachgewiesen. Weiterhin führt diese Arbeit ein Schema ein, mit dem PDBs bei der Suche direkt von der Festplatte gelesen werden können.
Des Weiteren wird der Nutzen von großen PDBs in einer Gruppe von PDBs untersucht, deren Heuristikwerte maximiert werden. Dazu wird analysiert, wie sich Gruppen von PDBs mit unterschiedlicher Größe verhalten und welche Faktoren bei solchen Konstellationen zum Erfolg der Gruppe beitragen. Es wird gezeigt, dass der Einsatz von großen PDBs effizient ist, wenn der
zur Verfügung stehende Hauptspeicher ausreicht, eine Gruppe zusammen mit einigen kleineren PDBs zu bilden.
Language:
German
Type:
masterthesis
,
doc-type:masterThesis
Format:
application/pdf
Permalink
