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

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

178.130.3.68 09:41, 15 сентября 2011 (UTC)mike.l

В описании решения ошибка! Если всего 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)