аисд. Т. е путь начинающийся и заканчивающимся на одной и той же вершине называется циклом. Обнаружение цикла или нахождение цикла это алгоритмическая задача
 Скачать 15.59 Kb.
|
|
Цикл – это путь, в котором первая и последняя вершина графа совпадают. Т.е. путь начинающийся и заканчивающимся на одной и той же вершине называется циклом. Обнаружение цикла или нахождение цикла - это алгоритмическая задача нахождения цикла в последовательности повторяющихся значений функции. Для любой функции, которая отображает конечное множество в себя, и любого начального значения в конечном множестве, последовательность итерационных значений функции в конечном итоге должно использоваться одно и то же значение дважды: должна существовать некоторая пара различных индексов i и j, таких, что x i = x j . Как только это произойдет, последовательность должна периодически продолжаться, повторяя ту же последовательность значений от xi до xj − 1. Обнаружение цикла - это проблема нахождения i и j. На данный момент известно несколько алгоритмов быстрого поиска циклов с небольшим объемом памяти. Алгоритм Флойда "черепаха и заяц" перемещает два указателя с разной скоростью по последовательности значений, пока они оба не укажут на равные значения. Или алгоритм Брента основан на идее экспоненциального поиска. И алгоритмы Флойда, и Брента используют только постоянное количество ячеек памяти и выполняют количество вычислений функций, пропорциональное расстоянию от начала последовательности до первого повторения. Где используется? Тестирование качества генераторов псевдослучайных чисел и криптографических хеш-функций, вычислительных алгоритмов теории чисел, обнаружение бесконечных циклов в компьютерных программах и периодических конфигураций в клеточных автоматах. Алгоритм Флойда Алгоритм поиска цикла Флойда - это алгоритм указателя, который использует только два указателя, которые перемещаются по последовательности с разной скоростью. Это также называется «черепаху и зайца алгоритм», имея в виду Эзопа басни Черепаха и Заяц . Ключевая идея алгоритма заключается в следующем. Если цикл существует, то для любых целых чисел i ≥ μ и k ≥ 0, xi = xi + kλ, где λ - длина цикла, который нужно найти, μ - индекс первого элемента цикла, а k - целое число, представляющее число циклов. Исходя из этого, затем можно показать, что i = kλ ≥ μ для некоторого k тогда и только тогда, когда x i = x 2 i (если x i = x 2 i в цикле, то существует некоторое k такое, что 2 i = i + kλ, что подразумевает, что i = kλ; и если есть некоторые i и k такие, что i = kλ, то 2i = i + kλ и x2i = xi + kλ). Таким образом, алгоритму нужно только проверить повторяющиеся значения этой специальной формы, одно из которых в два раза дальше от начала последовательности, чем другое, чтобы найти период ν повторения, кратный λ. Как только ν найдено, алгоритм восстанавливает последовательность с самого начала, чтобы найти первое повторяющееся значение x μ в последовательности, используя тот факт, что λ делит ν и, следовательно, что x μ = x μ + v. Наконец, как только значение μ известно, тривиально найти длину λ кратчайшего повторяющегося цикла путем поиска первой позиции μ + λ, для которой x μ + λ = x μ. Алгоритм Брента Ричард П. Брент описал альтернативный алгоритм определения цикла, который, как и алгоритм черепахи и зайца, требует только двух указателей на последовательность. Однако он основан на другом принципе: поиск наименьшей степени двойки 2 i, которая больше, чем λ и μ . Для i = 0, 1, 2, ... алгоритм сравнивает x 2 i -1 с каждым последующим значением последовательности до следующей степени двойки и останавливается, когда находит совпадение. Он имеет два преимущества по сравнению с алгоритмом черепахи и зайца: он находит правильную длину цикла λ напрямую, вместо того, чтобы искать его на следующем этапе, и его шаги включают только одно вычисление f, а не три. |