Marinin.xyz

Задача о разборчивой невесте (Algorithms to Live By)

written by Тим Маринин on 2017-01-17

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

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

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

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

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

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

You can subscribe to my newsletter, which is about the same things as my posts, but in your inbox instead of the browser.

powered by TinyLetter