Problemet med den kræsne brud

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. november 2021; verifikation kræver 1 redigering .

Problemet med kræsen brud ( Choice Stopping Problem ) er et optimeringsproblem, som først blev formuleret af Martin Gardner i 1960 .

I engelsk litteratur findes det også under navnet på sekretærproblemet .

Ordlyd

Opgaven kan formuleres som følger [1] :

  1. Bruden søger en brudgom (der er kun én ledig stilling).
  2. Der er et kendt antal kandidater - .
  3. Bruden kommunikerer med ansøgerne i tilfældig rækkefølge, med hver ikke mere end én gang.
  4. Ansøgerne danner en lineær rækkefølge : asymmetrisk, transitiv , og alle to er sammenlignelige - hver ansøger er kendt for at være bedre eller dårligere end nogen af ​​de foregående.
  5. Efter at have talt med ansøgeren sammenligner bruden ham med de tidligere og enten afslår eller accepterer hans tilbud. Hvis forslaget bliver accepteret, gifter de sig, og processen stopper. Hvis bruden nægter brudgommen, vil hun ikke være i stand til at vende tilbage til ham senere.
  6. Målet  er at vælge den bedste kandidat. Selv det andet passer hende ikke.

Beslutninger

I 1963 foreslog Evgeny Dynkin en løsning på dette problem for en bestemt sag. Den generelle løsning blev fundet af Sabir Hussein-Zade i 1966 .

Dette problem har fået stor opmærksomhed, hovedsageligt fordi den optimale strategi har et interessant træk: Hvis antallet af kandidater er stort nok, vil den optimale strategi være at afvise alle de første (hvor  er grundlaget for den naturlige logaritme ) ansøgere og vælg derefter den første, der er bedre end tidligere [2] . Med en stigning har sandsynligheden for at vælge den bedste ansøger en tendens til , det vil sige cirka 37%.

Problemvarianter

Blandt varianterne og generaliseringerne af problemet er der dem, hvor det samlede antal ansøgere ikke er kendt på forhånd, eller dem, hvor det for hver ansøger er muligt ikke kun at sammenligne det med de andre, men også at give det en absolut vurdering [3] .

I afhandlingen af ​​Boris Berezovsky , senere et tilsvarende medlem af Det Russiske Videnskabsakademi , for graden af ​​Doctor of Science "Udvikling af det teoretiske grundlag for algoritmisering til at træffe forprojektbeslutninger og deres anvendelse", forsvaret i 1983, en generalisering af problemet med en kræsen brud betragtes [4] .

Historie

Problemet med kræsen brud ser ud til at være blevet introduceret i 1949 af Merrill M. Flood, som kaldte det brudeproblemet i et foredrag, han holdt samme år. Han nævnte det flere gange i løbet af 1950'erne, såsom i en tale ved en konference i Purdue den 9. maj 1958, og det blev til sidst almindeligt kendt for offentligheden, selvom intet blev offentliggjort på det tidspunkt. I 1958 sendte han et brev til Leonard Gillman, med kopier, til et dusin venner, herunder Samuel Carlin og J. Robbins, hvor han skitserede et bevis på den optimale strategi med et appendiks af R. Palermo, som beviste, at alle strategier er domineret af strategien med at "afvise den første p betingelsesløst, og derefter acceptere den næste kandidat, der er bedre.

Den første publikation var tilsyneladende af Martin Gardner i Scientific American , februar 1960. Han hørte om det fra John H. Fox, Jr. og L. Gerald Marney, som uafhængigt kom op med et lignende problem i 1958; de kaldte det "game of googol". Fox og Marnie kendte ikke den optimale løsning; Gardner søgte råd hos Leo Moser, som (sammen med J. R. Pounder) leverede den korrekte analyse til offentliggørelse i tidsskriftet. Kort efter skrev adskillige matematikere til Gardner for at fortælle ham om et tilsvarende problem, som de havde hørt rygter om, og de var sandsynligvis alle sammen om Floods originale arbejde.

1/e-loven af ​​bedste valg skyldes F. Thomas Bruce (1984).

Ferguson (1989) har en omfattende bibliografi og påpeger, at et lignende (men anderledes) problem blev overvejet af Arthur Cayley i 1875 og endda af Johannes Kepler længe før det.

Noter

  1. ↑ Hussein-Zade, 2003 , s. 3-4.
  2. ↑ Hussein-Zade, 2003 , s. atten.
  3. ↑ Finch, 2003 .
  4. ↑ Hussein-Zade, 2003 .

Links