September 2016

Band 31, Nummer 9

Test Run: Das Sekretärinnenproblem

Von James McCaffrey

James McCaffreyAngenommen, Sie möchten eine Sekretärin einstellen. Sie können aus einem Pool von 100 Bewerberinnen wählen, und Sie führen täglich ein Einstellungsgespräch. Nach dem Gespräch müssen Sie sich sofort für oder gegen die Einstellung der jeweiligen Bewerberin entscheiden. Wenn Sie eine Bewerberin nicht einstellen, können Sie sie nicht erneut einladen. Ihnen fehlt die Zeit, mit allen 100 Kandidaten zu sprechen – welcher Algorithmus kann Ihnen helfen, Ihre Chance für die Auswahl der besten Bewerberin zu maximieren?

Was wir gerade beschrieben haben, ist ein Beispiel des Sekretärinnenproblems. Lösungen des Sekretärinnenproblems haben viele wichtige praktische Anwendungen. Beispielsweise wird beim Machine Learning häufig ein Ansatz für das Beenden des Trainings benötigt, der die Wahrscheinlichkeit der Wahl des besten Vorhersagemodells optimiert.

Das Sekretärinnenproblem ist Teil einer größeren Klasse von Problemen, die manchmal als Probleme der besten Wahl bezeichnet werden und ihrerseits zu den Optimierungsproblemen zählen. Meines Wissens wurde eine Beschreibung des Sekretärinnenproblems (in leicht abweichender Form) erstmals 1960 im Scientific American-Magazin veröffentlicht. Es gibt Dutzende interessante Abwandlungen des Problems.

In diesem Artikel zeige ich, wie das Sekretärinnenproblem mithilfe der sogenannten 1/e-Stoppregel bewältigt werden kann. Die Zielrichtung dieses Artikels lässt sich gut anhand des Demoprogramms aus Abbildung 1 nachvollziehen. Die Demo ist zwar in C# erstellt, aber der Code sollte sich ohne Schwierigkeiten in eine andere von Ihnen bevorzugte Sprache umgestalten lassen.

Sekretärinnenproblem-Demoprogrammausführung
Abbíldung 1 Sekretärinnenproblem-Demoprogrammausführung

Dieser Artikel geht davon aus, dass Sie über mindestens fortgeschrittene Programmierkenntnisse verfügen, aber er nimmt nicht an, dass Sie irgendetwas über das Sekretärinnenproblem wissen. Dieser Artikel enthält den vollständigen Quellcode für das Demoprogramm, sie erhalten ihn aber außerdem über den begleitenden Codedownload.

Die 1/e-Stoppregel

Es kann mathematisch bewiesen werden, dass unter bestimmten Voraussetzungen die Wahrscheinlichkeit, die beste Bewerberin im Sekretärinnenproblem auszuwählen, durch Anwenden der sogenannten 1/e-Regel bzw. des 1/e-Algorithmus maximiert werden kann. Im Kontext des Sekretärinnenproblems verwenden wir den Ausdruck „Kandidat“, um die beste Bewerberin zu einem bestimmten Zeitpunkt zu bezeichnen. Die Bedeutung des Ausdrucks „Kandidat“ weicht hier also etwas vom normalen Sprachgebrauch ab, in dem „Kandidat“ und „Bewerber“ als weitgehend deckungsgleich angesehen würden.

In der folgenden Erläuterung stellt N die Gesamtzahl der Bewerber und e die Eulersche Konstante dar, die näherungsweise 2,71828 beträgt. In Worten ausgedrückt besagt die 1/e-Regel „Überspringe die ersten N/e Bewerber, verfolge aber den besten Kandidaten nach. Dann stelle den ersten Kandidaten ein, der erscheint. Wenn sich nach dem Überspringen der ersten N/e Bewerber kein neuer Kandidat zeigt, erkläre den Durchgang für ungültig und stelle niemanden ein“.

Ein konkretes Beispiel soll den Algorithmus veranschaulichen. Der 1/e-Stopp-Algorithmus ist grafisch in Abbildung 2 dargestellt. Angenommen, Sie haben 10 Bewerber. Jeder Bewerber hat (was Ihnen erst nach dem Einstellungsgespräch bekannt ist) eine Bewertung zwischen 0,0 und 9,0, wobei höhere Werte besser sind. Dies sind die Bewertungen der Bewerber:

(5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0)
  0    1    2    3    4    5    6    7    8    9

Der 1/e-Algorithmus für das Sekretärinnenproblem
Abbildung 2 Der 1/e-Algorithmus für das Sekretärinnenproblem

Bewerberin 0 hat eine Bewertung von 5,0 und das erste Gespräch; Bewerberin 1 hat eine Bewertung von 2,0 und führt das zweite Gespräch usw. Die beste Bewerberin ist die Person 8 mit einer Bewertung von 9,0.

Die Anzahl der zu überspringenden Bewerberinnen ist N/e = 10/2,71828 = 3,6788, also 3 bei Streichung der Nachkommastellen und 4, wenn gerundet wird. Der Unterschied zwischen Streichung der Nachkommastellen und Rundung erweist sich als sehr gering, sofern N nicht sehr klein ist. Angenommen, Sie streichen auf 3.

Sie sprechen mit Bewerberin 0 und bewerten sie mit 5,0. Sie wird dadurch zur Kandidatin, da sie bisher die beste Bewertung hat (auch wenn es noch die einzige ist). Als nächstes befragen Sie Bewerberin 1 und stellen fest, dass sie mit 2,0 bewertet und daher nicht zur Kandidatin wird, da ihre Bewertung nicht besser als 5,0 ist. Sie befragen Bewerberin 2 und ermitteln eine Bewertung von 7,0, wodurch sie zur neuen Kandidatin wird. An diesem Punkt haben Sie mit den ersten N/e = 3 Bewerberinnen gesprochen, das heißt, Sie sind jetzt bereit, den ersten neu auftretenden Kandidaten einzustellen.

Sie befragen Bewerberin 3 und ermitteln eine Bewertung von 1,0 – sie wird also nicht zur Kandidatin. Sie führen ein Gespräch mit Bewerberin 5 und bestimmen eine Bewertung von 0,0 (Sie haben mein Mitgefühl! Ich habe mit dieser Person zusammengearbeitet), daher ist sie auch nicht die Kandidatin. Sie befragen Bewerberin 6 und ermitteln einen Bewertung von 8,0. Das ist die höchste bisher vorgekommene Bewertung, daher wird sie die Kandidatin, und da Sie die ersten N/e Bewerberinnen hinter sich haben, stellen Sie Bewerberin 6 sofort ein.

Beachten Sie, dass der 1/e-Algorithmus in diesem Beispiel nicht die beste Bewerberin gefunden hat, wohl aber die zweitbeste. Wenn Sie den 1/e-Algorithmus auf das Sekretärinnenproblem anwenden, liegt die Wahrscheinlichkeit, dass Sie die beste Bewerberin aus N Bewerberinnen auswählen, annähernd bei 1/e = 1/2,71828 = 0,3679.

Das Demoprogramm

Um das Demoprogramm zu erstellen, habe ich Visual Studio gestartet und ein neues C#-Konsolenanwendungsprogramm mit dem Namen „SecretaryProblem“ erstellt. Das Demoprogramm hat keine nennenswerten .NET-Abhängigkeiten, sodass jede Version von Visual Studio funktionieren sollte. Nach dem Laden des Vorlagencodes habe ich im Fenster des Projektmappen-Explorers mit der rechten Maustaste auf die Datei „Program.cs“ geklickt und sie in die aussagekräftigere „SecretaryProblemProgram.cs“ umbenannt; Visual Studio hat die Umbenennung der Klasse „Program“ automatisch vorgenommen. Oben im Editorfenster habe ich alle Using-Anweisungen mit Verweisen auf nicht benötigte .NET-Namespaces entfernt und nur den Verweis auf den obersten Namespace „System“ übrig gelassen.

Das Demoprogramm besteht aus zwei Teilen. Die ersten paar Zeilen in der Methode „Main“ veranschaulichen den 1/e-Algorithmus bei der Anwendung auf ein bestimmtes Beispiel des Sekretärinnenproblems mit 10 Bewerberinnen. Der zweite Teil der Demo liefert ein Beispiel für eine Simulation, in der der 1/e-Algorithmus 10.000 Mal mit 100 Bewerbern ausgeführt wird.

Dies sind die Schlüsselzeilen mit dem Aufrufcode für den ersten Teil der Demo:

double[] ratings =
  new double[] { 5.0, 2.0, 7.0, 1.0, 4.0, 0.0, 8.0, 3.0, 9.0, 6.0 };
Console.WriteLine("Applicant ratings are: \n");
for (int i = 0; i < ratings.Length; ++i)
  Console.Write(ratings[i].ToString("F1") + "  ");
Console.WriteLine("\n");
int selected = Select(ratings, true);  // Verbose

Ein Problem wird eingerichtet, indem Bewerberinnen als Array vom Typ „double“ definiert werden, wobei der Index eine Bewerberinnen-ID und der Zellwert die Bewertung der Bewerberin darstellt. Bei der einfachen Version des Sekretärinnenproblems wird angenommen, dass sich die Bewertungen aller Bewerberinnen unterscheiden, sodass kein Gleichstand auftreten kann.

Die im Programm definierte Select-Methode akzeptiert ein Array von Bewertungen und verwendet den 1/e-Algorithmus, um den Index der ausgewählten Bewerberin zu bestimmen und zurückzugeben. Die Select-Methode weist viele WriteLine-Anweisungen auf, die den Verlauf ausgeben, wie in Abbildung 1 zu sehen.

Die entscheidenden Zeilen für den Aufrufcode (mit kleineren Bearbeitungen zur Verbesserung der Lesbarkeit) für den zweiten Teil der Demo sind:

int numHiringSessions = 10000;
int numApplicants = 100;
double pBest = Simulation(numApplicants, numHiringSessions);
Console.WriteLine("Simulation prob of best applicant  = " +
  pBest.ToString("F4"));
double pTheory = 1 / Math.E;
Console.WriteLine("Theoretical prob of best applicant = " +
  pTheory.ToString("F4"));

Die im Programm definierte Methode „Simulation“ akzeptiert eine feste Anzahl von Bewerberinnen. Bei einem alternativen Entwurf könnte die Simulation die Anzahl der Bewerberinnen für jeden Versuch zufällig auswählen. Hinter den Kulissen wird die Methode „Simulation“ als Schleife ausgeführt und ruft eine nicht ausführliche Version der Methode „Select“ auf, während zugleich die Anzahl der erfolgreichen Auswahlvorgänge der besten Bewerberin nachverfolgt wird.

Die Select-Methode

Die Definition der Select-Methode beginnt in dieser Form:

static int Select(double[] ratings)
{
  int numApplicants = ratings.Length;
  int numSkip = (int)(numApplicants / Math.E);
  int candidate = 0;  // Best applicant seen
  double bestRating = ratings[0];
  double rating = 0.0;
  bool readyToHire = false;
...

Die Anzahl der Bewerberinnen wird durch die Anzahl der Zellen im Bewertungsarray bestimmt. Das könnte auch explizit dargestellt werden, indem „Select“ ein zusätzlicher Parameter „N“ übergeben wird. Die Variable „numSkip“ ist die Anzahl der zu überspringenden ersten Bewerberinnen, während die bis zum jeweiligen Test beste Bewerberin nachverfolgt wird. Wenn Sie lieber runden möchten, als die Nachkommastellen zu streichen, könnten Sie schreiben:

int numSkip = (int)Math.Round(numApplicants / Math.E);

Die Variable „candidate“ ist die beste Bewerberin zu jedem gegebenen Zeitpunkt während des Einstellungsverfahrens, und die Variable „bestRating“ ist die der Kandidatin zugeordnete Bewertung. Die zwei Variablen werden auf die Werte der ersten Bewerberin initialisiert, statt Dummywerte zu verwenden, wie etwa -1 bzw. -1,0.

Die Variable „rating“ stellt die Bewertung der aktuellen Bewerberin dar und dient nur der besseren Lesbarkeit. Die Boolesche Variable „readyToHire“ ist FALSCH, wenn die die ersten numSkip-1 Bewerberinnen verarbeitet werden und wird anschließend auf WAHR festgelegt.

Der Hauptteil der Methode „Select“ ist kurz und relativ einfach:

...
  for (int applicant = 0; applicant < numApplicants; ++applicant) {
    rating = ratings[applicant];
    if (applicant >= numSkip) readyToHire = true;
    if (rating > bestRating) {
      candidate = applicant;
      bestRating = rating;
      if (readyToHire == true) return candidate;
    }
  }
  return -1;
}

Die Methode durchläuft alle Bewerberinnen im Array „ratings“. Für jede Bewerberin wird die aktuelle Bewerberin zum Kandidaten, wenn die Bewertung der aktuellen Bewerberin höher ist als die beste (höchste) bisher aufgetretene Bewertung. Wenn die Boolesche Variable „readyToHire“ FALSCH ist, werden die Kandidaten identifiziert, aber nicht zurückgegeben. Wenn „readyToHire“ WAHR ist, wird der erste gefundene verfügbare Kandidat zurückgegeben, was im Rahmen des Sektretärinnenproblems der sofortigen Einstellung entspricht.

In einem alternativen Entwurf können zwei Schleifen anstelle einer einzelnen Verarbeitungsschleife verwendet werden; dabei durchläuft die erst Schleife die zu überspringenden Kandidaten, während die zweite Schleife den ersten verfügbaren Kandidaten identifiziert:

// 1. prelim loop
for (int applicant = 0; applicant < numSkip; ++applicant)
{
  // Track best rating seen
}
// 2. hiring loop
for (int applicant = numSkip; applicant < numApplicants; ++applicant)
{
  // Return first Candidate found
}

Möglicherweise tritt nach den ersten <numSkip> Bewerberinnen kein neuer Kandidat in Erscheinung. Nehmen Sie beispielsweise an, dass Sie über acht Bewerberinnen mit den Bewertungen (7,0, 6,0, 5,0, 4,0, 3,0, 2,0, 1,0, 0,0) verfügen. Die Variable „numSkip“ würde auf 8/2,71828 = 2 festgelegt. Nach den Gesprächen mit den ersten zwei Bewerberinnen wäre die beste Bewertung 7.0, und keine der verbleibenden sechs Bewerberinnen würde als Kandidat identifiziert. Die Methode „Select“ gibt den Dummywert -1 zurück, wenn kein Kandidat gefunden wird.

Die Simulation-Methode

In abstraktem Pseudocode sieht die Methode „Simulation“ so aus:

generate applicants / ratings
determine optimal rating
set number_times_best_applicant_selected = 0
loop numTrials times
  randomize order of applicants
  select an applicant using 1/e algorithm
  if selected applicant is optimal
    ++number_times_best_applicant_selected
  end-if
end-loop
return number_times_best_applicant_selected / numTrials

Die Definition der Methode „Simulation“ beginnt mit:

static double Simulation(int numApplicants, int numTrials)
{
  double[] ratings = new double[numApplicants];
  for (int i = 0; i < numApplicants; ++i)
    ratings[i] = (i * 1.0);
  double optimalRating = 1.0 * (numApplicants - 1);
  int numBestSelected = 0;
...

Wie weiter oben beschrieben, sind Bewerberinnen und ihre Bewertungen in einem Array gespeichert, bei dem der Arrayindex die Bewerberinnen-ID und der Zellwert die Bewertung ist. Der Wert in Zelle 0 wird auf 0,0, der Wert in Zelle 1 auf 1.0 festgelegt usw. Wenn beispielsweise N = 100 Bewerberinnen antreten, sind die Bewerberinnen-IDs 0 bis 99, und die optimale Bewertung ist 99,0.

Die Hauptverarbeitungsschleife in der Methode „Simulation“ ist:

for (int trial = 0; trial < numTrials; ++trial) {
  Shuffle(ratings);
  int selected = Select(ratings);
  if (selected == -1)  // failed to select an applicant
    continue;
  double rating = ratings[selected];
  if (rating == optimalRating)
    ++numBestSelected;
}

Eine vom Programm definierte Methode mit dem Namen „Shuffle“ ordnet die Bewertungen an Ort und Stelle neu an und verwendet dazu den Fisher-Yates-Minialgorithmus:

static void Shuffle(double[] ratings)
{
  for (int i = 0; i < ratings.Length; ++i)
  {
    int ri = rnd.Next(i, ratings.Length);  // random index in [i, N)
    double tmp = ratings[i];
    ratings[i] = ratings[ri];
    ratings[ri] = tmp;
  }
}

Der Fisher-Yates-Algorithmus wird häufig in Programmen für Machine Learning und Simulationen verwendet, um die Werte in einer linearen Sammlung zufällig zu mischen. Viele Programmiersprachen, z. B. Python und R, enthalten eine integrierte Shufflemethode als Teil ihrer Bibliothek mit Standardfunktionen. Hier nimmt die vom Programm definierte Methode „Shuffle“ das Vorhandensein eines Objekts mit klassenweitem Gültigkeitsbereich an:

class SecretaryProblemProgram
{
  static Random rnd = new Random(0);
  static void Main(string[] args)
  {
...

Nachdem die Bewertungen randomisiert wurden, ruft die Verarbeitungsschleife in der Methode „Simulation“ die Methode „Select“ auf, um mithilfe des 1/e-Algorithmus eine Bewerberin auszuwählen; die ausgewählte Bewerberin wird anschließend überprüft, um festzustellen, ob sie die optimale Bewerberin ist.

Bei der Prüfung auf den optimalen Kandidaten werden zwei Gleitkommawerte auf exakte Übereinstimmung geprüft:

if (rating == optimalRating)
  ++numBestSelected;

Dieses Vorgehen ist normalerweise keine gute Idee, da einige Gleitkommawerte in der Praxis aufgrund einer festen Anzahl Dezimalstellen nur als Näherungswerte gespeichert werden. Der Vergleich auf exakte Übereinstimmung ist im Fall dieses Beispiels unproblematisch, im allgemeinen ist jedoch ein Vergleich auf große Nähe von Werten zueinander sinnvoller als auf exakte Übereinstimmung.

Zusammenfassung

Die in diesem Artikel vorgestellten Informationen basieren im Wesentlichen auf dem Forschungspapier „Analysis of Heuristic Solutions to the Best Choice Problem“ von W. Stein, D. Seale und A. Rapoport aus dem Jahr 2003. Dieses Dokument ist im Internet von mehreren Speicherorten im PDF-Format abrufbar. Das Papier stellt eine mathematische Analyse der 1/e-Regel und zweier weiterer Regeln vor.

Bei der „Kandidatenanzahlregel“ wird in zufälliger Weise der n-te Kandidat ausgewählt. Für n = 3 wird beispielsweise der dritte angetroffene Kandidat ausgewählt. In dem am Anfang dieses Artikels vorgestellten Beispiel, bei denen die Bewerberinnen und Bewertungen (5,0, 2,0, 7,0, 1,0, 4,0, 0,0, 8,0, 3,0, 9,0, 6,0) lauten, ist der dritte Kandidat die Bewerberin 6 mit einer Bewertung von 8,0, was zufälliger Weise das gleiche Ergebnis wie das der 1/e-Regel ist. Wie sich herausstellt, ist die Kandidatenanzahlregel nicht besonders effektiv.

Die Regel zu „nachfolgenden Nichtkandidaten“ wählt den ersten Kandidaten aus, der nach dem Beobachten von k Nichtkandidaten auftritt. Nehmen Sie beispielsweise k = 3 an. Für die Beispielbewerberinnen und -bewertungen haben die ersten k Nichtkandidaten die Bewertungen 2,0, 1,0 und 4.0. Der nächste Kandidat ist Bewerberin 6 mit der Bewertung 8,0, was, wiederum zufällig, das gleiche Ergebnis ist, wie bei der 1/e-Regel. Die Regel zu nachfolgenden Nichtkandidaten erweist sich als recht gut funktionierend.

Sobald Sie mit der allgemeinen Struktur des Sekretärinnenproblems vertraut werden, werden Ihnen die Grundprinzipien in einer ganzen Reihe von Szenarien begegnen. Immer, wenn Sie sich einer Programmieraufgabe gegenübersehen, die einen ungewissen Endpunkt mit sich bringt, können die Ideen zum Sekretärinnenproblem möglicherweise nützlich sein.


Dr. James McCaffreyist in Redmond (Washington) für Microsoft Research tätig. Er hat an verschiedenen Microsoft-Produkten mitgearbeitet, unter anderem an Internet Explorer und Bing. Dr. McCaffrey erreichen Sie unter jammc@microsoft.com.

Unser Dank gilt den folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Chris Lee und Kirk Olynyk