[algorithm] 사이클 링크 된 목록에서 사이클 시작 노드를 찾는 방법을 설명하십시오.
Tortoise와 Hare의 회의는 루프가 존재한다는 것을 이해하지만 토끼를 회의장에 유지하면서 거북이를 연결 목록의 시작 부분으로 이동 한 다음 한 번에 한 단계 씩 이동하면 사이클의 시작점에서 만나게됩니까?
답변
이것은 사이클 감지를위한 Floyd의 알고리즘입니다 . 알고리즘의 두 번째 단계에 대해 묻습니다. 사이클의 일부인 노드를 찾으면 사이클의 시작 을 어떻게 찾 습니까?
Floyd 알고리즘의 첫 번째 부분에서, 토끼는 거북이의 모든 단계마다 두 단계 씩 움직입니다. 거북이와 토끼가 만나면주기가 있고 만나는 지점이주기의 일부이지만 반드시주기의 첫 번째 노드는 아닙니다.
거북이와 토끼가 만나면 X i = X 2i가 되도록 가장 작은 i (거북이 걸음 수)를 발견했습니다 . mu가 X 0 에서 사이클 시작 까지의 단계 수를 나타내고 람다는 사이클 길이를 나타냅니다. 그런 다음 i = mu + a lambda 및 2i = mu + b lambda입니다. 여기서 a 및 b는 거북이와 토끼가 사이클을 몇 번이나 수행했는지 나타내는 정수입니다. 두 번째 방정식에서 첫 번째 방정식을 빼면 i = (ba) * lambda가되므로 i는 람다의 정수배입니다. 따라서 X i + mu = X mu 입니다. X i 는 거북이와 토끼의 만남의 장소를 나타냅니다. 거북이를 시작 노드 X로 다시 옮기면0 , 거북이와 토끼가 같은 속도로 계속되도록합니다. mu 추가 단계 후에 거북이가 X mu에 도달 하고 토끼가 X i + mu = X mu에 도달 하므로 두 번째 미팅 포인트는 시작의 시작을 나타냅니다. 주기.
답변
http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare 에서 제공되는 사이클 감지 알고리즘을 명확하게 설명하겠습니다 .
작동 원리
위의 다이어그램 에서처럼 주기로 목록의 시작을 가리키는 거북이와 토끼 (포인터 이름)를 보자.
한 번에 거북이를 한 단계 씩 움직이고 한 번에 두 단계 씩 토끼를 타면 결국에는 만나게된다는 가설을 세우십시오. 먼저이 가설이 사실임을 보여 드리겠습니다.
그림은주기가있는 목록을 보여줍니다. 주기는 길이이며 n처음에는 m주기에서 멀어집니다. 또한 미팅 포인트가 k사이클 시작과 거북이에서 멀어지고 거북이가 i총 걸음을 내딛을 때 토끼가 만나는 것으로 가정 해 봅시다 . 2i그때 까지는 총 걸음을 내딛었을 것 입니다.
다음 두 가지 조건이 충족되어야합니다.
1) i = m + p * n + k
2) 2i = m + q * n + k
첫 번째는 거북이가 i단계 를 움직이고이 단계에서 i먼저주기에 도달 한다고 말합니다 . 그런 다음 p양수에 대한 사이클 시간을 거 칩니다 p. 마지막으로 k토끼를 만날 때까지 더 많은 노드를 통과 합니다.
토끼도 마찬가지입니다. 2i단계를 이동 하고이 2i단계 에서 먼저주기에 도달합니다. 그런 다음 q양수에 대한 사이클 시간을 거 칩니다 q. 마지막으로 k거북이를 만날 때까지 더 많은 노드 로 넘어갑니다 .
토끼가 거북이 속도의 두 배로 이동함에 따라 회의 지점에 도달했을 때 시간이 일정합니다.
따라서 간단한 속도, 시간 및 거리 관계를 사용하면
2 ( m + p * n + k ) = m + q * n + k
=> 2m + 2pn + 2k = m + nq + k
=> m + k = ( q - 2p ) n
m, n, k, p, q 중에서 처음 두 가지는 주어진 목록의 속성입니다. 이 방정식을 참으로 만드는 k, q, p에 대해 적어도 하나의 값 집합이 있음을 나타낼 수 있다면 가설이 올바른 것입니다.
이러한 솔루션 세트 중 하나는 다음과 같습니다.
p = 0
q = m
k = m n - m
이러한 값이 다음과 같이 작동하는지 확인할 수 있습니다.
m + k = ( q - 2p ) n
=> m + mn - m = ( m - 2*0) n
=> mn = mn.
이 세트 들어 i있다
i = m + p n + k
=> m + 0 * n + mn - m = mn.
물론, 이것이 반드시 가장 작은 것은 아니라는 것을 알아야합니다. 다시 말해, 거북이와 토끼는 이미 여러 번 전에 만났을 수도 있습니다. 그러나 우리는 그들이 적어도 어느 시점에서 한 번 만나는 것을 보여주기 때문에 가설이 정확하다고 말할 수 있습니다. 따라서 한 단계 씩 한 단계 씩 이동하고 다른 하나는 한 번에 두 단계 씩 이동하면 만나야합니다.
이제 우리는 사이클의 시작 부분을 찾는 방법 인 알고리즘의 두 번째 부분으로 이동할 수 있습니다.
사이클 시작
거북이와 토끼가 만나면 거북이를 목록의 시작 부분으로 되돌리고 토끼가 만나는 곳 (주기 시작에서 k 단계 떨어져 있음)을 유지합시다.
가설은 우리가 그것들을 같은 속도 (둘 다 1 단계)로 움직이게하면, 그들이 다시 처음 만날 때 사이클이 시작된다는 것입니다.
이 가설을 증명해 봅시다.
먼저 오라클이 m이 무엇인지 알려줍니다.
그런 다음 m + k 단계를 이동 시키면 거북이가 원래 만나는 지점에 도착해야합니다 (주기에서 시작하여 k 단계-그림 참조).
이전에 우리는 그것을 보여 주었다 m + k = (q - 2p) n.
m + k 스텝은 사이클 길이 n의 배수이므로, hare는 그 사이에 사이클 (q-2p) 시간을 거쳐 같은 지점으로 돌아갑니다 (k 사이클이 사이클 시작에서 멀어짐).
이제 m + k 단계를 움직이게하는 대신 m 단계 만 움직이게하면 거북이가주기 시작에 도달하게됩니다. 토끼는 (q-2p) 회전을 완료하는 데 k 스텝이 부족합니다. 사이클 시작 앞에서 k 단계를 시작했기 때문에, 토끼는 사이클 시작에 도달해야합니다.
결과적으로, 그들은 처음 몇 번의 단계 후에 시작하는 사이클에서 만날 필요가 있다고 설명합니다 (거북이 m 단계 후에 사이클에 도착했을 때 이미 처음부터 거북이를 볼 수 없었기 때문에 처음으로 사이클).
이제 우리는 그것들이 만나기 전까지 이동해야하는 단계의 수가 목록의 시작에서 사이클 시작까지의 거리 인 것으로 판명되었습니다. 물론, 알고리즘은 m이 무엇인지 알 필요가 없습니다. 그들은 거북이와 토끼가 한 번에 한 단계 씩 만날 때까지 움직일 것입니다. 미팅 포인트는 사이클 시작이어야하고 단계 수는 사이클 시작까지의 거리 (m) 여야합니다. 리스트의 길이를 알고 있다고 가정하면,리스트 길이에서 m을 빼는주기의 길이를 계산할 수도 있습니다.
답변
이 이미지를 참조하십시오 :
회의 전에 slowPointer로 이동 한 거리 = x + y
회의 전에 fastPointer로 이동 한 거리 = (x + y + z) + y = x + 2y + z
fastPointer는 slowPointer 속도의 두 배로 이동하므로 미팅 포인트에 도달 할 때 시간이 일정 합니다.
따라서 간단한 속도, 시간 및 거리 관계를 사용하여 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
따라서 slowPointer 를 링크 된 목록의 시작 으로 이동 하고 slowPointer와 fastPointer가 한 번에 하나의 노드를 이동 하게하여 둘 다 같은 거리 를가집니다 .
링크 된 목록에서 루프가 시작되는 지점에 도달합니다.
답변
Old Monk의 단순하고 과소 평가 된 답변 은 빠른 러너가 단일 전체 사이클 만 완료 할 때주기를 찾는 방법을 설명합니다. 이 답변에서는 느린 러너가 루프에 들어가기 전에 빠른 러너가 루프를 여러 번 실행 한 경우를 설명합니다.
동일한 이미지 사용하기 :
빠른 러너가 느리고 빠른 만남 전에 루프 m 을 실행했다고 가정 해 봅시다 . 이것은 다음을 의미합니다.
- 느린 거리 : x + y
- 빠른 거리 : x + m (y + z) + y 즉 그들이 만나는 여분의 y
빠른 속도는 두 배의 느린 속도로 달리고 그들이 같은 시간 동안 달리고 있기 때문에, 우리가 거리를 두 배로 느리게 달리면 거리가 빨리 나옵니다. 그러므로,
- 2 (x + y) = x + m (y + z) + y
x를 구하면
x = (m-1) (y + z) + z
실제 시나리오에서는 x = (m-1) 전체 루프 실행 + 추가 거리 z를 의미 합니다.
따라서 하나의 포인터를 목록의 시작 부분에 놓고 다른 하나를 회의 지점에두면 동일한 속도로 이동하면 루프 포인터가 루프의 m-1 런을 완료 한 다음 다른 포인트 를 만나게됩니다 루프 시작에서 바로 포인터.
답변
매우 간단합니다. 상대 속도로 생각할 수 있습니다. 토끼가 두 개의 노드를 움직이고 거북이가 한 노드를 움직이면 거북이 토끼가 한 노드를 움직입니다 (거북이 있다고 가정). 따라서 순환 연결 목록에서 하나의 노드를 이동하면 해당 지점에서 다시 만나게됩니다.
원형 연결리스트 내에서 연결된 점을 찾은 후, 이제 두 연결리스트 문제의 교점을 찾는 문제가 줄어 듭니다.
답변
첫 번째 충돌시 거북이 는 위 그림과 같이 m + k 단계만큼 이동했습니다 . 토끼는 거북이보다 두 배 빠르게 움직입니다. 즉, 토끼는 2 (m + k) 걸음을 이동했습니다. 이러한 간단한 사실을 통해 다음 그래프를 도출 할 수 있습니다.
이 시점에서 우리는 거북이를 처음으로 다시 이동시키고 토끼와 거북이 모두 한 번에 한 단계 씩 움직여야한다고 선언합니다. 정의에 따르면, m 단계 후에 거북이가 사이클의 시작 부분에있게됩니다. 토끼는 어디에 있습니까?
토끼는 또한 사이클의 시작에있을 것입니다. 이것은 두 번째 그래프에서 분명합니다. 거북이가 처음으로 돌아 왔을 때, 토끼는 마지막주기 에서 k 단계 였습니다 . m 단계 후 , 토끼는 다른주기를 완료하고 거북이와 충돌했습니다.
답변
접근하다:
두 가지 포인터가 있습니다.
- 한 번에 한 노드 씩 이동하는 느린 포인터.
- 한 번에 두 노드를 이동하는 빠른 포인터.
두 포인터가 만나면 루프가 있음을 증명합니다. 일단 충족되면 노드 중 하나가 헤드를 가리키고 한 번에 한 노드 씩 진행합니다. 그들은 루프의 시작에서 만날 것입니다.
이론적 근거 :
두 사람이 원형 트랙을 따라 내려갈 때, 그 중 하나는 다른 속도의 두 배 속도로 어디에서 만나나요? 그들이 정확히 어디서 시작했는지.
이제 빠른 러너가 스텝 랩 k에서 헤드 스타트 단계를 가지고 있다고 가정 하십시오 n. 그들은 어디서 만날 것인가? n-k단계적으로 정확 합니다. 느린 주자가 (n-k)단계 를 다룰 때 빠른 주자가 k+2(n-k)단계를 다룰 것 입니다. ( 즉, k+2n-2k단계 즉 2n-k단계 ). 즉 (n-k)단계 (경로는 원형이며 우리는 그들이 만나는 라운드 수에 대해 걱정하지 않습니다; 우리는 그들이 만나는 위치에 관심이 있습니다).
이제 빠른 러너는 어떻게 맨 k먼저 단계를 시작 했습니까? 루프 시작에 도달하는 데 많은 단계가 느린 러너가 필요했기 때문입니다. 따라서 루프의 시작은 헤드 노드에서 k 단계입니다.
참고 : 두 포인터가 만나는 노드 k는 루프 시작 (루프 내부) k에서 멀어지고 헤드 노드는 루프 시작에서 멀어집니다. 따라서 봇에서 1 단계 속도로 같은 속도로 포인터를 진행하면 루프 시작시 만나게됩니다.
나는 그것이 간단하다고 생각합니다. 모호한 부분이 있으면 알려주십시오.
