Слушаю Algorithms to Live by, книгу про применение «алгоритмов» к жизни обычных людей. А если точнее, то рассматриваются задачи, которые возникают в computer science, но находки легко перенести в, собственно, жизнь. Пока очень интересно, но самое интересное ещё предстоит послушать.
Первая глава посвящена тому, что на русском называется задачей о разборчивой невесте, а на английском – secretary problem: как найти лучший вариант, если мы не можем сначала посмотреть всех, а потом вернуться к лучшему? То есть, нам представляют варианты по одному, у нас нет общего тотального рейтинга, а только относительный по просмотренным (Кандидат №1 был лучше кандидата №2, но кандидат №3 лучше их обоих).
Лучший алгоритм – “смотри и прыгай” (look and jump): просмотреть 37% (фаза “смотри”) а потом брать первый лучший (фаза “прыгай”). Тогда вероятность выбрать лучший вариант из всех возможных – как ни странно, тоже 37% (сам не считал, числа из книги).
Я ещё давно писал про применение этого к поиску квартиры , а Пешехонов заметил, что тогда надо знать, сколько квартир всего я собираюсь посмотреть. Так вот, если количество заявок на время примерно стабильно, то можно отсчитывать не от общего n, а времени, отведённого на поиск. И к задаче поиска квартиры это более чем применимо.
Ещё эту задачу кучу раз модифицировали с разными условиями (можно вернуться к предыдущему варианту; есть вероятность отказа; etc.), и каждый раз получается что-то интересное. В основном, люди “прыгают” раньше, чем было бы оптимально. Но если внести в задачу стоимость “просмотра” варианта примерно в 1% от разницы между худшим/лучшим вариантом среди возможных, то люди (as in обычные люди) прыгают как раз вовремя.
А я? А я что? Снимаю мансарду возле Чкаловской, которую нашёл практически случайно.