攻城獅
Not a programmer 不工程的攻城獅

Follow

Not a programmer 不工程的攻城獅

Follow

Algorithm 演算法 - 判圈系列 Brent 判圈算法(傳送龜算法)

Brent's Cycle Detection Algorithm (The Teleporting Turtle)

攻城獅's photo
攻城獅
·Jun 10, 2022·
Play this article

簡介 Intro

image.png

根據演算法期會比 Floyd 的方式快 24-36% 的速度。

解釋

這個演算法的方式其實基本上跟 Floyd 不一樣的地方在於龜兔的移動方式。在 Floyd 的演算法中,龜兔會一起移動,只是步數的不同。但在 Brent 的演算法中,只有兔子在移動。

每次兔子移動後,烏龜會馬上傳送到跟兔子一樣的位置(所以才叫 Teleporint Turtle)。然後兔子在將步數倍增移動。例如兔子第一次移動 1 格、再來 2 格、4 格一直走到底或是遇到烏龜。

進階題目

找出迴圈長度

當相遇時,兔子從原本位置走到烏龜的位置就是迴圈的長度。為什麼呢?因為當兔子要開始走的時候,假設位置是 x,烏龜會需要先瞬移到兔子現在的位置 x。而兔子從 x 走到烏龜的位置,不就是整整繞了一圈嗎?因此當下兔子走的步數就是迴圈的長度

def detectCycle(self):
    # if head is null
    # then no loop
    temp = self.head

    if not (temp):
        return False
    tortoise = temp
    hare = temp.next
    power = 1
    length = 1

    # This loop runs till we
    # find the loop. If there
    # is no loop then second
    # pointer ends at NULL
    while hare and hare != tortoise:

        # condition after which
        # we will update the power
        # and length as smallest
        # power of two gives
        # the start of cycle.
        if length == power:

            # updating the power.
            power *= 2

            # updating the length
            length = 0

            tortoise = hare

        hare = hare.next
        length += 1
    # if it is null then no loop
    if not (hare):
        return

找出迴圈連結點

要找出連結點的話,在找出迴圈長度後。只要將兔子放回開頭,而烏龜放到從起點走回圈長度的距離(就是 length + 1)。之後兩個同時一步一步走,走到相遇就是起點了。

這邊要來講說為什麼,發現網路上都只跟我說這樣就好,但原理還是要理解才不容易忘。

假設迴圈長度 C、起點到迴圈連接點的長度是 L。然後從連接點到烏龜的點是 A,烏龜的位置到連接點長度是 B

A + B = C
A = C - L
C - L + B = C
C - C + B = L
B = L

所以就是 BL 喔(笑


    # Now set tortoise pointer
    # to the beginning and
    # hare pointer to
    # beginning plus cycle
    # length which is length.
    tortoise = hare = self.head
    while length > 0:
        hare = hare.next
        length = length - 1

    # Now move both pointers
    # at same speed so that
    # they meet at the
    # beginning of loop.
    while hare != tortoise:
        hare = hare.next
        tortoise = tortoise.next

    return tortoise

Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this