Technical Report No. 57, September 1994 - Abstract

Jürgen Eckerle and Sven Schuierer:
Effiziente speicherplatzbeschränkte Graph-Such-Algorithmen

Heuristische Suchalgorithmen sind Verfahren, die in einem Graphen unbekannter, in der Regel exponentieller Größe nach optimalen Wegen zu einem oder mehreren vorgebenen Zielknoten suchen. Sie verwenden dabei problemspezifisches Wissen, das durch eine Heuristik zur Verfügung gestellt wird.

In diesem Bericht stellen wir heuristische Suchalgorithmen vor, die einen vorgebenen, beschränkten Speicherplatz der Größe m verwenden. Als Maß für die Güte eines Verfahrens A betrachten wir die Anzahl der von A expandierten Knoten im Verhältnis zu der Anzahl n von Knoten, die das Verfahren A* expandiert, um das gleiche Problem zu lösen. Die bisher in der Literatur vorgestellten Verfahren wie IDA*, IDA*_CR, MA*, SMA* etc. expandieren bis zu Omega(n^2) Knoten und weisen einen hohen Overhead auf, der diese Verfahren für praktische Anwendungen ungeeignet macht. Für unsere Verfahren kann gezeigt werden, da\ss{} die Anzahl der expandierten Knoten durch O(d*n^2/m) bzw.O(n^2/m) beschränkt ist, wobei d die Länge eines Lösungsweges und m die Größe des benötigten Speichers ist. Bei Verwendung eines entsprechend gro\ss{}en Speichers kann dies zu einer deutlichen Verringerung der Anzahl der expandierten Knoten führen. 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.