Алгоритм обнаружения цикла Флойда | Определение начальной точки цикла

Question

Я ищу помощь в понимании алгоритма обнаружения цикла Флойда. Я прошел через объяснение в Википедии (http://en.wikipedia.org/wiki/cycle_detection#tortoise_and_hare)

Я вижу, как алгоритм обнаруживает цикл во время O (n). Тем не менее, я не могу визуализировать тот факт, что после того, как указатели черепахи и зайца встретятся в первый раз, начало цикла можно определить, перемещая указатель черепахи назад, а затем перемещая и черепаху, и затшет один шаг за раз. Точка, где они впервые встречаются, - это начало цикла.

Может ли кто -нибудь помочь, предоставив объяснение, надеюсь, отличается от того, что в Википедии, так как я не могу понять/визуализировать его?

Answer 1

Я нашел ответ на Stackoverflow. Спасибо, если кто -то задумался об этом для меня. А для тех, кто мне нравится, хотели объяснения, пожалуйста, обратитесь к: https://stackoverflow.com/questions/3952805/proof-of detecting-the-start-fycle-in-licked-list Выбранный ответ на вопрос, объясняет это!

Answer 2

Вы можете ссылаться на "Обнаружение начала петли в одиночном списке", вот отрывка:

Расстояние пройдет мимо slowPointer до встречи $ = x+y $

Расстояние пройдет мимо fastPointer до встречи $ = (x + y + z) + y $ = x + 2y + z

С fastPointer путешествует с двойной скорость slowPointer, а также время постоянно для обоих, когда достичь точки встречи. Таким образом, используя простую скорость, время и расстояние (slowPointer прошел половину расстояния):

begin {align*} 2* operatorname {dist} ( text {slowpointer}) & = operatornam 2x+2y & = x+2y+z x & = z end {Align*}

Следовательно, движусь slowPointer Для начала связанного списка и создания обоих slowPointer а также fastPointer перемещать по одному узлу за раз, У них обоих есть одно расстояние, чтобы покрыть.

Они достигнут в той точке, где петля начинается в связанном списке.

Answer 3

Я видел принятый ответ в качестве доказательства в другом месте. Однако, хотя его легко в Grok, это неверно. Что доказывает

$ x = z $ (что, очевидно, неверно, и диаграмма просто делает это правдоподобным из -за того, как она нарисована).

Вы действительно хотите доказать (используя те же переменные, как описано на диаграмме в принятом ответе выше):

$ z = x mod (y + z) $

$ (y + z) $ - длина петли, $ l $

Итак, мы хотим доказать:

$ z = x mod l $

Или что Z совпадает с x (модуля)

Следующее доказательство имеет для меня больше смысла:

Точка встречи, $ m = x + y $

$ 2 (x + y) = m + kl $, где $ k $ является некоторой постоянной. По сути, расстояние, пройденное по быстрому указателю, составляет $ x + y $ плюс несколько длины петли, $ l $

$ x + y = kl $

$ x = kl - y $

Приведенное выше уравнение доказывает, что $ x $ совпадает с некоторой кратной длиной цикла, $ l $ минус $ y $. Таким образом, если быстрый указатель начинается с точки встречи, $ M $ или по цене $ x + y $, то он окажется в начале цикла.