АЛЕКСЕЙ, 66 - 30 июля 2012 22:21

КАК СЛЕДУЕТ ИСКАТЬ ВТОРУЮ ПОЛОВИНКУ.

Нам часто нужно выбрать лучшее (с какой–то точки зрения) из некоторой совокупности людей или объектов (например, при покупке товаров или выборе будущего супруга). Для анализа этой проблемы предположим, что людей или объекты можно упорядочить по их достоинствам, т.е. сравнивая любые два из них, можно всегда сказать, какой из них лучше.
Выбор лучшего не представляет трудностей, когда мы видим все объекты. Однако в большинстве случаев объекты или людей рассматривают последовательно и, раз что–то или кого-то, отвергнув, мы к этому вернуться не можем. В дальнейшем будем предполагать, что если «кандидат» не выбран, когда подошла его очередь, то позднее мы не можем изменить наше решение. Но и в этом случае проблема не описана однозначно. Мы можем даже не знать общего числа объектов, из которых должны выбирать. (Как правило, нет такой информации при выборе будущего мужа или жены.) Предположим, что всего имеется n возможностей, точнее n лиц или объектов, проходящих мимо нас в произвольной последовательности (эти последовательности считаются равновероятными). Вопрос состоит в следующем. Исходя, из какого метода выбирать лучшего кандидата, если любого из них можно сравнивать, естественно, только с предыдущими? Если всегда выбирать, например, третьего, то шансы выбрать лучшего равны 1/n. С ростом n величина M/n стремится к 0 и поэтому при большом числе предложений вероятность выбора лучшего близка к 0. Удивительно, но есть метод, позволяющий выбирать лучшего кандидата с вероятностью близкой к 30% даже при больших значениях n. Метод состоит в следующем. После того, как пройдут первые 37% (точнее 100/е) кандидатов, выбираем первого, кто окажется лучше всех предыдущих (если такого нет, то выбираем последнего). В этом случае шансы выбрать лучшего приблизительно равны 1/е, т. е. ~37% как бы ни было велико значение n.