Задача о разборчивой невесте или проблема секретаря

Привет, Вы узнаете о том , что такое задача о разборчивой невесте, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое задача о разборчивой невесте, задачи секретаря , настоятельно рекомендую прочитать все из категории Теория вероятностей. Математическая статистика и Стохастический анализ .

задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.

В англоязычной литературе встречается также под названием задачи о секретаре.

Формулировка

Задача может быть сформулирована следующим образом :

1. Невеста ищет себе жениха (существует единственное вакантное место).
2. Есть известное число претендентов — {\displaystyle n}.
3. Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4. Претенденты образуют линейный порядок: асимметричный, транзитивный и любые два сравнимы — о каждом претенденте известно, лучше он или хуже любого из предыдущих.
5. Пообщавшись с претендентом, невеста сравнивает его с предыдущими и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет.
6. Цель — выбрать лучшего претендента. Даже второй ее не устраивает.

Решения

В 1963 году Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико, оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых (где — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих . При увеличении {\displaystyle n} вероятность выбора наилучшего претендента стремится к , то есть примерно к 37 %.

Варианты задачи

Среди вариантов и обобщений задачи встречаются такие, в которых заранее неизвестно общее количество претендентов, или такие, в которых для каждого претендента можно не только сравнить его с остальными, но и дать ему абсолютную оценку .

В диссертации Бориса Березовского, впоследствии члена-корреспондента РАН, на соискание ученой степени доктора наук «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищенной в 1983 году, рассматривается обобщение задачи о разборчивой невесте .

Задача секретаря

Задача секретаря демонстрирует сценарий, включающий теорию оптимальной остановки ^, которая широко изучается в областях прикладной теории вероятностей , статистики и теории принятия решений . Он также известен как проблема брака , в приданом проблема султана , с проблемой суетливого жениха , в гуголе игре , и задачи наилучшего выбора .

Основная форма проблемы такова: представьте себе администратора, который хочет нанять лучшего секретаря из всех. претенденты на должность с высоким рейтингом. Претенденты проходят собеседование по одному в случайном порядке. Решение по каждому конкретному заявителю будет принято сразу после собеседования. После отклонения заявитель не может быть отозван. Во время собеседования администратор получает информацию, достаточную для ранжирования кандидата среди всех кандидатов, проинтервьюированных до сих пор, но не знает о качестве еще не замеченных кандидатов. Вопрос заключается в оптимальной стратегии ( правиле остановки ), чтобы максимизировать вероятность выбора лучшего претендента. Если решение можно отложить до конца, это можно решить с помощью простого алгоритма максимального выбораотслеживания бегового максимума (и того, кто его достиг), и выбора общего максимума в конце. Сложность в том, что решение нужно принимать немедленно.

Самое короткое из известных до сих пор строгих доказательств дает алгоритм вероятностей . Это означает, что оптимальная вероятность выигрыша всегда не менее (где e - основание натурального логарифма ), и последнее верно даже в гораздо большей общности. Оптимальное правило остановки предписывает всегда отказываться от первого кандидаты, которые проходят собеседование, а затем останавливаются на первом кандидате, который лучше, чем каждый кандидат, проинтервьюированный до сих пор (или переходя к последнему кандидату, если этого никогда не происходит). Иногда эту стратегию называют правила остановки, потому что вероятность остановки у лучшего претендента с этой стратегией составляет около уже для умеренных значений . Одна из причин, по которой проблеме секретаря уделяется так много внимания, заключается в том, что оптимальная политика для проблемы (правило остановки) проста и выбирает единственного лучшего кандидата примерно в 37% случаев, независимо от того, 100 или 100 миллионов претендентов.

Формулировка задачи секретаря

Хотя существует множество вариантов, основную проблему можно сформулировать следующим образом:

• Необходимо заполнить одну позицию.
• На должность подано n претендентов, и величина n известна.
• Претендентов, если рассматривать их вместе, можно однозначно распределить от лучших к худшим.
• Кандидаты проходят собеседование последовательно в случайном порядке, причем каждый порядок одинаково вероятен.
• Сразу после собеседования опрошенный кандидат либо принимается, либо отклоняется, и решение является безотзывным.
• Решение принять или отклонить заявителя может быть основано только на относительных рангах заявителей, проинтервьюированных на данный момент.
• Цель общего решения - обеспечить наибольшую вероятность выбора лучшего претендента из всей группы. Это то же самое, что и максимизация ожидаемого выигрыша, при этом выигрыш определяется как один для лучшего претендента и ноль в противном случае.

Кандидат определяется как заявитель , который в интервью, лучше , чем все заявители интервью ранее. Пропустить означает «отклонить сразу после собеседования». Поскольку цель задачи - выбрать единственного лучшего кандидата, для принятия будут рассматриваться только кандидаты. «Кандидат» в этом контексте соответствует концепции записи в перестановке.

Получение оптимальной политики [ править ]

Оптимальная политика для решения проблемы - правило остановки . Под ним, интервьюер отвергает первый г - 1 заявители (заявитель пусть М быть лучшим заявителем среди этого г - 1 заявители), а затем выбирает первый последующий заявитель , который лучше , чем заявитель М . Можно показать, что оптимальная стратегия лежит в этом классе стратегий. ^{[ необходима цитата ]} (Обратите внимание, что мы никогда не должны выбирать кандидата, который не является лучшим кандидатом, которого мы видели до сих пор, поскольку он не может быть лучшим кандидатом в целом.) Для произвольного отсечения r вероятность того, что будет выбран лучший кандидат, равна

Сумма не определена для r = 1, но в этом случае единственно возможная политика - выбрать первого заявителя, и, следовательно, P (1) = 1 / n . Эта сумма получается из того, что если кандидат i является лучшим кандидатом, то он выбирается тогда и только тогда, когда лучший кандидат среди первых претендентов i - 1 находится среди первых r - 1 претендентов, которым было отказано. Устремляя n к бесконечности, пишемв качестве предела (r-1) / n , используя t для (i-1) / n и dt для 1 / n , сумму можно аппроксимировать интегралом

Взяв производную от P ( x ) по, установив его на 0 и решив относительно x , мы находим, что оптимальный x равен 1 / e . Таким образом, оптимальное отсечение стремится к n / e при увеличении n , и лучший кандидат выбирается с вероятностью 1 / e .

Для малых значений n оптимальное r также можно получить стандартными методами динамического программирования . Оптимальные пороги r и вероятность выбора наилучшей альтернативы P для нескольких значений n показаны в следующей таблице.

	1	2	3	4	5	6	7	8	9
	1	1	2	2	3	3	3	4	4
	1.000	0,500	0,500	0,458	0,433	0,428	0,414	0,410	0,406

Вероятность выбора лучшего кандидата в классической задаче секретаря сходится к .

Альтернативное решение задачи секретаря

Эта проблема и несколько модификаций могут быть решены (включая доказательство оптимальности) простым способом с помощью алгоритма шансов , который также имеет другие приложения. Модификации проблемы секретаря, которые могут быть решены этим алгоритмом, включают случайную доступность кандидатов, более общие гипотезы для кандидатов, представляющих интерес для лица, принимающего решения, групповые собеседования для кандидатов, а также определенные модели для случайного числа кандидатов.

Ограничения задачи секретаря

Решение проблемы с секретарем имеет смысл только в том случае, если оправдано предположение, что кандидаты не знают об использованной стратегии принятия решений, потому что у ранних кандидатов нет вообще никаких шансов и они могут не появиться иначе. Об этом говорит сайт https://intellect.icu . ^{[ необходима цитата ]}

Одним из важных недостатков приложений решения классической задачи секретаря является то, что количество претендентов необходимо знать заранее, что бывает редко. Один из способов решить эту проблему - предположить, что количество претендентов является случайной величиной. с известным распределением (Пресман, Сонин, 1972). Однако для этой модели оптимальное решение в целом намного сложнее. Более того, оптимальная вероятность успеха теперь уже не около 1 / е, а обычно ниже. Это можно понять в контексте наличия «цены», которую придется заплатить за незнание количества претендентов. Однако в этой модели цена высока. В зависимости от выбора распределения, оптимальная вероятность выигрыша может приближаться к нулю. Поиск способов справиться с этой новой проблемой привел к новой модели, дающей так называемый 1 / e-закон наилучшего выбора.

1 / электронный закон лучшего выбора задачи секретаря

Суть модели основана на идее, что жизнь последовательна и что реальные проблемы возникают в реальном времени. Кроме того, легче оценить время, в которое конкретные события (прибытие кандидатов) должны происходить чаще (если они происходят), чем оценить распределение числа конкретных событий, которые произойдут. Эта идея привела к следующему подходу, так называемому единому подходу (1984):

Модель определяется следующим образом: кандидат должен быть выбран на некотором временном интервале. с неизвестного номера претендентов с высоким рейтингом. Цель состоит в том, чтобы максимизировать вероятность выбора только лучших при гипотезе, что все порядки прибытия разных рангов равновероятны. Предположим, что у всех кандидатов одинаковая, но независимая друг от друга, плотность времени прибытия. на и разреши обозначают соответствующую функцию распределения времени прибытия, то есть

, .

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

1 / е-стратегия

(i) урожайность для всех вероятность успеха не менее 1 / е,

(ii) является единственной стратегией, гарантирующей эту нижнюю оценку вероятности успеха 1 / e, и эта оценка является оптимальной,

(iii) выбирает, если есть хотя бы один заявитель, ни одного с вероятностью ровно 1 / e.

1 / e-закон, доказанный в 1984 г. Ф. Томасом Брюссом , стал неожиданностью. Причина заключалась в том, что значение около 1 / е раньше считалось недосягаемым в модели для неизвестных, тогда как это значение 1 / e теперь было достигнуто как нижняя граница вероятности успеха, и это в модели с возможно более слабыми гипотезами (см., например, Math. Reviews 85: m).

Закон 1 / e иногда путают с решением классической проблемы секретаря, описанной выше, из-за аналогичной роли числа 1 / e. Однако в законе 1 / e эта роль более общая. Результат также более сильный, поскольку он справедлив для неизвестного числа кандидатов и поскольку модель, основанная на распределении времени прибытия F, более удобна для приложений.

Игра в гугол

Согласно Ferguson 1989 harvnb error: множественные цели (2 ×): CITEREFFerguson1989 ( help ) , задача секретаря впервые появилась в печати, когда она была представлена Мартином Гарднером в его колонке «Математические игры» в журнале Scientific American за февраль 1960 года . Вот как это сформулировал Гарднер: «Попросите кого-нибудь взять столько листов бумаги, сколько ему заблагорассудится, и на каждом листе напишите разное положительное число. Цифры могут варьироваться от мелких долей единицы до числа размером с цифру. гугол(1, за которой следует сотня нулей) или даже больше. Эти листы переворачиваются лицевой стороной вниз и перетасовываются над столом. По одному переворачиваете квитанции лицевой стороной вверх. Цель состоит в том, чтобы перестать вращаться, когда вы дойдете до числа, которое, по вашему мнению, является самым большим в серии. Вы не можете вернуться и выбрать ранее повернутый лист. Если вы перевернете все листы, то, конечно же, вы должны будете выбрать последний из них ».

В статье "Кто решил проблему Секретаря?" Ferguson 1989 harvnb error: множественные цели (2 ×): CITEREFFerguson1989 ( help ) указал, что проблема секретаря осталась нерешенной, как это было заявлено М. Гарднером, то есть как игра с нулевой суммой для двух человек с двумя антагонистическими игроками. В этой игре Алиса, информированный игрок, тайно записывает различные числа наоткрытки. Боб, останавливающий игрок, наблюдает за фактическими значениями и может прекратить переворачивать карты, когда захочет, выигрывая, если последняя повернутая карта имеет общее максимальное количество. Отличие от основной проблемы с секретарем состоит в том, что Боб наблюдает за фактическими значениями, записанными на карточках, которые он может использовать в своих процедурах принятия решений. Цифры на карточках аналогичны количественным качествам претендентов в некоторых версиях задачи секретаря. Совместное распределение вероятностей чисел находится под контролем Алисы.

Боб хочет угадать максимальное число с максимально возможной вероятностью, в то время как цель Алисы - сохранить эту вероятность как можно ниже. Для Алисы неоптимально отбирать числа независимо от некоторого фиксированного распределения, и она может играть лучше, выбирая случайные числа каким-либо зависимым образом. ДляУ Алисы нет минимаксной стратегии, что тесно связано с парадоксом Т. Ковер . Но дляу игры есть решение: Алиса может выбирать случайные числа (которые являются зависимыми случайными величинами) таким образом, что Боб не может играть лучше, чем использование классической стратегии остановки, основанной на относительных рангах ( Gnedin 1994 ).

Эвристическая производительность

В оставшейся части статьи снова рассматривается проблема секретаря для известного числа кандидатов.

Ожидаемые вероятности успеха для трех эвристик.

Stein, Seale & Rapoport 2003 вывели ожидаемые вероятности успеха для нескольких психологически правдоподобных эвристик, которые можно было бы использовать в задаче секретаря. Они исследовали следующие эвристики:

• Правило отсечения (CR): не принимайте ни одного из первых y кандидатов; после этого выберите первого встреченного кандидата (т. е. кандидата с относительным рангом 1). Это правило имеет как частный случай оптимальную политику для классической задачи секретаря, для которой y = r .
• Правило подсчета кандидатов (CCR): выберите y -го встреченного кандидата. Обратите внимание, что это правило не обязательно пропускает кандидатов; он учитывает только то, сколько кандидатов наблюдалось, а не то, насколько глубоко лицо, принимающее решения, находится в последовательности кандидатов.
• Правило последовательных некандидатов (SNCR): выберите первого встреченного кандидата после наблюдения y некандидатов (т. Е. Кандидатов с относительным рангом> 1).

У каждой эвристики есть единственный параметр y . На рисунке (показан справа) показаны ожидаемые вероятности успеха для каждой эвристики в зависимости от y для задач с n = 80.

Вариант кардинальной выплаты

Поиск единственного лучшего кандидата может показаться довольно строгой задачей. Можно представить, что интервьюер предпочел бы нанять более ценного соискателя, чем менее ценного, и не только заботился бы о том, чтобы получить лучшее. То есть интервьюер получит некоторую ценность от выбора кандидата, который не обязательно является лучшим, и полученное значение увеличивается вместе со стоимостью выбранного кандидата.

Чтобы смоделировать эту проблему, предположим, что кандидаты имеют «истинные» значения, которые являются случайными величинами X, полученными iid из равномерного распределения на [0, 1]. Подобно классической задаче, описанной выше, интервьюер только наблюдает, является ли каждый кандидат лучшим на данный момент (кандидат), должен принять или отклонить каждого на месте и должен принять последнего, если он / она найден. (Для ясности, интервьюер не узнает фактический относительный ранг каждого кандидата. Он / она узнает только, имеет ли кандидат относительный ранг 1.) Однако в этой версии выигрышдается истинной стоимостью выбранного претендента. Например, если он / она выберет кандидата, истинная ценность которого составляет 0,8, то он / она заработает 0,8. Задача интервьюера - максимизировать ожидаемую ценность отобранного соискателя.

Так как значения заявителя являются IID черпает из равномерного распределения на [0, 1], ожидаемое значение из т - й заявитель при условии , что дан кем-то

Как и в классической задаче, оптимальная политика задается порогом, который для этой задачи мы обозначим как , на котором интервьюер должен начать прием кандидатов. Bearden 2006 показал, что c либо или же . (Фактически, то, что ближе всего к.) Это следует из того, что данная проблема с претендентов, ожидаемый выигрыш для некоторого произвольного порога является

Дифференцировать относительно c , получаем

Обучение в парадигме последовательного поиска частичной информации. Числа отображают ожидаемые значения претендентов на основе их относительного ранга (из m всех просмотренных на данный момент кандидатов) в различных точках поиска. Ожидания рассчитываются на основе случая, когда их значения равномерно распределены между 0 и 1. Информация об относительном ранге позволяет интервьюеру более точно оценивать кандидатов, поскольку они накапливают больше точек данных для их сравнения.

С для всех допустимых значений , мы находим, что максимизируется на . Поскольку V выпукло в, оптимальный целочисленный порог должен быть либо или же . Таким образом, для большинства значенийинтервьюер начнет принимать кандидатов раньше в версии с кардинальной выплатой, чем в классической версии, где цель состоит в том, чтобы выбрать единственного лучшего кандидата. Обратите внимание, что это не асимптотический результат: он верен для всех. Однако это не оптимальная политика для максимизации ожидаемого значения от известного распределения. В случае известного распределения оптимальный люфт может быть рассчитан с помощью динамического программирования.

Более общая форма этой проблемы, представленная Пэлли и Кремером (2014) ^, предполагает, что по мере прибытия каждого нового заявителя интервьюер наблюдает за их рангом по отношению ко всем кандидатам, которые наблюдались ранее. Эта модель соответствует концепции обучения интервьюера.поскольку они продолжают процесс поиска, накапливая набор прошлых данных, которые они могут использовать для оценки новых кандидатов по мере их поступления. Преимущество этой так называемой модели частичной информации состоит в том, что решения и результаты, достигнутые с учетом информации об относительном ранге, можно напрямую сравнивать с соответствующими оптимальными решениями и результатами, если интервьюеру была предоставлена ​​полная информация о ценности каждого кандидата. Эта проблема полной информации, при которой кандидаты отбираются независимо от известного распределения, а интервьюер стремится максимизировать ожидаемую ценность выбранного кандидата, была первоначально решена Мозером (1956), Сакагучи (1961), и Карлин (1962).

Другие модификации

Существует несколько вариантов задачи секретаря, которые также имеют простые и элегантные решения.

Один вариант заменяет желание выбрать лучшее желанием выбрать второе. Роберт Дж. Вандербей называет это проблемой «постдока», утверждая, что «лучшие» поступят в Гарвард. Для этой задачи вероятность успеха для четного числа претендентов точно равна. Эта вероятность стремится к 1/4, поскольку n стремится к бесконечности, что свидетельствует о том, что легче выбрать лучшее, чем второе из лучших.

Для второго варианта указано количество вариантов больше одного. Другими словами, интервьюер нанимает не одного секретаря, а, скажем, принимает группу студентов из резерва кандидатов. При предположении, что успех достигается тогда и только тогда, когда все отобранные кандидаты превосходят всех невыбранных кандидатов, это снова проблема, которую можно решить. В Vanderbei 1980 было показано, что при четном n и желании выбрать ровно половину кандидатов оптимальная стратегия дает вероятность успеха равную.

Другой вариант - выбор лучшего секретарей из пула , опять же в онлайн-алгоритме. Это приводит к стратегии, родственной классической, и порогу отсечениядля которого классическая проблема является частным случаем Ghirdar 2009 .

Проблема с множественным выбором

Игроку разрешено выбор, и он побеждает, если любой выбор является лучшим. Гилберт и Мостеллер 1966 показали, что оптимальная стратегия задается пороговой стратегией (стратегией отсечения). Оптимальная стратегия относится к классу стратегий, определяемых набором пороговых чисел, где . Первый выбор следует использовать для первых кандидатов, начиная с-го кандидата, и как только будет использован первый вариант, второй вариант должен быть использован для первого кандидата, начиная с -й заявитель и так далее.

Гилберт и Мостеллер показали, что . Для дальнейших случаев, когдасм. Matsui & Ano 2016 (например,).

Когда вероятность выигрыша сходится к ( Гилберт и Мостеллер, 1966 ). Мацуи и Ано 2016 показали, что для любого положительного целого числа, вероятность выигрыша (из выбор секретаря) сходится к где . Таким образом, вероятность выигрыша сходится к а также когда соответственно.

Экспериментальные исследования

Психологи- экспериментаторы и экономисты изучали поведение реальных людей при принятии решений в проблемных ситуациях с секретарями. В значительной степени эта работа показала, что люди склонны прекращать поиск слишком рано. Это можно объяснить, по крайней мере частично, стоимостью оценки кандидатов. В реальных условиях это может означать, что люди недостаточно ищут всякий раз, когда сталкиваются с проблемами, когда альтернативные решения встречаются последовательно. Например, пытаясь решить, на какой заправке вдоль шоссе остановиться для заправки, люди могут недостаточно искать, прежде чем остановиться. Если это правда, то они будут платить за бензин больше, чем если бы они искали дольше. То же самое может быть верно, когда люди ищут в Интернете авиабилеты. Экспериментальное исследование таких проблем, как проблема секретаря, иногда называют исследованием поведенческих операций .

Нейронные корреляты

Несмотря на то, что существует значительный объем нейробиологических исследований интеграции информации или представления убеждений в задачах перцептивного принятия решений с использованием как животных ^{, так} и людей ^, относительно мало известно о том, как это решение чтобы прекратить сбор информации.

Исследователи изучили нейронные основы решения проблемы секретарши у здоровых добровольцев с помощью функциональной МРТ . ^[10] Марков процесс принятия решения (MDP) использовали для количественной оценки стоимости продолжения поиска по сравнению с совершением текущего варианта. Решения о выборе варианта вместо принятия решения касались теменной и дорсолатеральной префронтальной коры, а также вентрального полосатого тела , передней островки и передней поясной извилины . Таким образом, области мозга, ранее участвовавшие в интеграции доказательств и представлении вознаграждения, кодируют пересечения пороговых значений, которые запускают принятие решений о совершении выбора.

История

Проблема секретаря была, по-видимому, введена в 1949 году Меррилом М. Флудом , который назвал ее проблемой невесты в лекции, которую он прочитал в том же году. Он упоминал его несколько раз в течение 1950-х годов, например, во время выступления на конференции в Пердью 9 мая 1958 года, и в конечном итоге он стал широко известен в фольклоре, хотя в то время ничего не было опубликовано. В 1958 году он отправил письмо Леонарду Гиллману с копиями десятку друзей, включая Сэмюэля Карлина и Дж. Роббинса, с изложением доказательства оптимальной стратегии и приложением Р. Палермо, который доказал, что во всех стратегиях доминирует стратегия форма « безоговорочно отклонить первый p , затем принять следующего кандидата, который лучше». (См. Flood (1958).)

Первая публикация была, по-видимому, Мартином Гарднером в Scientific American, февраль 1960 г. Он слышал об этом от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо разработали аналогичную задачу в 1958 году; они назвали это «игрой в гугол». Фокс и Марни не знали оптимального решения; Гарднер попросил совета у Лео Мозера , который (вместе с Дж. Р. Паундером) предоставил правильный анализ для публикации в журнале. Вскоре после этого несколько математиков написали Гарднеру, чтобы рассказать ему об эквивалентной проблеме, которую они услышали через виноградную лозу, и все из которых, скорее всего, можно отнести к оригинальной работе Флода.

Лучший выбор закона 1 / e принадлежит Ф. Томасу Брюссу (1984).

Фергюсон (1989) имеет обширную библиографию и указывает, что похожая (но другая) проблема рассматривалась Артуром Кейли в 1875 году и даже Иоганном Кеплером задолго до этого.

Комбинаторное обобщение

Проблема секретаря может быть обобщена на случай, когда имеется несколько разных должностей. Опять же, естьсоискатели поступают в случайном порядке. Когда кандидат приходит, она показывает набор неотрицательных чисел. Каждое значение указывает ее квалификацию для одной из должностей. Администратор не только должен решить, принимать или нет соискателя, но, если да, также должен назначить ее на постоянное место работы на одну из должностей. Задача - найти задание, в котором сумма квалификаций как можно больше. Эта проблема идентична поиску паросочетания максимального веса в двудольном графе, взвешенном по ребрам, гдеузлы одной стороны прибывают в оперативный режим в случайном порядке. Таким образом, это частный случай онлайн- задачи двустороннего согласования .

Путем обобщения классического алгоритма для задачи секретаря можно получить задание, в котором ожидаемая сумма квалификаций является лишь фактором менее чем оптимальное (оффлайн) задание.

Вау!! 😲 Ты еще не читал? Это зря!

• Задача трех узников
• Условная вероятность
• Теорема Байеса
• Парадокс двух конвертов
• Парадокс с полом ребенка
• Парадокс Бертрана ( вероятность )
• парадокс бертрана ,
• парадокс монти холла ,
• Проблема с присвоением
• Алгоритм коэффициентов
• Оптимальная остановка
• Проблема Роббинса
• Теория поиска
• Проблема стабильного брака

Исследование, описанное в статье про задача о разборчивой невесте, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое задача о разборчивой невесте, задачи секретаря и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Теория вероятностей. Математическая статистика и Стохастический анализ