Browse Reports

Heuristische Suchalgorithmen sind Verfahren, die in einem Graphen unbekannter, in der Regel exponentieller Groesse nach optimalen Wegen zu einem oder mehreren vorgebenen Zielknoten suchen. Sie verwenden dabei problemspezifisches Wissen, das durch eine Heuristik zur Verfuegung gestellt wird. In diesem Bericht stellen wir heuristische Suchalgorithmen vor, die einen vorgebenen, beschraenkten Speicherplatz der Groesse \pl\ verwenden. Als Mass fuer die Guete eines Verfahrens $A$ betrachten wir die Anzahl der von $A$ expandierten Knoten im Verhaeltnis zu der Anzahl $n$ von Knoten, die das Verfahren \as\ expandiert, um das gleiche Problem zu loesen. Die bisher in der Literatur vorgestellten Verfahren wie \ida, \idacr, \mas, \sma\ etc.\ expandieren bis zu $\Omega(n^2)$ Knoten und weisen einen hohen Overhead auf, der diese Verfahren fuer praktische Anwendungen ungeeignet macht. Fuer unsere Verfahren kann gezeigt werden, da\ss{} die Anzahl der expandierten Knoten durch $O(dn^2/\pl)$ bzw.\ $O(n^2/\pl)$ beschraenkt ist, wobei $d$ die Laenge eines Loesungsweges und $\pl$ die Groe\ss{}e des benoetigten Speichers ist. Bei Verwendung eines entsprechend gro\ss{}en Speichers kann dies zu einer deutlichen Verringerung der Anzahl der expandierten Knoten fuehren. Zudem zeichnen sich diese Algorithmen durch eine wesentlich geringere Anzahl von Update-Operationen der benutzten Datenstrukturen aus, was in praktischen Anwendungen die Laufzeit erheblich reduzieren kann.