Sekretærproblemet

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

Sekretærproblemet er et berømt problem som benytter optimal stopp teori. Problemet har blitt studert mye i statistikk og beslutningsteori. Det er også kjent som giftemålsproblemet, sultanens medgift problemet, googol spillet og beste valg problemet.

Den grunnleggende formuleringen av problemet er som følger: Forestill deg en administrator som ønsker å ansette den beste sekretæren ut av n rangerbare søkere for en stilling. Søkerne blir intervjuet en for en i tilfeldig rekkefølge. En beslutning må treffes umiddelbart etter intervjuet for den enkelte søker. Når søkeren er avvist kan man ikke kalles inn igjen. I løpet av intervjuet kan administratoren rangere søkerne blant alle som er intervjuet så langt, men har ingen kjennskap til kvaliteten til søkere som ennå ikke er intervjuet. Spørsmålet er om den optimale stopp strategi (stopp regelen) som maksimerer sannsynligheten for å velge den beste søkeren. Hvis beslutningen kan utsettes til slutten, kan man løse dette simpelthen med maksimum seleksjons algoritmen og velge den maksimale på slutten. Vanskeligheten er at beslutningen må treffes umiddelbart.

Problemformulering[rediger | rediger kilde]

Selv om det finnes mange måter å formulere problemet på, kan det formuleres som følger:

  • Det skal ansettes en person
  • Det er n søkere til stillingen, og n er kjent.
  • Søkerne, hvis de blir sett under ett, kan rangeres fra best til verst.
  • Søkerne er intervjuet sekvensielt i en tilfeldig rekkefølge, med hver orden like sannsynlig.
  • Umiddelbart etter intervjuet må søkeren enten aksepteres eller forkastes, man kan ikke gå tilbake på beslutningen.
  • Beslutning om å akseptere eller forkaste en søker kan bare være basert på den relative rangeringen av søkerne så langt.
  • Målsetning for den generelle løsningen er å velge den beste søkeren ut av en hel gruppe. Dette er det samme som å maksimere forventet forventet avkastning, med avkastning definert som 1 for den beste søkeren, og 0 ellers.

Litteratur[rediger | rediger kilde]


Wiki letter w.svgDenne artikkelen er foreløpig kort eller mangelfull. Du kan hjelpe Wikipedia ved å utvide den.