11 нояб. 2009 г.

Проблема остановки выбора (разборчивая невеста)

Знаете ли вы, что 33% студенток Гарвардского университета вышли замуж за своих преподавателей в 1901 году? Можно представить себе, что написала бы жёлтая пресса про учителей вроде бы приличного ВУЗа, которые не умеют себя контролировать... Впрочем, если разобраться, то окажется, что в том году в Гарварде было всего три студентки, одна из которых вышла замуж за своего профессора. Утверждение может быть абсолютно корректным, но выглядеть дико, если его «удачно» подать. Поэтому знание математики необходимо обществу, если оно не хочет слепо следовать за первым попавшимся жуликом.

Разберём коротко прошлую задачку о странном любовном треугльнике: Женатый Джек любит Анну, которая влюблена в холостого Джорджа. Вроде бы мы не знаем статус Анны, но давайте рассмотрим оба варианта:
- Если Анна состоит в браке, то она и есть тот человек, который любит холостого.
- Если Анна свободна, то женатый Джек является тем человеком, который любит незамужнюю.
Это означает, что ответ «недостаточно данных» является преждевременным. Похоже, интуиция многим мешает разобрать обе возможные ветки этой задачи. Я тоже чуть было так не ответил, но вовремя сообразил, что «не зря же мне эту задачу предложили». И тогда подумал ещё раз, что и привело к полному пониманию ситуации.

Задача очень простая, но, судя по всему, редкий человек успевает заставить себя подумать второй раз... Это очень интересный эффект, мне кажется. Его интересно прочувствовать на себе, чтобы быть внимательнее в жизненно важных ситуациях.

Раз у нас нынче идёт неделя вероятностей, женитьб и чисел вида 1/e (речь о парадоксе с раздачей подарков), то имеет смысл вспомнить ещё одну задачку, которая возникла совсем недавно - буквально 50 лет назад. Мы её знаем как задачу о разборчивой невесте или проблему остановки выбора, а зарубежом она обычно называется «secretary problem» или «marriage problem» (конечно, есть ещё масса названий).

Проблема формулируется так:
- есть множество из N претендентов на одну вакансию/руку принцессы;
- про любых двух претендентов есть надёжный способ определить, какой из них лучше (более того, если А лучше Б, а Б лучше В, то А заведомо лучше В);
- наниматель/принцесса общается с претендентами в случайном порядке;
- с каждым претендентом можно поступить одним из двух способов: согласиться (тогда игра заканчивается), отказать ему (но тогда он больше не вернётся, поэтому уже никогда нельзя будет принять его предложение);

Цель нанимателя/принцессы: выбрать самого лучшего из возможных.
Вопрос: как следует действовать и с какой вероятностью цель будет достигнута?

В чём проблема? А в том, что если принцесса отказала всем, кроме одного, то ей придётся за него выйти. Поэтому слишком большая разборчивость может привести к тому, что она упустит своего самого лучшего принца. Но если она согласится слишком рано, то даже не позволит чемпиону проявить себя. Надо знать меру, но как её найти?

Оказывается, правильная стратегия состоит в следующем:
1. Делим всех N претендентов на две группы: «эксперементальная» (1/e от всех) и «рабочая» (1-1/e от всех).
2. Первой группе (первым N/e претендентам) следует отказать, запоминая, кто из них самый лучший.
3. Представители второй группы уже имеют шансы: следует соглашаться на предложение первого же, кто лучше всех своих предшественников.

Интересно, что при этой стратегии принцесса получит наилучшего принца с вероятностью 1/e (согласитесь, не так уж и мало, учитывая сложность ситуации). Эта задача имеет интересные расширения. Например, если принцесса не слишком привередлива, то она может прожить счастливую жизнь не с самым лучшим принцем, а с тем, кто входит в список «k лучших принцев». Если k=2 (если принцесса согласна на любого из двух самых лучших), то при правильной стратегии она найдёт своего принца с вероятностью 57 процентов.

Рекомендую прочитать интереснейшую книгу на эту тему - Разборчивая невеста (всего 200 килобайт). Это 25-ый выпуск библиотеки «Математическое просвещение» - на двух десятках страниц изложены очень интересные подходы к решению задач (кстати, многие школьники вполне смогут понять этот материал, поэтому стоит попробовать им предложить!). Любители английского языка и противники pdf-файлов найдут статью в википедии (не так подробно, но есть ссылки на близкие по содержанию материалы)

Хорошего дня!

26 комментариев:

  1. Анонимный11.11.2009, 19:55

    Хотел написать, что недостаточно данных, теперь понял, почему.
    Анну я за "человека" не посчитал...

    ОтветитьУдалить
  2. „...но вовремя сообразил, что «не зря же мне эту задачу предложили»“
    Увы, на практике такой роскоши не бывает. Лучше стараться в каждой задаче разбираться сразу до конца, не надеясь на второй раз.
    С проблемой остановки выбора раньше почему-то не сталкивался. Интересно, спасибо.

    ОтветитьУдалить
  3. eyeless-watcher, неожиданно... Вы из Украины, поэтому посчитали, что раз «человек» созвучно с «чоловік», то к женщинам это не относится? ;)

    Xavier, да, я понимаю. В этом смысл подобных задачек - получить «прививку» на будущее, чтобы в следующие разы тщательнее думать.

    ОтветитьУдалить
  4. Ну именно к выбору кандидатов на руку/должность такая задача относится весьма условно, так как:
    1) обычно нет нужды отвечать кандидатам сразу;
    2) надёжного способа (да ещё и транзитивного) определить кто лучше обычно нет.
    Но наверняка свои приложения она имеет.

    Про утверждения и проценты помню задачку:
    «В сосновом бору лиственные деревья составляют 1% от всех.
    Директор лесозаготавливающего предприятия сообщил, что после запланированной ими вырубки (вырубаться будут только сосны) лиственные деревья составят 2%.
    Экологи сочли, что вырубка ~1% деревьев бору не повредит и одобрили проект.
    А сколько же точно процентов леса будет вырублено?»

    ОтветитьУдалить
  5. LisandreL, имхо как раз "сколько точно процентов" не важно, важно только сразу понимать, что вырублено будет много.

    ОтветитьУдалить
  6. Ну это всё-таки задача на тему «проценты», а не ситуация из жизни, так что требуется точное число.
    И, кстати, многим интуиция (без фразы «Экологи сочли…» - её добавил я, намекая что на самом деле всё не так) подсказывает ~1%.
    Причём, увы, даже учителям математики.

    ОтветитьУдалить
  7. Интереса для: сколько времени у Вас уходит на оформление каждой заметки? Просто удивляюсь как люди успевают не просто выделить интересные темы, но еще и оформить их %). Очень правильный распорядок дня или в чем секрет, у меня так не получается :(

    ОтветитьУдалить
  8. LisandreL, а мне интуиция и до фразы про экологов не врала :)
    А насчёт точного числа всё же не соглашусь. Одно дело когда это задачка для "школы", а другое - когда для интереса. В последнем случае различие между точным ответом и "половина леса" на мой взгляд абсолютно неважно.

    ОтветитьУдалить
  9. С Анной может быть еще один вариант:
    Анна - дочь Джека:)

    ОтветитьУдалить
  10. LisandreL
    Интуиция подсказывает что 50 процентов деревьев. И чуть-чуть больше если считать от сосен. Интуиция этого уже подсчитать не шмогла.

    ОтветитьУдалить
  11. Анонимный13.11.2009, 02:27

    Я вот не понимаю, как можно руководствоваться метаматическими фоормулами при выборе принца..разве такое возможно..и вообще что главнее..если человек притягивается, и с ним просто хорошо, можно подумать и о своместной жизни , о семье..а как возможно построить свое счастье на математических выкладках..или я не с той стороны смотрю на все это дело..

    ОтветитьУдалить
  12. Анонимный13.11.2009, 03:36

    а как можно РАЗУМНО ЛЮБИТЬ??? бред какой-то...можно либо чувствовать что-то либо нет..а как можно среди потенциальных принцев еще и ВЫБИРАТЬ?? вот это мне непонятно никак

    ОтветитьУдалить
  13. Анонимный13.11.2009, 04:20

    Слушайте, а почему бы не рассмотреть варианты любовных треугольников: равнобедренный, прямоугольный, равносторонний, разносторонний...можно еще с катетами и гипотенузами поэкспериментировать, с синусами-косинусами, тангенсами и котангенсами

    ОтветитьУдалить
  14. ezoterika77
    1. Примерно так выбирали женихов/невест аристократы XVII-XVIII веков. Отношение «лучше» там определялось по политическим и экономическим факторам.
    2. Абстрактное мышление развивать всё-таки полезно. Ни к чему напрямую перекладывать математическую задачу на конкретный случай, а потом негодовать, мол, в этой области математику применять некорректно.

    ОтветитьУдалить
  15. В последнем случае различие между точным ответом и "половина леса" на мой взгляд абсолютно неважно.
    7vies, а разница нулевая. Ровно 50% леса они и вырубят.

    ezoterika77, для любви у королев есть фавориты.
    А свадьба - это просто сделка, которую хочется провернуть повыгоднее. Как пелось в песне: «жениться по любви не может ни один король». К королевам это тоже относится.

    ОтветитьУдалить
  16. Задача для ezoterika77
    Проблема формулируется так:
    - есть множество из N квартир для вас;
    - про любую из двух квартир есть надёжный способ определить, какая из них лучше (более того, если А лучше Б, а Б лучше В, то А заведомо лучше В);
    - Вы с риелтором просматриваете квартиры в случайном порядке;
    - с каждой квартирой можно поступить одним из двух способов: согласиться купить (тогда игра заканчивается), отказаться (но тогда уже хозяин найдет другого покупателя, поэтому уже никогда нельзя будет принять его предложение);

    Ваша цель: выбрать самую лучшую квартиру из возможных.
    Вопрос: как следует действовать и с какой вероятностью цель будет достигнута?

    ОтветитьУдалить
  17. LisandreL, благодарю за формулировку задачки!

    HAS, спасибо за тёплые слова!
    Я одновременно работаю над двумя-тремя десятками заметок, поэтому надеюсь, что некоторые удаются. Время на одну заметку я не засекал. Но обычно бывает так: придумал идею (происходит само, время не отнимает) -> дошёл до компьютера -> записал в черновик (это достаточно быстро).
    А перед публикацией стараюсь ещё раз оглядеть "свежим взглядом"...

    ezoterika77, это теоретическая задачка. Самое удивительное, я думаю, что она имеет хорошее решение - т.е. с высокой вероятностью (36%) наниматель/принцесса найдёт наилучшего кандидата, даже если их тысячи. Мне кажется, это полезно глубоко осознать, чтобы интуиция работала лучше.

    Уважаемый аноним, в этой задаче никто не предполагает, что принцесса выходит замуж по любви. Она выходит за "лучшего" по какой-то странной шкале - это её цель. Но можно рассматривать задачу найма лучшей секретарши или ещё что-то другое. Присмотритесь к предложению al31f - с другими задачами об остановке выбора всё становится проще, потому что нет этических и моральных проблем, так ведь? :)

    ОтветитьУдалить
  18. Анонимный13.11.2009, 10:23

    Ну тогда все понятно...если не учитывать какие-то моральные принципы..я просто тогда выпала из темы..кстати, недавно читала статью, как Петр 1 женил удачно своих племянниц...там-то как раз ему и повезло , примерно как в задачке

    ОтветитьУдалить
  19. LisandreL, Вы ошибаетесь - если бы так было, я бы не придирался :)
    Точный ответ - не 50%, а 49.(49)%. Разница в полпроцента и есть различие между точным (неинтересным) и приблизительным (интересным) ответом.

    ОтветитьУдалить
  20. LisandreL, я видимо сам ошибся, и считал процент вырубленных сосен, а не процент вырубленного леса. Вы всё же правы :)

    ОтветитьУдалить
  21. 7vie, давайте считать на пальцах.
    В лесу 100 деревьев. 99 сосен и 1 берёза.

    От скольких деревьев 1 берёза составит 2%?
    X*0,02=1
    X=1/0,02
    X=50

    То есть в лесу останется 50 деревьев (1 берёза и 49 сосен).

    А сколько значит было вырублено? 100-50=50.

    То есть сколько процентов леса вырублено?
    50/100=0,5, т.е. ровно 50%.

    Так что придираться вы можете только к своей невнимательности при решении или чтении условия задачи.

    ОтветитьУдалить
  22. LisandreL, да не волнуйтесь Вы так :]
    Моя ошибка, кстати, лишь подтверждает то, что я говорил - интерес в этой задаче только в приблизительном, а не в точном ответе, и от замены "процентов леса" на "процентов сосен" суть не поменяется.

    ОтветитьУдалить
  23. Анонимный16.11.2009, 03:47

    это про свадьбы на Руси:
    http://shkolazhizni.ru/archive/0/n-32012/

    ОтветитьУдалить
  24. Анонимный24.05.2011, 20:01

    проблема

    ОтветитьУдалить
  25. Анонимный18.12.2018, 10:05

    Странная задача, очень странная... Ведь лучший претендент может попасться и в начале выбора, но он будет отвергнут согласно рекомендациям, но тогда уже никого нельзя выбрать, потому что остальные будут уже заведомо хуже.

    ОтветитьУдалить
    Ответы
    1. В реальной жизни у человека мало попыток, а в задачках на теорию вероятностей о количестве попыток часто вообще можно не думать - наша цель максимизировать шансы на принца. В таких жёстких условиях найти принца с вероятностью 1/e - это очень крутой результат, по-моему. Хоть и обидно, конечно, если в реальной жизни придётся довольствоваться оставшимися (1-1/e).

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний