Zu den Modifikationen von uninformierten Suchverfahren gehören auch solche, bei denen die Forderung nach Exaktheit der Lösung zumindest teilweise "über Bord geworfen" wird. Es handelt sich um Verfahren einer unvollständigen Suche mit der Gefahr, dass wir nur suboptimale Lösungen finden. Ausführlicher zur Frage, weshalb man überhaupt auf eine solche Idee kommen kann später, aber knapp vorweg: Viele Satisfizierungsprobleme und kombinatorische Optimierungsprobleme sind derart komplex, daß eine vollständige Suche auch mit optimierten Verfahren, wie wir sie hier betrachtet haben, ausgeschlossen ist
Unvollständige uninformierte Strategien |
Wähle als nächste Knoten nur die die aussichtsreichsten Knoten aus. |
Man arbeitet also nicht mit allen bei einer Expansion erzeugten Nachfolgern eines Knotens weiter, sondern nur mit denen, bei denen am meisten Asussicht auf Erfolg besteht. Die Kriterien ergeben sich wiederum, wie für die gerichtete und gezielte Tiefensuche, aus lokalen oder globalen Informationen. Eine unvollständige Tiefensuche wird kann also wie eine gerichtete oder gezielte Tiefensuche stattfinden, es werden aber nur die jeweils besten der Nachfolgerknoten weiter verwendet.
Bei unvollständigen Breitensuche werden nicht pro expandiertem Knoten, sondern für jede Ebene des Suchgraphen (also für alle derzeit aktuellen Knoten) nur die besten Knoten der Folgeebene aufbewahrt und alle anderen fallengelassen.