Speedup-Anomalien

Durch die unterschiedliche Vorgehensweise beim parallelen Suchen können gegenüber der sequentiellen Suche weniger oder mehr Knoten besucht werden. Dadurch entsteht superlinearer bzw. sublinearer Speedup. Die Bilder 10.2 und 10.3 zeigen Anomalien bei Depth First Search bzw. Best First Search.

Anomalien bei Depth First Search

Sei opt der optimale Zielfunktionswert. Ein Knoten im Zustandsraum mit einem l -Wert b < opt muß von jedem sequentiellen und parallelen Algorithmus expandiert werden. Ein Knoten mit l -Wert b = opt muß nur dann expandiert werden, wenn zu diesem Zeitpunkt noch keine Lösung mit diesem Wert vorliegt.

Anomalien bei Best First Search