Floyd '의주기 감지 알고리즘 | 주기의 시작점 결정

“단일 연결 목록에서 루프 시작 감지” a를 참조 할 수 있습니다. > 발췌 :

만남 전에 slowPointer까지 이동 한 거리 $ = x + y $

만남 전 fastPointer까지 이동 한 거리 $ = (x + y + z) + y = x + 2y + z $

fastPointer가 slowPointer의 속도와 시간이 일정합니다. 모두 회의 지점에 도달했을 때. 따라서 간단한 속도, 시간 및 거리 관계를 사용하여 (slowPointer 이동 거리의 절반) :

\ begin {align *} 2 * \ operatorname {dist} (\ text {slowPointer}) & = \ operatorname {dist} (\ text {fastPointer}) \\ 2 (x + y) & = x + 2y + z \\ 2x + 2y & = x + 2y + z \\ x & = z \ end {align *}

따라서 slowPointer를 연결 목록의 시작으로 이동하고 둘 다 slowPointer 및 fastPointer는 한 번에 하나의 노드를 이동하고 둘 다 동일한 거리를가집니다. .

연결된 목록에서 루프가 시작되는 지점에 도달합니다.

댓글

• 여기에서 한 번의 회전 후에 만날 것이라고 가정했습니다. 특정 아니오 후에 만날 수있는 경우 (주기가 작은 경우)가있을 수 있습니다. 회전.
• @JotWaraich 이미지가 모든 경우를 대표하는 것은 아닙니다. 그러나 논리는 여전히 유지됩니다.
• 이것은 전체 인터넷에서이 알고리즘에 대한 가장 직접적인 대답입니다.
• 나는 ‘ 잘 모르겠습니다. 이 증거가 맞다면. 느린 포인터가 이동 한 거리는 (x + (y + z) * α + y)이고 빠른 포인터가 이동하는 거리는 (x + (y + z) * β + y) 여야합니다. 여기서 α와 β는 숫자입니다. 느리고 빠른 포인터가 통과하는 사이클 수. 이 추가로 인해 증명이 실패한 것 같습니다.
• @ hashcode55 예 동의합니다. 이것은 명확하지 않습니다.

허용 된 답변을 다른 곳에서도 증거로 보았습니다. 그러나 그 로크하기 쉽지만 잘못된 것입니다. 그것이 증명하는 것은

$ x = z $ (분명히 틀린 것이며, 다이어그램은 스케치 된 방식 때문에 그럴듯하게 보이게합니다)

당신이 정말로 원하는 것입니다. 증명하는 것은 (위의 허용 된 답변의 다이어그램에 설명 된 것과 동일한 변수 사용) :

$ z = x \ mod \ (y + z) $

$ (y + z) $는 루프 길이, $ L $

그래서 우리가 증명하고 싶은 것은 :

$ z = x \ mod \ L $

또는 z가 x와 합동 (모듈로 L)

다음 증명이 더 의미가 있습니다.

만남 지점, $ M = x + y $

$ 2 (x + y) = M + kL $, 여기서 $ k $는 상수입니다.기본적으로 빠른 포인터가 이동하는 거리는 $ x + y $에 루프 길이의 배수를 더한 값입니다. $ L $

$ x + y = kL $

$ x = kL- y $

위 방정식은 $ x $가 루프 길이의 배수 인 $ L $에서 $ y $를 뺀 값과 동일 함을 증명합니다. 따라서 빠른 포인터가 회의 지점, $ M $ 또는 $ x + y $에서 시작하면 루프의 시작 부분에서 끝납니다.

Comments

• ‘이 답변이 과소 평가 된 이유를 모르겠습니다. 이것은 가장 공식적인 증거인 것 같습니다.
• @ I8Again x = z가 틀리면 빠른 포인터를 시작점으로 다시 이동시키는 논리 & 둘 다 이동 빠른 & 루프의 시작을 찾는 느린 포인터가 작동하지 않습니다. ‘ x = z가 의미하는 바를 이해하지 못합니다. 그게 어떻게 잘못되었는지 설명해주세요.
• @divine x = z는 둘 다 동등하다는 것을 의미하기 때문에 잘못되었지만 매우 긴 ” tail”(큰 x) 및 매우 작은 원 (작은 z). 모듈로를 사용하여 공식적으로 정확합니다. x % L == z, 즉 다른 하나와 결합하기 위해 기다리는 원을 이동하는 포인터가 원하는만큼 많은 루프를 만들 수 있다는 것을 증명하고 싶습니다. 마지막 단계 (예 : 루프 후 나머지)는 서클 자체의 시작으로 이어집니다.
• 이거 좋습니다 !!
• 아직도하지 않았던 분들을 위해 ‘ x = k * L-y가 z = x mod L로 이어지는 이유를 이해하지 못합니다. From x = k * L-y — > x = (k-1) * L + L-y 그러면 이제 L-y가 z가되어야한다고 말할 수 있습니다. 이제 x = (k-1) * L + z

루프 시작 전 span class = “math-container”> $ l $ 요소와 루프의 $ n $ 요소. 그리고 $ e_l $ 는 연결 목록을 탐색 할 때 나타나는 루프의 첫 번째 요소입니다. $ e보다 앞서 ” 요소가 $ x $ 단계라고 말할 때 $ “, 즉, $ x $ 단계를 거쳐 해당 요소에 도달 할 수 있습니다. = “math-container”> $ e $ .

이제 Tr (거북이)가 $ e_l $ 에 도달하면 $ l $ 반복, 예를 들어 Hr (Hare)는 pan class = “보다 $ x $ 단계 앞서 있습니다. math-container “> $ e_l $ . Hr은 그때까지 총 $ 2l $ 걸음을 걸었으므로 (루프 이전에 $ l $ 걸음), 따라서 :

$ x = l \ bmod n $ .

향후 각 반복에서 Tr 및 Hr은 1 단계와 2 단계를 각각 수행하므로 각 반복은 ” 격차 “를 1 씩 증가시킵니다. 따라서 $ nx $ 추가 반복, 그 간격은 $ x + (nx) = n $ 가됩니다. 따라서 회의 요소 $ M $ 는 pan class = “math보다 $ nx $ 단계 앞서 있습니다. -container “> $ e_l $ . 즉, $ M $ 이후에 $ x $ 단계를 수행하면 다시 $ e_l $ . 우리의 목표는 $ e_l $ 를 찾는 것입니다.

따라서 에서 하나의 참조 Tr로 시작하면 $ M $ 및 링크 된 목록의 선두에있는 또 다른 참조 시간, $ l $ 반복 후 한 번에 한 단계 씩 진행 :

• 시간은 $ l $ 보다 앞서서 $ e_l $ .

• Tr은 $ (l \ bmod n) $ 단계입니다. $ M $ , 즉 $ x $ 보다 앞서 $ M $ , 이는 $ e_l $ 입니다.

따라서 $ e_l $ 인 것을 알고 있습니다.

이 도움말 참조 자세한 내용은. $ e_l $ 를 찾기 위해 약간 수정 된 방법을 찾을 수 있습니다.

stackoverflow에서 답을 찾았습니다. 누군가 나를 위해 이것을 찾고 있다면 감사합니다. 저와 같은 사람들은 설명을 원하시면 다음을 참조하십시오. https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list 질문에 대한 선택된 답변은 그것!

또한 상위 답변이 불완전하다고 생각합니다. 다른 설명도 좋지만 다른 설명도 있습니다. MOD가없는 버전은 동일한 것을 표시하기 때문에 일부 사람들에게는 더 쉬울 수 있습니다.

동일한 설정에서는 $ X \ ge 0 $ 가 루프 전 거리, $ N \ le \ text {size of list} $ 는 루프의 크기 (수량 $ y + z $ (사진에서)), 모임 지점은 루프에서 $ Y $ 입니다. 이 시점에서 $ X + Y \ le N $ 도 만들었습니다.

이제 느린 포인터가 이동합니다 $ X + Y + pN $ , 여기서 $ p $ 는 임의의 정수입니다. 그런 다음 빠른 포인터가 $ 2 (X + Y + pN) $ 를 이동했습니다.

이제 $ Y $ 에서 만난다고 주장합니다.

증명 :

$ Y $ 에서 만나는 경우 더 빠른 포인터는 더 느린 포인터보다 정확히 $ qN $ 더 많이 이동했습니다. 여기서 $ q $ 는 정수입니다. . 다음은 다음과 같습니다. $$ \ text {distance difference =} 2 (X + Y + pN)-(X + Y + pN) = X + Y + pN $$ . 하지만 $ Y $ 가 루프에서 임의의 만남 지점이되었으므로 간단히 $ X + Y = N을 선택할 수 있습니다. $ 는 $ X + Y \ le N $ 로 유지됩니다.

따라서 다음과 같은 결과가 있습니다. $$ X + Y + pN = N + pN = (p + 1) N = qN $$ $ p + 1 = q 인 경우 참 $ . 이제 $ p $ 및 $ q $ 모두 임의의 정수이므로 최소값 만 선택할 수 있습니다. 해당 $ p = 0, q = 1 $ , 이에 해당 : $$ \ text {느린 포인터로 이동 한 거리} = X + Y + pN = X + Y $$ 및 $$ \ text {빠른 포인터로 이동 한 거리} = (X + Y + pN) + qN = X + Y + N $$ 빠른 포인터가 느린 포인터를 처음 만났을 때 정확히 $ N $ 더 이동했습니다.

거북이와 토끼는 목록의 “상단”값으로 초기화되는 두 개의 포인터입니다. 루프의 각주기에서 토끼는 2 개씩 증가하는 반면 거북이는 1 개씩 증가합니다. 어느 시점에서 토끼가 토끼와 같으면 루프가 감지되었습니다. 토끼가 끝과 같으면 루프가 발견되지 않습니다.

이 게시물은 더 나은 라인별로 설명합니다.

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29