Транзитивное замыкание. Поиск кратчайшего пути на графе

 

Пусть задан граф G = (V, E), и нас интересует, какие вершины связаны между собой, не только напрямую, но и через посредство других вершин. Чтобы ответить на этот вопрос, воспользуемся матрицей смежности.

                  

 

 

Рис. 3.5. G * — транзитивное замыкание графа G

 

Поиск кратчайшего пути

 

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

Алгоритм поиска кратчайшего пути следующий.

Пусть путь ищется между вершинами s (начало) и f (конец). Мы начинаем проход из вершины s и просматриваем граф в ширину, помечая вершины значениями их расстояний от s. Процесс заканчивается, когда вершина f помечена значением ее расстояния от s и эта метка далее не меняется. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а некоторые — временные.

Если учесть, что в начале алгоритма вершине s присваивается окончательная метка 0 (нулевое расстояние до самой себя), а каждой из остальных вершин присваивается метка ¥, то на каждом шаге алгоритма одной из вершин присваивается окончательная метка и поиск продолжается дальше.     

Рис. 3.6. Простой взвешенный граф

 

Как видно из нижнего рисунка граф G из b в g имеет три кратчайших пути, длины которых равны 12. Это путь b, c, e, d, g; b, c, a, d, g и b, c, d, g.

На каждом шаге метки меняются следующим образом:

1. Каждой вершине j, не имеющей окончательной метки, присваивается новая временная метка с учетом расстояния от s до j.

2. Находится наименьшая из временных меток, она и становится окончательной меткой своей вершины. В случае равенства выбирается любая из них. Процесс продолжается до тех пор, пока вершине f не присваивается окончательная метка.

 

 

4. Генерирование случайных последовательностей

Генерирование равномерно распределенных случайных чисел

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

Джон фон Нейман

 

Числа, которые выбираются случайным образом, находят множество полезных применений в

· моделировании. Это позволяет сделать модели похожими на реальные явления;

· выборочном методе. Часто невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать «типичным поведением»;

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

· компьютерном программировании. Случайные числа являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов;

· принятии решений;

· эстетике;

· развлечениях.

 

Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным [8].

 Джон фон Нейман первым предложил в 1946 г. идею возвести в квадрат предыдущее случайное число и выделить средние цифры. Например, необходимо получить 10 -значное число, предыдущее равнялось 5772156649. Возводим в квадрат и получаем

 

33317792380594909200.

 

Значит, следующим числом будет 7923805949. Претензии к такому подходу касаются вопроса: как может быть случайной последовательность, генерируемая таким образом, если каждое число полностью определяется предыдущим? Ответ состоит в том, что эта последовательность не случайна, но кажется такой. Последовательности, генерируемые детерминистическим путем, таким как этот, называются псевдослучайными или квази- случайными.

Метод середины квадратов фактически является сравнительно бедным источником случайных чисел. Опасность состоит в коротком цикле (периоде) повторяющихся элементов. Рассмотрим методы генерирования последовательности случайных дробей [8], т.е. случайных действительных чисел U_n, равномерно распределенных между нулем и единицей. Будем генерировать целое число Х _n между нулем и некоторым числом U, тогда дробь

U_n = Х _n / m

будет принадлежать [0,1]. Обычно m выбирают равным размеру слова компьютера. Обозначим m = b^e, где b — основание системы счисления, используемой ЭВМ, а e — число разрядов машины. Поэтому Х _n можно по традиции рассматривать как целое число, занимающее все компьютерное слово с точкой в правом конце слова, а U_n — как содержание того же слова с точкой в левом конце слова.

 

Линейный конгруэнтный метод

Выберем четыре числа [5]:

m — модуль, m > 0;

a — множитель, 0 £ a < m;

c — приращение, 0 £ с < m;

Х₀ — начальное значение, 0 £ Х₀ < m.

Последовательность случайных чисел {Х _n } можно получить, полагая

 

Х_n+1 = (a Х_n + c) mod m, n ³ 0                       (4.1)

 

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для m = 10 и Х₀ = a = c = 7 получим последовательность

 

                                7, 6, 9, 0, 7, 6, 9, 0, …

 

В примере отражен факт, что конгруэнтная последовательность всегда образует петли, т.е. обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство является общим для всех последовательностей вида X_{n +1} = f (X_n), где f — функция, преобразующая конечное множество само в себя. Повторяющиеся циклы называют периодами. Задача генерации случайных последовательностей состоит в использовании относительно длинного периода, что связано с выбором довольно большого m, так как период не может иметь больше m элементов. Другой фактор — скорость генерирования. При выборе множителя а следует принимать во внимание выводы следующей теоремы.

Теорема А. Линейная конгруэнтная последовательность, определенная числами m, a, c и X ₀, имеет период длиной m тогда и только тогда, когда:

· числа с и m взаимно простые;

· b = a - 1 кратно p для каждого простого p, являющегося делителем m;

· b кратно 4, если m кратно 4.

 

Пример. Для m = 120 назначить а и построить последовательность случайных чисел в интервале [0,1].

Решение. Выберем с = 7, a = 5, тогда при x ₀ = 1 получим следующие числа: X ₁= 12, X ₂ = 67, X ₃= 102, … Далее генерируем u ₀ = 1/120, u ₁ = 12/120, u ₂ = 67/120, u ₃ = 102/120, …

В связи с довольно простым получением случайных чисел возникает такая общепринятая ошибочная идея — достаточно взять хороший генератор случайных чисел и немного его модифицировать для того, чтобы получить «еще более случайную» последовательность. Часто это не так. Например, известно, что формула (4.1) позволяет получить более или менее хорошие случайные числа. Может ли последовательность, полученная из

 

X_{n +1} = ((a X_n) mod (m + 1) + c) mod m

быть еще более случайной? Ответ: новая последовательность является менее случайной с большей долей вероятности, т.е. мы попадаем в область генераторов типа X_{n +1}= f (X_n) с выбранной на удачу функцией f. Но известно, что эти последовательности, вероятно, ведут себя намного хуже, чем последовательности, полученные при использовании более регулярных функций (4.1). Отметим, что период линейной конгруэнтной последовательности довольно длинный; когда m приблизительно равно длине слова компьютера, обычно получаются периоды порядка 10⁹ или больше и в типичных вычислениях используется лишь маленькая часть последовательности.

Рассмотрим аддитивный генератор, предложенный Дж. Ж. Митчелом (G. J. Mitchell) и Д.Ф. Муром (D.P. Moore):

 

X_n= (X_n-24 + X_n-55) mod m n ³ 55,                        (4.2)

 

где m — четное число, числа 24 и 55 — специальные числа, выбранные для того, чтобы определить такую последовательность, младшие значащие двоичные разряды (X_nmod 2) которой имеют длину периода 2⁵⁵ – 1. Далее рассмотрим реализацию этой последовательности с помощью циклической таблицы [5].

Алгоритм В. (Аддитивный генератор чисел). В ячейки памяти Y [1], Y [2], …, Y [55] записано множество значений X ₅₄, X ₅₃, …, X ₀ соответственно; j вначале равно 24, k равно 55.

При реализации этого алгоритма на выходе последовательно получаем числа X ₅₅, X ₅₆, …

В1. [Суммирование] (Если на выходе мы оказываемся в точке X_n, то Y [ j ] равно
X_{n -24}, а Y [ k ] равно X_{n -55}). Y [ k ] (Y [ k ] + Y [ j ]) mod 2 ^e.

В2. [Продвижение] Уменьшим j и k на 1. Если j = 0, то присвоим j 24, иначе, если k = 0, присвоить k 55.

Числа 24 и 55 в выражении (4.2) называются запаздыванием, а числа X_n, определенные в (4.2) — последовательностью Фибоначчи с запаздыванием.

Вместо рассмотрения исключительно аддитивных или исключительно мультипликативных последовательностей можно построить достаточно хороший генератор случайных чисел, используя всевозможные линейные комбинации X_{n -1}, …, X_{n - k} для малых k. В этом случае наилучший результат получается, когда модуль m является большим простым числом; например, m может быть выбрано так, чтобы оно было наибольшим простым числом, которое можно записать одним компьютерным словом. Формула для генерации может быть выбрана такой:

 

X_n= (a ₁ X_{n -1} + … + a_k X_{n - k}) mod p                            (4.3)

 

с периодом p^k – 1. Здесь X ₀, X ₁, …, X_{k -1} могут быть выбранны произвольно, но не равные нулю одновременно.

Обратимся к процессу генерирования случайных чисел «0» и «1» по формуле (4.3). Зададим произвольно ненулевое двоичное слово (1 0 1 1), то есть X ₁ = 1, X ₂ = 0, X ₃ = 1, X ₄ = 1, k примем равным 4, а p равным 2. Зададим также произвольно коэффициенты а₁, а₂, а₃, а₄ двоичным словом (0 0 1 1), то есть а₁ = 0, а₂ = 0, а₃ = 1, а₄ = 1. Перепишем (4.3) с учетом введенных величин, получим

 

X_n= (a ₁ × X_{n -1} + a ₂ × X_{n -2} + a ₃ × X_{n -3} + a ₄ × X_{n -4}) mod 2

                             X_n= (0 × X_{n -1} + 0 × X_{n -2} + 1 × X_{n -3} + 1 × X_{n -4}) mod 2

                          X_n= (X_{n -3} + X_{n -4}) mod 2

Откуда следует, что X ₅ = (X ₂ + X ₁) mod 2 = 1

X₆= (X₃ + X₂) mod 2 = 1;        X₇= (X₄ + X₃) mod 2 = 0;

X₈= (X₅ + X₄) mod 2 = 0;        X₉= (X₆ + X₅) mod 2 = 0;

X₁₀= (X₇ + X₆) mod 2 = 1;       X₁₁= (X₈ + X₇) mod 2 = 0;

X ₁₂ = (X ₉ + X ₈) mod 2 = 0; … и т.д.

 

То есть сгенерированные числа (коды) имеют значения:

 

1011 (начальное число); 1100; 0100; 1101; 0111; 1000; 1001 …

 

Период, т.е. число шагов, через которое начинается повтор, равняется 2⁴ – 1 = 15.

   Для генерирования случайных чисел предложено множество других схем. Наиболее интересным из альтернативных методов является обратная конгруэнтная последовательность, предложенная Эйченауэром (Eichenauer) и Лехном (Lehn) [5]:

 

                                    (4.4)

 

Здесь p — простое число, X_n принимает значения из множества {0, 1, …, p-1, …¥}, а обращение определено как 0^-1 = ¥, ¥^-1 = 0. X ^-1 × X º 1 по модулю p.

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

Допустим, имеются последовательности X ₀, X ₁, … и Y ₀, Y ₁, … случайных чисел, лежащих между 0 и m – 1 и предпочтительно сгенерированных двумя различными методами. Тогда можно использовать одну случайную последовательность для изменения порядка элементов другой. Рассмотрим алгоритм рандомизации перемешиванием.

 

Алгоритм М (рандомизации перемешиванием)

 

Если заданы методы генерирования двух последовательностей { X_n }и { Y_n }, этот алгоритм будет последовательно генерировать элементы «значительно более случайной» последовательности. Воспользуемся вспомогательной таблицей V [0], V [1], …, V [ k -1], где k — некоторое число, для удобства обычно выбираемое приблизительно равным 100. Вначале V -таблица заполняется первыми k значениями последовательности X.

М1. [Генерирование X, Y ]. Положим X и Y равными следующим членам последовательности { X_n } и { Y_n } соответственно.

М2. [Выбор j ]. Присвоим j [ k × Y / m ], где m — модуль, используемый в последовательности {Y _n }, т.е. j — случайная величина, определяемая Y, 0 £ j < k.

M3. [Замена]. Выведем V [ j ], а затем присвоим V [ j ] X.

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

 

Z_n= (X_n - Y_n) mod m,                          (4.5)

 

где 0 £ X_n < m и 0 £ Y_n < m ¢ £ m.

Простейшим путем улучшения случайности при с = 0 является использование только каждого j -го элемента для некоторого малого j. Но лучшим способом, возможно, еще более простым, является применение (4.1) для получения скажем массива из 500 случайных чисел и использование только первых 55 чисел. После этого таким же методом генерируются следующие 55 чисел и т.д.