В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение(и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются).Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?
естественная стратегия для принцессы состоит из двух стадий:
1) на первых скольких-то претендентов только смотреть (сразу отказывать им, но запоминать, насколько они были хороши)
2) из оставшихся претендентов — выходить замуж за первого же, кто будет лучше всех ранее виденных
но остается вопрос, как выбрать момент s (долю от 0 до 1) перехода от первой стадии ко второй — и здесь вполне можно поставить компьютерный эксперимент:
def concrete_test(s,sigma):
N = len(sigma)
n = math.floor(N*s)
m = max(sigma[:n]) if n>0 else -1
# пропустили долю s кандидатов
# и ждем первого, лучше всех предыдущих
while n<N and sigma[n]<=m: n += 1
return n<N and sigma[n]==N-1 # нашли максимум?
def random_tests(s,N,T):
sigma = np.array(range(N))
wins = 0
for _ in range(T):
random.shuffle(sigma)
if concrete_test(s,sigma): wins += 1
return wins/T
попросил и из этого chatgpt сделать html-версию и мгновенно… получил программу с неправильной генерацией случайной перестановки
но вроде всё удалось исправить — и по ссылке https://dev.mccme.ru/~merzon/compmath/bride.html можно выбрать момент s и посмотреть, насколько успешна ваша стратегия
для меня сюрпризом стало, что в реальности разница между теоретически лучшим вариантом (ну почитайте Гусейна-Заде!) и наивным s=50% (или, скажем, s=25%) ничтожна
(тут, кстати, легко грубо прикинуть: вероятность того, что лучший кандидат во второй половине, а second best в первой, — уже 1/4, так что s=1/2 приводит к успеху с вероятностью больше 25%)
можно дальше, конечно, экспериментировать с разными обобщениями (принцессу устравает не только лучший, но и второй… принцессу разные результаты устраивают в разной степени… принцессе тяжело долго ждать… и т.д.)