Problém vybíravé nevěsty

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 22. listopadu 2021; ověření vyžaduje 1 úpravu .

Problém vybíravé nevěsty ( Choice Stopping Problem ) je optimalizační problém , který poprvé zformuloval Martin Gardner v roce 1960 .

V anglické literatuře se vyskytuje také pod názvem secretary problem .

Formulace

Úkol lze formulovat následovně [1] :

  1. Nevěsta hledá ženicha (je pouze jedno volné místo).
  2. Je znám počet uchazečů - .
  3. Nevěsta komunikuje s žadateli v náhodném pořadí, s každým ne více než jednou.
  4. Žadatelé tvoří lineární pořadí : asymetrické, tranzitivní a kterékoli dva jsou srovnatelné – o každém žadateli je známo, že je lepší nebo horší než kterýkoli z předchozích.
  5. Po rozhovoru se zájemcem ho nevěsta porovná s předchozími a jeho nabídku buď odmítne, nebo přijme. Pokud je návrh přijat, vezmou se a proces se zastaví. Pokud nevěsta odmítne ženicha, nebude se k němu moci později vrátit.
  6. Cílem  je vybrat nejlepšího kandidáta. Ani to druhé jí nesedí.

Rozhodnutí

V roce 1963 Evgeny Dynkin navrhl řešení tohoto problému pro konkrétní případ. Obecné řešení našel Sabir Hussein-Zade v roce 1966 .

Tomuto problému je věnována velká pozornost, především proto, že optimální strategie má zajímavou vlastnost: je-li počet kandidátů dostatečně velký, optimální strategií bude odmítnout všechny první (kde  je základ přirozeného logaritmu ) uchazeče a pak vyberte prvního, kdo je lepší ze všech předchozích [2] . S nárůstem se pravděpodobnost výběru nejlepšího žadatele blíží , tedy přibližně 37 %.

Problémové varianty

Mezi varianty a zobecnění problému patří takové, u kterých není předem znám celkový počet uchazečů, nebo takové, u kterých je možné jej u každého uchazeče nejen porovnat s ostatními, ale také mu dát absolutní hodnocení [3] .

V disertační práci Borise Berezovského , pozdějšího člena korespondenta Ruské akademie věd , pro titul doktora věd „Rozvoj teoretických základů algoritmizace pro rozhodování před projektem a jejich aplikace“, obhájené v roce 1983 zobecnění o problému vybíravé nevěsty se uvažuje [4] .

Historie

Zdá se, že problém vybíravé nevěsty zavedl v roce 1949 Merrill M. Flood, který jej nazval problémem nevěst v přednášce, kterou přednesl téhož roku. Během 50. let se o něm několikrát zmínil, například v projevu na konferenci v Purdue 9. května 1958, a nakonec se stal široce známým veřejnosti, ačkoli v té době nebylo nic publikováno. V roce 1958 poslal dopis Leonardu Gillmanovi s kopiemi tuctu přátel, včetně Samuela Carlina a J. Robbinse, v němž nastínil důkaz optimální strategie s dodatkem R. Palerma, který dokázal, že všem strategiím dominuje strategie „bezpodmínečně odmítněte první p, pak přijměte dalšího kandidáta, který je lepší.

První publikace byla zjevně od Martina Gardnera v Scientific American , únor 1960. Slyšel o tom od Johna H. Foxe, Jr. a L. Geralda Marneyových, kteří nezávisle na sobě přišli s podobným problémem v roce 1958; říkali tomu "hra googol". Fox a Marnie neznali optimální řešení; Gardner požádal o radu Lea Mosera, který (spolu s J. R. Pounderem) poskytl správnou analýzu pro publikaci v časopise. Krátce nato několik matematiků napsalo Gardnerovi, aby mu řekli ekvivalentní problém, o kterém slyšeli zvěsti, a všichni se s největší pravděpodobností sblížili s původním Floodovým dílem.

Nejlepší volbou 1/e-law je F. Thomas Bruce (1984).

Ferguson (1989) má rozsáhlou bibliografii a poukazuje na to, že podobným (ale jiným) problémem se zabýval Arthur Cayley v roce 1875 a dokonce i Johannes Kepler dlouho předtím.

Poznámky

  1. ↑ Hussein-Zade, 2003 , str. 3-4.
  2. ↑ Hussein-Zade, 2003 , str. osmnáct.
  3. ↑ Finch, 2003 .
  4. ↑ Hussein-Zade, 2003 .

Odkazy