@misc{Maier2011, type = {Master Thesis}, author = {Maier, Robert}, title = {Massiv-parallele Suche und effiziente Heuristiken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42448}, school = {Humboldt-Universit{\"a}t zu Berlin}, pages = {81}, year = {2011}, abstract = {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{\"o}ße steigt und f{\"u}r die effektive heuristische Suche in großen Zustandsr{\"a}umen große PDBs n{\"o}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{\"u}tt (2009) zur massiv-parallelen Breitensuche so, dass damit sehr große PDBs erzeugt werden k{\"o}nnen. So entsteht die erste vollst{\"a}ndige 8+8+8 PDB f{\"u}r das 24er-Puzzle. Reinefeld und Sch{\"u}tt implementieren ebenfalls das heuristische Suchverfahren BFIDA* f{\"u}r MapReduce. In dieser Arbeit wird dieser Implementation ein Speedup von 857 bei 2039 Kernen nachgewiesen. Weiterhin f{\"u}hrt diese Arbeit ein Schema ein, mit dem PDBs bei der Suche direkt von der Festplatte gelesen werden k{\"o}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{\"o}ß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{\"u}gung stehende Hauptspeicher ausreicht, eine Gruppe zusammen mit einigen kleineren PDBs zu bilden.}, language = {de} }