Наверх
Александр, 56 - 25 ноября 2019 11:32
Все
Отредактировано:25.11.19 22:49
Задача о разборчивой невесте (проблема остановки выбора). Оптимизационная задача, сформулированная известным американским популяризатором науки Мартином Гарднером в 1960 году (его книги издавались у нас ещё в СССР! ) Некая невеста ищет себе жениха (т.е. существует единственное вакантное место). Есть заранее известное число претендентов - N. (Например, она сама себе назначила: выберу из 100 первых). Невеста общается с претендентами в каком-то заранее неопределённом порядке, с каждым не более одного раза. О каждом претенденте при встрече ей становится известно, лучше он или хуже любого из предыдущих. В результате общения с текущим претендентом невеста должна либо ему отказать, либо принять его предложение. Если предложение принято, процесс останавливается, если невеста отказывает жениху, то вернуться к нему позже она не сможет. Цель - выбрать лучшего претендента. Оказывается, что если число кандидатов достаточно велико, то существует оптимальная стратегия! Она заключается в том, чтобы отклонить всех первых N/e претендентов ( e ~ = 2,718 - основание натуральных логарифмов), запомнив наилучшего; а затем выбрать первого, кто будет лучше его (т.е. и всех предыдущих). При увеличении N вероятность выбора при такой стратегии наилучшего претендента стремится к 1/e, то есть примерно к 37%. --- Обычно мы любой выбор в штуках не планируем. Но можно, например, по времени. Хотя в неделю или месяц будет происходить разное число случаев выбора, и стратегия сработает похуже, но в среднем за долгое время - вполне похоже на исходный вариант. Итак, если Вы, например, решили посвятить выбору из неких НЕВОЗВРАЩАЕМЫХ возможностей 10 лет, то 3 года, 8 месяцев и 1 неделю проверяете их, а затем выбираете первую, что будет лучше. ----- Так вот, доказано, что любая другая стратегия дает худший результат!
Добавить комментарий
Комментарии: 3
|