Задача о «разборчивой невесте»

Написал и опубликовал Тим Маринин
и поставил теги computer science.

Слушаю Algorithms to Live by, книгу про применение «алгоритмов» к жизни обычных людей. А если точнее, то рассматриваются задачи, которые возникают в computer science, но находки легко перенести в, собственно, жизнь. Пока очень интересно, но самое интересное ещё предстоит послушать.

Первая глава посвящена тому, что на русском называется задачей о разборчивой невесте, а на английском – secretary problem: как найти лучший вариант, если мы не можем сначала посмотреть всех, а потом вернуться к лучшему? То есть, нам представляют варианты по одному, у нас нет общего тотального рейтинга, а только относительный по просмотренным (Кандидат №1 был лучше кандидата №2, но кандидат №3 лучше их обоих).

Лучший алгоритм – “смотри и прыгай” (look and jump): просмотреть 37% (фаза “смотри”) а потом брать первый лучший (фаза “прыгай”). Тогда вероятность выбрать лучший вариант из всех возможных – как ни странно, тоже 37% (сам не считал, числа из книги).

Я ещё давно писал про применение этого к поиску квартиры , а Пешехонов заметил, что тогда надо знать, сколько квартир всего я собираюсь посмотреть. Так вот, если количество заявок на время примерно стабильно, то можно отсчитывать не от общего n, а времени, отведённого на поиск. И к задаче поиска квартиры это более чем применимо.

Ещё эту задачу кучу раз модифицировали с разными условиями (можно вернуться к предыдущему варианту; есть вероятность отказа; etc.), и каждый раз получается что-то интересное. В основном, люди “прыгают” раньше, чем было бы оптимально. Но если внести в задачу стоимость “просмотра” варианта примерно в 1% от разницы между худшим/лучшим вариантом среди возможных, то люди (as in обычные люди) прыгают как раз вовремя.

А я? А я что? Снимаю мансарду возле Чкаловской, которую нашёл практически случайно.