NovelAI Diffusion V4 Full プライベートテスト、近日公開 by 不気味の谷
607 단어
3 분
브렌트 알고리즘(사이클 탐지 알고리즘)
개요
브렌트 알고리즘은 Richard P. Brent가 토끼와 거북이 알고리즘같은 사이클 탐지 알고리즘을 개선하기 위해 고안한 알고리즘입니다.
브렌트 알고리즘은 기존 플로이드의 토끼와 거북이 알고리즘과 비교해 실행시간이 24%~36%나 더 빠른 성질을 가지고 있습니다.
이 알고리즘 또한 토끼와 거북이 알고리즘처럼 두 개의 포인터를 사용하고 사이클의 시작점과 길이를 모두 찾을 수 있습니다.
토끼와 거북이 알고리즘과 다르게 브렌트 알고리즘은 탐색범위를 늘려 평균적으로 더 빠르게 탐색을 실시합니다.
동작 원리
브렌트 알고리즘은 토끼와 거북이라는 포인터와 power(탐색 범위)와 len이라는 현재 단계의 이동 횟수 변수를 사용합니다.
토끼는 시작점에서 한 칸 건너간 곳에서 출발하고 거북이는 시작점에서 출발, power와 len은 1의 값을 가지고 시작합니다.
이후로는 아래의 과정을 충돌이 발생하거나 토끼가 리스트의 끝에 도달할 때까지 반복합니다.
- 토끼가 거북이가 충돌하는가?
- len이 power와 같은가?
- 같다면
- 거북이를 현재 토끼 위치로 재설정
- power를 2배 증가
- len을 0으로 리셋
- 같다면
- 토끼 한 칸 증가
- 길이 1 증가
만약 리스트의 끝에 도달하면 사이클이 존재하지 않는 것입니다.
충돌이 발생할 경우 len 값이 사이클의 길이입니다.
예시로는 아래 그림과 같은 경우가 있습니다.
이렇게 사이클의 존재를 찾은 뒤에는 시작점도 탐색할 수 있습니다.
시작점을 탐색할 땐 거북이를 다시 출발점으로 보내고 사이클 길이만큼 토끼를 앞으로 이동시킵니다.
그 후 거북이와 토끼를 한 칸씩 이동시키며 만나는 지점을 찾고 이 때의 이동횟수가 출발점부터 사이클 시작점까지의 거리입니다.
