Star-Suche

Grundidee

Stell dir vor, Roger Federer kommt zu einer ETH-Vorlesung.
Alle erkennen ihn – aber er kennt niemanden im Saal.
→ Roger ist der „Star“.

Definition:
In einer Gruppe von Personen $P_{1}, P_{2}, ..., P_{n}$ ist eine Person $P_{s}$ ein Star, wenn:

Alle anderen $P_{t}$ (für $t \neq = s$ ) kennen $P_{s}$ .
Der Star $P_{s}$ kennt niemanden der anderen.

Ziel der Star-Suche

Wir wollen herausfinden, ob es in einer Gruppe einen Star gibt – und falls ja, wer das ist.
Wir dürfen nur Fragen der Form stellen:

„Kennt Person A die Person B?“

Naiver Ansatz

Idee:

Wir fragen alles ab.

Für jede Person $P_{i}$ prüfen wir, ob sie jede andere $P_{j}$ kennt.

Das sind insgesamt $n \cdot (n - 1)$ Fragen.

Beispiel: Bei 4 Personen = 12 Fragen.

So wissen wir am Ende genau, wer wen kennt – aber das ist sehr ineffizient.

Rekursiver Ansatz

Bildliche Vorstellung:

Wir lassen die Personen nacheinander aus dem Raum gehen und behalten nur mögliche Stars zurück.

Vorgehen:

Finde den Star unter den ersten $n - 1$ Personen.
(Also wir lassen eine Person raus und suchen dort den Star.)
Prüfe, ob diese gefundene Person auch in der ganzen Gruppe (mit der letzten Person $P_{n}$ ) ein Star ist:
- Kennt der Star die neue Person? (→ dürfte er nicht)
- Kennt die neue Person den Star? (→ muss sie)
Falls der Kandidat kein Star ist, teste die neue Person $P_{n}$ .
Dazu fragen wir:
- Kennt $P_{i}$ (alle anderen) $P_{n}$ ?
- Kennt $P_{n}$ (die anderen) $P_{i}$ ?

Wenn alle $P_{i}$ $P_{n}$ kennen und $P_{n}$ niemanden kennt, ist $P_{n}$ der Star.

Best Case

Wenn der Star immer sofort gefunden wird (also keine extra Tests nötig sind):

Es werden 2(n – 1) Fragen gestellt.

Beispiel:
Bei 5 Personen = $2 \cdot 4 = 8$ Fragen
(statt 20 beim naiven Ansatz)

Worst Case

Wenn es ganz schlecht läuft – also jedes Mal die falsche Person aus dem Raum geht, und der echte Star erst am Ende erkannt wird –
dann brauchen wir wieder genauso viele Fragen wie beim naiven Ansatz:

$n \cdot (n -1)$ Fragen

Verbesserter Algorithmus

Der Trick: Bevor wir jemanden aus dem Raum „werfen“, prüfen wir kurz, ob diese Person überhaupt ein Star sein kann.

Neuer Schritt:

Bevor wir rekursiv weitermachen:

Wenn die zweitletzte Person $P_{n - 1}$ die letzte $P_{n}$ kennt,
dann tauschen wir sie – und wissen sicher: $P_{n}$ ist kein Star.

Warum?
Weil ein Star niemanden kennen darf.

So sparen wir unnötige Tests in späteren Schritten.

Ergebnis

Mit dieser Verbesserung brauchen wir im Worst Case nur noch:

3n – 4 Fragen

Das ist deutlich besser als $n (n -1)$ .

Zusammenfassung

Algorithmus	Idee	Max. Fragen
Naiv	Alle fragen alles	$n (n -1)$
Rekursiv	Suche schrittweise mit Ausschluss	bis $n (n -1)$
Verbessert	Schließe Nicht-Stars vorher aus	3n – 4

CS Notes

Explorer