Задачи о правилах остановки

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

Типичный пример – задача о разборчивой невесте. Предположим, имеется N женихов, причем из любых двух женихов можно указать лучшего. Женихи рассматриваются в случайном порядке, и невеста хочет выбрать самого лучшего из них. При этом она может сравнивать жениха с рассмотренными ранее, но если некоторый субъект уже был отвергнут, то возвращаться к нему нельзя. Как ей следует поступить? На каком женихе остановиться, чтобы вероятность того, что он наилучший, была максимальной?

Очевидно, эту задачу можно сформулировать так. Имеется N вещественных чисел b ₁, b ₂,..., b_N, среди которых нет одинаковых. Эти числа перемешаны так, что все перестановки равновероятны. Мы последовательно просматриваем эти числа и хотим выбрать самое большое. Возвращаться к числам уже просмотренным и невыбранным запрещается.

Если некоторое число b_k больше всех предыдущих, то мы будем назвать его рекордсменом. Ясно, что наш выбор должен остановиться на каком–то из рекордсменов, поэтому изучим последовательность рекордсменов подробнее. Очевидно, что рекордсменом обязательно будет первое число b ₁. Если , то других рекордсменов вообще не будет. Самое большое из чисел b_k всегда будет рекордсменом, на каком бы месте оно не стояло.

Обозначим r_k номер в порядке рассмотрения чисел (k + 1)-го рекордсмена: r ₀ = 1, так как первый рекордсмен b ₁. Если r_n номер последнего рекордсмена в последовательности b ₁, b ₂,..., b_N, то условимся считать, что r_m = ¥ при m > n. Нетрудно проверить, что r ₀, r ₁,..., r_n – марковская цепь. Состояния этой цепи суть числа 1, 2,...., N и точка ¥. Найдем ее переходные вероятности:

При n £ k вероятность, стоящая в числителе, равна нулю. При ¥> n > k событие { r_i = k, r_{i + 1} = n } означает, что среди чисел b ₁, b ₂,..., b_n правее всех оказались b_k и b_n, причем b_k > b_n. Вероятность этого события равна Вероятность, стоящая в знаменателе, равна 1/ k.

Таким образом, вероятности p_kn для цепи r_i равны 0 при n £ k <¥. Вероятность того, что k -й рекордсмен последний, вычисляется по формуле

Если b_k – последний рекордсмен, то b_k – абсолютный чемпион, наибольшее число. Следовательно, если мы остановимся на рекордсмене b_k, то мы выиграем, то есть выберем наибольшее число с вероятностью P_{k ¥} = k / N.

Посмотрим, какова будет вероятность q_k выигрыша, если мы остановимся на следующем после b_k рекордсмене. C вероятностью p_kn следующим рекордсменом будет b_n и с вероятностью p_{n ¥} этот рекордсмен будет последним, поэтому

Отношение с ростом k монотонно убывает. Пока оно больше единицы, останавливаться не стоит: вероятность выигрыша на следующем рекордсмене больше, чем на нынешнем. Интуитивно ясно, что надо ждать, пока впервые не появится рекордсмен b_k с таким k, что q_k / P_{k ¥} меньше 1. Именно на нем и нужно останавливаться. Все предыдущие рекордсмены имеют меньшую вероятность быть последним, а других рекордсменов с большой вероятностью не будет.

При больших N и k отношение q_k / P_{k ¥} = ln (N / k), следовательно, впервые станет меньше 1 при k» N / e.

n Оптимальная стратегия, при больших N состоит в том, что нужно пропустить приблизительно N/e = N/2,71 чисел, а затем выбрать то число, которое больше всех предыдущих. При малых N нужно пропустить kN чисел, а затем выбрать первое число, большее предыдущих, где kN – наименьшее решение неравенства 1/kN + 1/kN + 1 + … + 1/N<1.

Так, при N = 5 нужно будет пропустить три первых числа; при N = 10 оптимальная стратегия состоит в выборе наибольшего после четырех пропущенных.

Можно подсчитать вероятность выигрыша при использовании оптимальной стратегии. Оказывается, при больших N эта вероятность стремится к 1/ e = 0,37.

Задача о разборчивой невесте приводит к отысканию оптимального момента остановки марковской цепи. В задаче о невесте эта цепь – последовательность номеров рекордсменов, и наша задача свелась к такому выбору правила остановки t, чтобы с наибольшей вероятностью остановиться в момент, непосредственно предшествующий скачку в ¥. Из состояния k совершается скачок в ¥ с вероятностью k / N. Поэтому вероятность успеха при стратегии t равна

Таким образом, задача о разборчивой невесте эквивалентна выбору такого правила остановки t для цепи r ₀, r ₁,..., r_n,..., которое бы максимизировало бы М r _t.

Общую задачу об оптимальной остановке марковской цепи x ₀, x ₁,..., x_n,... можно сформулировать так. Пусть есть две функции f (x) и g (x) на состояниях цепи. Требуется выбрать такой марковский момент t, чтобы

приняло бы максимальное значение.

Пример 7.1

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

Решение.

Пусть X_k = + 1, если в результате k -го бросания выпал герб, и X_k = –1, если в результате k -го бросания выпала решка, тогда выигрыш, накопившийся за n бросаний .

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

Выберем в качестве состояния системы общий накопленный к данному моменту выигрыш. Если мы находимся в состоянии i, то есть если наш выигрыш к данному моменту составляет i, то независимо от того, сколько игр нам пришлось сыграть, чтобы накопить эту сумму, вероятность перехода в состояние i + 1 есть ½ и в состоянии i –1 – тоже ½.

Таким образом

Начальное состояние есть i ₀ = 0. Платеж, если мы останавливаемся в состоянии i, – это выигрыш к данному моменту: F (i) = i. Вступительного взноса нет f (i) = 0; состояний с вынужденной остановкой или продолжением также нет.

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

Пример 7.2

Задача о стоянках. Предположим, что мы едем куда–то на автомобиле, и что до места нашего назначения будет еще N стоянок. В поле зрения попадает каждый раз только одна стоянка. Естественно, что если стоянка занята, то мы не можем на ней остановиться; если же стоянка свободна и мы поставим на ней автомобиль, то штраф, или убыток – это то расстояние, которое нам придется пройти до места назначения пешком.

Решение.

В последовательности независимых случайных величин X _{– N}, X _{– N + 1}, …, X ₀, X ₁, … все случайные величины принимают значение 0 или 1 с одной и той же вероятностью P (X_k = 0) = p; P (X_k = 1) = 1– p.

Мы может остановиться на X_k, только в том случае, если X_k = 0, но если X_k = 0 и мы действительно останавливаемся, то мы платим штраф | k |.

Возьмем в качестве состояний пары чисел (i, k), где i пробегает значения – N, – N + 1, …, 0, 1, …, а k принимает только значения 0 и 1. Содержательно это означает, что i измеряет расстояние от данной стоянки до пункта назначения, а k отмечает, свободна данная стоянка или нет. Переход из (i, k) в (i + 1, 0) осуществляется с вероятностью p, а переход в (i + 1, 1) – с вероятностью 1–р.

В примере есть состояния с вынужденным продолжением (i, 1), где i = – N, – N + 1, …. Платеж задается формулой F (i, 0) = –| i |, где минус показывает, что платеж – величина, противоположная штрафу. Вступительный взнос равен нулю, а в качестве начального состояния снова берется (– N –1, 0).

Контрольные вопросы

Задание 7.1

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

I гр. II гр. III гр. IV гр. V гр.

1 5 8 12

3 2 3 9

2 4 7 20

1 4