почти все члены взаимно уничтожились. Это дает

Z.(n)-Z.(l) = 15(tt-1)+18 (M-i)=

= 15(н-1) + 8

i = 2 i = l

8nM - 8M-4n+lln~7.

Таким образом, L{n)=8nM-M-4n-f lln+7.

В предположении, что. последняя вершина W появляется с одинаковой вероятностью на любой итерации, нижняя граница среднего числа выполняемых операторов в подпрограмме DIJKST определяется выражением

LBD = X(«) =

п = \

Л1(М-1) + 7(М-1) =

= 4M-/W-i-УИ+-/W+у М+ 7 = -+1М+ 7.

Заметим, что нижняя граница ожидаемой трудоемкости алгоритма все же составляет О(УИ). Удивляет ли это вас? Как вы полагаете, что бы мы получили, если бы вычислили верхнюю границу?

и 1 1 11

Рис. 6.2,5. Найдите кратчайший путь от U до V. {Указание: его длина 12.

Упражнения 6.2

6.2.1. Закончите выполнение алгоритма Дейкстры на сети с рис. 6.2.1 и найдите кратчайший путь от Лексингтона к Дэнвиллу.

6.2.2. Найдите кратчайший путь от Лексингтона к Дэнвиллу в смысле затраченного времени. Вы получите путь, не совпадающий с полученным в упр. 6.2.1.

6.2.3. Найдите кратчайший путь от U до V в сети, показанной на рис. 6.2.5.

6.2.4. Могут ли существовать два различных дерева кратчайших путей в сети?

6,3. Вероятностные алгоритмы Извлечение выборки

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

Один из наивных подходов состоит в том, чтобы выбирать записи с вероятностью M/N. Этот метод удобен тем, что каждый предмет принимается или отвергается в момент его прохождения, и можно делать только один проход вдоль набора предметов. К сожалению, такая процедура не гарантирует, что будет выбрано точно М предметов.

Чтобы убедиться в этом, определим случайные переменные для . . ., N:

1 1, если выбран предмет i; \ О, если предмет i не выбран. Вероятностная мера для каждого Xj равна

Р(Х, = 0)=1-; P(X,= l) = f,

Xi - независимые, одинаково распределенные случайные переменные. Каждая имеет среднее M/N и дисперсию (M/N)-[l-{MIN)]. Случайная переменная

ХХг+ХЛ. . .-Хг,

означает число предметов, извлеченных в некотором испытании. Тогда

var [X] = var [X J + ... + var [Х] = (1 = TW (1 - -f) .

Таким образом, только среднее число выбранных предметов равно М, а большая дисперсия приводит к тому, что действительное число выб-

£ [X] = £ [X,]+..-+£ [Х] = 4 = :

ранных предметов в некотором испытании может оказаты;я существенно больше или меньше, чем М.

Другой интуитивный подход при выборе М чисел из N состоит в том, чтобы многократно генерировать случайные целые числа до тех пор, пока не окажется М различных. Эту процедуру можно сформулировать в виде алгоритма следующим образом:

Algorithm TRYAGAIN (Еще одна попытка) для извлечения несмещенной выборки lMN чисел из множества 1,2, . . ., N. Выбранные числа будут помещены в массив SELECT (1), SELECT (2), . . ., SELECT (/W).

Шаг 0. [Инициализация) Set L ч- О (переменная L используется для записи текущего числа выбранных объектов); and пометить все целые числа 1, , . ., N как «невыбранные». Шаг 1. [цикл] Do through шаг 3 while KM od; and STOP.

Шаг 2. [Генерация случайного целого числа] Генерируется (с равномерным распределением) случайное число К, между 1 и N.

Шаг 3. [Было ли выбрано Ю\ И К помечено «не выбрано» then set L-L+l; SELECT (L) i(; and пометить К «выбрано» fi.

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

Пусть Pi= {N-L)/N - вероятность генерации невыбранного числа из 1, при условии, что уже выбрано L целых чисел. Пусть 1-Pi=LlN - вероятность генерации одного из L ранее выбранных чисел.

Если Xi - случайная переменная, равная количеству целых чисел, сгенерированных прежде, чем появилось невыбранное число, при условии, что уже было выбрано L чисел, то

P{X,k) = qtp,.

Таким образом, Х, имеет геометрическое распределение и

E{X,)=kqrp, = l-

(См. упр. 2.4.31.)

Например, если нужно выбрать 97 целых чисел из 100 с помощью алгоритма TRYAGAIN и уже выбрано 96, потребуется сгенерировать в среднем еще 100/(100-96)=25 чисел прежде, чем будет получено одно из оставшихся трех чисел.

Если Т - случайная переменная, равная общему количеству це-