Обсуждение:Задача о разборчивой невесте

Решение не полно

Не указано, что делать, если наилучший жених не попадётся. То ли выбрать последнего, то ли не выбирать никакого.

Транзитивность

А есть ли транзитивность для отношения сравнения женихов? Optisamit 13:23, 30 июня 2014 (UTC)

Ошибка?

В описании решения ошибка! Если всего 100 женихов, а лучшим является, например, 5ый, то в указанном решении требуется пропустить 37 первых, а затем выбирать лучшего из всех просмотренных. Поскольку 5ый наилучший, и он уже просмотрен, невеста не выберет никого из 100 претендентов. Repovesi 20:14, 17 сентября 2012 (UTC)

Это оптимальное решение, которое в среднем будет давать наилучший результат. Никто не говорить, что всегда будет выбираться лучший жених. И еще, по алгоритму нужно будет выбрать не "лучшего из всех просмотренных", а первого жениха, который будет лучше всех предыдущих. Tookser 11:10, 24 июля 2013 (UTC)

Так лучше пятого же никого не встретится! --Nashev 19:49, 3 марта 2014 (UTC)

Ну и что? При заданных условиях не существует алгоритма, который позволит выбрать лучшего. Но это алгоритм, который дает максимальные шансы выбрать этого жениха. Optisamit 13:23, 30 июня 2014 (UTC)

Кажется Repovesi не про это говорил. На сколько я понял он обратил внимание что с некоторой вероятностью (та-же 1/e, кажется) в результате работы алгоритма не будет выбран ни один из кандидатов (все реально рассматриваемые кандидаты хуже одного из первоночально отброшенных и следовательно не могут быть выбраны). Т.е. невеста останется старой девой (: Эту особенность надо иметь в виду, ведь в некоторых приложениях такой результат может быть просто недопустим. MrClon 00:34, 16 октября 2014 (UTC)

вклад Дынкина и Гусейн-Заде

Английская вики утверждает, что решение появилось в 1958 году, а опубликовано было в 1960, то есть раньше публикаций Дынкина и Гусейн-Заде. Возникает вопрос в чём именно заключается их вклад (возможно, они решали какую-то более общую задачу)? Надо бы обновить раздел Решения и упомянуть всех авторов в хронологическом порядке (со ссылками на конкретные публикации). - Maxal 16:56, 10 ноября 2015 (UTC)

Согласен, английская вики сильно расходится с этой страницей в плане истории задачи, но с другой стороны, исходных публикаций нет в интернете, и их надо бы проверить. --Dlougach (обс) 16:14, 4 октября 2016 (UTC)