https://en.wikipedia.org/wiki/Cycle_detection

Сверху ссылка на алгоритм.

alt text

Как он работает:

В начале графа (слева), запускаем 2 животных:

1) черепаха движется по со скоростью 1 вершина

2) заяц движется со скоростью 2 вершины

в итоге они встретятся в точке М, затем мы поставим черепаху в начало, и оба животных будут двигаться со скоростью 1 вершина, пока не дойдут до начала цикла, потому что $%x mod L = z$%.

Я видел доказательство того, что это работает, звучит оно так:

Надо доказать, что $$x mod L = z$$.

Т.к. $$L = (x + y)$$ нужно доказать, что $$x mod (x + y) = z$$.

$$2(x + y) = M + kL, т.к. M = x + y, то$$

$$2(x+y) = x+y + (kL)$$

$$x+y = k*L$$

$$x = k*L - y$$

$$x mod L = -y mod L$$

$$x mod L = z$$

Но мне интересно 1) как доказать, что заяц и черепаха обязательно встретятся в точке М. 2) Как доказать, что этот алгоритм работает за линейное время?

задан 8 Мар 2:55

изменен 9 Мар 0:34

10|600 символов нужно символов осталось
1

Предположим, что последовательность периодична, начиная с некоторого номера, то есть существуют натуральное $%T$% и некоторое $%i_0$% такие, что $%x_i=x_{i+T}$% для всех $%i\ge i_0$%. Отсюда следует, что $%x_i=x_{i+Tk}$% для всех $%i\ge i_0$% и любого натурального $%k$%. Положим $%i=Ti_0\ge i_0$%. Тогда $%x_i=x_{i+Ti_0}=x_{2i}$%. Отсюда следует, что индекс $%i$% с требуемым свойством существует, и алгоритм находит наименьшее такое $%i\ge1$%.

Оценим сверху величину $%i$%. Пусть $%i_0$% -- длина непериодической части, $%T$% -- длина цикла. Положим $%i=i_0+d$%. Тогда $%2i=i_0+(i_0+2d)$%, и совпадение значений $%x_i=x_{2i}$% равносильно тому, что $%i_0+2d$% сравнимо с $%d$% по модулю $%T$%, то есть $%i_0+d$% кратно $%T$%.

Наименьшее натуральное $%d$% с таким свойством не больше $%T$% (в противном случае его можно уменьшить на $%T$%). Тем самым, $%i\le i_0+T$%, то есть значение $%i$% будет найдено не позднее прохождения "медленной" точкой непериодической части и одного цикла.

ссылка

отвечен 8 Мар 4:14

изменен 8 Мар 12:47

А можно просто сказать, что т.к. заяц идет с шагом 2, а черепаха с шагом 1, то за каждый шаг алгоритма, заяц ближе к черепахе на 1 шаг. Поэтому он ее догонит за d шагов, где d - расстояние между ними на тот момент, когда черепаха вошла в цикл. И т.к. это то же самое, что заставить черепаху стоять на месте, а зайца идти со скоростью = 1, то он ее обязательно не пропустит?

(8 Мар 4:34) pavel1076

Вы говорите в первом абзаце i = Ti0, может вы имели в виду i = Tk? Просто как-то непонятно что такое i0 тогда.

(8 Мар 5:14) pavel1076

Потом вы говорите, что i0+2d кратно T, может вы имели в виду, что i0+d кратно T? потому что мы за i0+d шагов зашли в цикл, и еще за столько же шагов вернулись на то же место.

(8 Мар 5:17) pavel1076
1

Извините, я просто запутался в ваших нотациях немного

(8 Мар 5:18) pavel1076

@pavel1076: с обозначениями тут всё в порядке, но Ваше соображение позволяет всё то же самое доказать без формул. В самом деле, через i0 шагов черепаха входит в цикл, а заяц уже там, и он начинает к ней приближаться по направлению движения на 1 шаг. Поэтому они встретятся, причём не позднее шага с номером i0+T.

(8 Мар 6:01) falcao

@falcao а почему i0+2d кратно Т? Я тут тоже запутался немного

(8 Мар 6:15) pavel1076
1

просто когда черепаха прошла i0+d шагов, заяц прошел 2*(i0+d) шагов, и они встретились в одной точке, получается что i0+d кратно T, а не i0+2d?

(8 Мар 6:33) pavel1076

@pavel1076: да, Вы правы. Черепаха прошла i0+d шагов, из них d по циклу. Заяц прошёл 2i0+2d, из них i0+2d по циклу. Поэтому i0+2d сравнимо с d по модулю T, то есть i0+d кратно T. Я сейчас у себя исправлю. Но рассуждение от этого не зависит.

(8 Мар 12:46) falcao

спасибо за пояснения

(8 Мар 21:54) pavel1076
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×237

задан
8 Мар 2:55

показан
108 раз

обновлен
9 Мар 0:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru