(←) предыдущая запись ; следующая запись (→)
Задача о разборчивом туристе
Есть известная задача о разборчивой невесте, в которой невеста, чтобы найти лучшего жениха из 100,000 претендентов, первых 37,000 свайпает влево, даже если они были ничего так. А потом свайпает вправо первого из рассмотренных, такого что он лучше всех просмотренных. С вероятностью 1 - 1/e ≈ 63%, правда она никого себе не найдёт, а с вероятностью 100% у неё отсохнет палец, но математикам нет дела до чужих страданий.
Я же столкнулся с аналогичной задачей, пытаясь найти наилучший обменник. Но, увы, воспользоваться готовым решением не получается, потому что разборчивый турист гибче разборчивой невесты.
Задача, хоть и похожа по форме, но на самом деле совсем другая. У невесты была цель с максимальной вероятностью выбрать самого лучшего из претендентов, у туриста же цель — оптимизировать сумму в кошельке, и его потери не в вероятности неидеального выбора партнёра, а в объёме недополученных денег.
Какие ещё есть отличия задачи?
Во-первых, если качество женихов распределено не пойми как, то распределение качества обменников можно параметризовать и оценивать в процессе накопления знаний об обменниках. И по классике, в зависимости от того, знаем ли мы априорно официальный курс, мы будем получать разные оценки распределения качества.
В рамках подготовки к разным сценариям апокалипсиса, предлагаю подумать, как вы будете выбирать обменник при гиперинфляции.
Во-вторых, не обязательно всю сумму менять в одном обменнике (для простоты допустим, что нет разницы, менять большую сумму или маленькую).
Вижу богатые возможности по backporting-у условий в оригинальную задачу о разборчивой невесте. Например, можно разрешить двоемужество.
Как при таких вводных будет выглядеть оптимальная стратегия поиска обменника?
Есть ещё нюанс, который мне кажется неинтересными: турист иногда готов вернуться к одному из нескольких последних обменников. В отличие от жениха, ранее отброшенные обменники не закроют перед туристом дверь, оскорблённые первоначальным отказом.
Обратным портированием была бы возможность невесты вернуться к прошлому крашу, пока он сам не женился (можно было бы добавить жениху агентности… впрочем не, это слишком либерально).