Eine Firma produziert täglich eine große Anzahl elektrischer Bauteile, von denen möglicherweise einige wenige defekt sind. Diese möchte man mit möglichst wenig Aufwand aussortieren. Gelegentlich bietet es sich an, nicht jedes einzelne Teil in eine Testschaltung einzusetzen, sondern viele Bauteile zusammenzuschalten und gemeinsam zu prüfen. Das Prüflämpchen leuchtet auf, wenn alle funktionsfähig sind. Anderenfalls weiß man nur, daß mindestens eines der Teile defekt ist, und muß die Suche fortsetzen.

Ist dieses Vorgehen überhaupt sinnvoll? Die Frage stellt sich auch für analoge Probleme aus gänzlich anderen Gebieten: Kann man etwa aufwendige Massenuntersuchungen auf Krankheitserreger im Blut abkürzen, indem man zunächst Teile der einzelnen Blutproben zusammenschüttet und testet? Bei Dopingkontrollen könnte man ebenso mit Urinproben verfahren.

Wenn man die gesamte Charge in zwei Gruppen unterteilt und der Gruppentest beide Male das Ergebnis „defekt“ – beziehungsweise „befallen“ – liefert, ist man offensichtlich nur wenig klüger als zuvor. Wenn andererseits eine der Gruppen den Test besteht, kann man auf entsprechend viele Einzelprüfungen verzichten. Dieses Prinzip kann man für jede der Teilgruppen, die man weiter untersuchen muß, aufs neue anwenden; stets hat man die Chance, daß eine der – immer kleiner werdenden – Gruppen sich als funktionstüchtig beziehungsweise gesund erweist. Ein solcher Einsparungserfolg ist offenbar um so wahrscheinlicher, je seltener ein Defekt vorkommt. Schon 1960 konnte der Mathematiker Peter Ungar vom Courant-Institut der Universität New York diese Aussage präzisieren: Wenn die Wahrscheinlichkeit eines Teils, defekt zu sein, geringer ist als (3–*5)/2 (ungefähr 0,382), dann wird man mit einem geschickten Gruppenprüfungsverfahren im Durchschnitt weniger Tests benötigen als mit Einzelprüfungen.

Wie viele braucht man im ungünstigsten Fall? Viel mehr als mit Einzelprüfungen, denn bis man herausbekommt, daß wirklich alle Teile defekt sind, hat man zahlreiche Gruppen und Untergruppen geprüft. Allerdings ist dieser Fall äußerst unwahrscheinlich und eine darauf bezogene Aussage daher relativ uninteressant.

Abschätzungen des Suchaufwands für realistischere Bedingungen stellten sich indes als überraschend schwierig heraus. Erst kürzlich konnte Eberhard Triesch in seiner Habilitationsschrift an der Rheinisch-Westfälischen Technischen Hochschule Aachen einen wesentlichen Fortschritt erzielen. Triesch, der inzwischen am Forschungsinstitut für diskrete Mathematik der Universität Bonn arbeitet, fand darauf aufbauend gemeinsam mit Ingo Althöfer von der Universität Bielefeld eine Abschätzung des Testaufwands unter der Voraussetzung, daß die Anzahl der defekten Teile eine vorgegebene Schranke r nicht überschreitet („Edge Search in Graphs and Hypergraphs of Bounded Rank“, erscheint in „Discrete Mathematics“).

Der einfachste Fall ist r=1: Aus einer großen Menge von Gegenständen ist ein spezieller herauszufinden. Jeder Test besteht darin, daß man eine Teilmenge benennt und die Auskunft erhält, ob der gesuchte Gegenstand in der Teilmenge enthalten ist.

Dieser Spezialfall des Problems kommt in einem bekannten Kinderspiel vor: Ein Kind denkt sich einen Gegenstand aus, und das andere muß ihn mit möglichst wenig Ja-Nein-Fragen identifizieren. Die Denksportaufgabe, eine falsche Münze unter vielen echten durch möglichst wenige Wägungen auf einer Balkenwaage herauszufinden, gehört zur gleichen Problemklasse, ebenso wie die weniger spielerische Aufgabe, einen neuen Begriff in eine bestehende Datei einzuordnen. Hier ist der gesuchte Gegenstand das eindeutig bestimmte Stichwort in der Datei, das alphabetisch vor, dessen Nachfolger jedoch hinter dem neuen Stichwort rangiert.

In allen diesen Beispielen besteht die Kunst darin, geschickte Fragen zu stellen oder – was dasselbe ist – geeignete Teilmengen für den Test auszuwählen. Auch wer beim Fragespiel schon weiß, daß das gesuchte Objekt ein Tier ist, tut gut daran, nicht gleich zu fragen: „Ist es ein Elefant?“, sondern mit gröberen Einteilungen des Tierreichs (etwa Wirbeltier, Landbewohner, Säugetier und so fort) das Gesuchte einzukreisen.

Wenn man nun wissen möchte, wie viele Fragen man im schlimmsten Fall benötigt, oder seine Strategie auf diesen Fall ausrichten möchte, stellt man sich zweckmäßig einen unfairen Gegner vor: Der denkt sich anfangs gar kein bestimmtes Objekt aus, sondern beantwortet jede Frage so, daß er es seinem Gegner möglichst schwer macht – es muß aber, wohlgemerkt, wenigstens einen Gegenstand geben, auf den alle bisherigen Antworten zutreffen. Eine Strategie, die gegen einen solch hinterhältigen Gegner Erfolg hat, ist für das Schlimmste gewappnet. Das ist das Minimax-Prinzip der Spieltheorie: Man minimiert den Aufwand für den Fall maximalen Ärgers.

Jede Frage läuft darauf hinaus, dem Gegner zwei Teilmengen einer Grundgesamtheit – zum Beispiel „Elefanten“ und „Nicht-Elefanten“ – zur Auswahl anzubieten. Dieser wird entsprechend seiner obstruktiven Zielsetzung die größere wählen: „Nein, es ist kein Elefant.“ Die beste Gegenstrategie für den Ratenden besteht deshalb darin, die jeweilige Grundmenge in zwei möglichst gleich große Teilmengen zu zerlegen und so mit jeder Frage die Anzahl der verbleibenden Objekte zu halbieren.

Theoretisch kann man so mit 21 Fragen ein bestimmtes unter 221 Objekten – mehr als 2 Millionen – ausfindig machen. Allgemein gilt, daß die Anzahl k der Fragen, die man bis zum Ziel benötigt, gleich dem – nach oben aufgerundeten – Zweierlogarithmus aus der Anzahl n der Objekte ist. Das entspricht einem Satz aus der Informationstheorie: Um eine Menge aus n Elementen durchzunumerieren – das heißt jedes von ihnen eindeutig zu kennzeichnen –, braucht man k-stellige Binärzahlen. Die gesuchte Information beträgt also k Bits, entsprechend k Ja-Nein-Fragen.

Der allgemeine Fall, daß mehrere unbekannte (defekte) Gegenstände zu identifizieren sind (r größer als 1), ist erheblich komplizierter. Erstens besteht die Menge der denkbaren Lösungen nicht mehr einfach aus den Elementen der Grundmenge, sondern aus allen r-elementigen Teilmengen; das sind erheblich mehr. Zweitens wird man wieder die Menge der in Frage kommenden Gegenstände in zwei Teilmengen zerlegen, aber diesmal nicht unbedingt so, daß in beiden gleich viele Gegenstände liegen, sondern so, daß zu beiden gleich viele Lösungsmöglichkeiten gehören. Das Zerlegungsproblem ist auch mit Hilfe eines Computers schwer (im Jargon: „NP-vollständig“) und in jedem Fall nur angenähert lösbar (Bild); es gelang Althöfer und Triesch jedoch zu zeigen, daß man die Abweichungen in (berechenbaren) Grenzen halten kann. Drittens können sich in beiden Teilmengen der gewählten Zerlegung defekte Teile finden, so daß das zugehörige Testergebnis nicht so leicht zu verwerten ist.

Angesichts dieser Schwierigkeiten ist das Resultat von Althöfer und Triesch überraschend günstig: Wenn r größer als 1 ist, sind zwar zusätzliche Tests erforderlich. Aber deren Anzahl gr hängt nur von r, nicht von der Anzahl n der Gegenstände ab. Man kann sogar beweisen, daß gr sich nicht ändert, wenn der verwendete Test durch einen weniger empfindlichen ersetzt wird, der beispielsweise erst oberhalb einer gewissen Mindestkonzentration an Erregern in der Blutprobe anspricht. Die genaue Größe von gr ist noch unbekannt. Aber dieses Zusatzproblem scheint nicht mehr unüberwindlich. Peter Damaschke aus Hagen vermochte bereits zu zeigen, daß im Falle r=2 eine einzige Zusatzfrage genügt (das Bild zeigt ein Beispiel).

Althöfer und Triesch haben ihr Ergebnis nicht bewiesen, indem sie eine konkrete Teststrategie angaben, sondern auf nicht-konstruktivem Wege. Eine genaue Analyse des Beweises liefert jedoch eine Teststrategie mit den Eigenschaften des bewiesenen Satzes: Die Zahl der erforderlichen Zusatzfragen ist unabhängig von der Anzahl der Gegenstände nach oben beschränkt. Ob man möglicherweise regelmäßig mit einer Frage weniger auskommen würde, muß vorläufig offen bleiben.


Aus: Spektrum der Wissenschaft 2 / 1993, Seite 32
© Spektrum der Wissenschaft Verlagsgesellschaft mbH