lvlv1

Categories:

Задача выбора жениха (проблема остановки выбора)

Оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.

Условия задачи:

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

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

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

У задачи нетривиальное решение, но ответ достаточно простой, хоть в нем и содержится число e=2,718 (основание натурального логарифма).

Ответ: Принцессе необходимо хладнокровно отклонить первых n/e кандидатов. После этого, ей нужно дать согласие первому, кто будет лучше предыдущих. Если такой не встретится, выйти замуж за последнего в списке.

Пример: Пускай у порога томятся 100 кандидатов. Принцессе нужно отклонить 37 человек (100/2.71 ~ 37), после чего начать искать лучшего среди оставшихся или согласиться на последнего.

Как применить это на практике?

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

Первые 11 дней просто смотрим квартиры, начиная с 12го ищем такую, которая лучше предыдущих.

Error

Anonymous comments are disabled in this journal

default userpic