Phát hiện chu trình

Trong Khoa học máy tính, bài toán phát hiện chu trình hay tìm chu trình là bài tìm thuật toán tìm vòng lặp trong một chuỗi giá trị hàm.

Bất kỳ hàm  nào ánh xạ một tập hữu hạn  tới chính nó, và bất kỳ giá trị ban đầu  trong , chuỗi các giá trị hàm

 

phải có một giá trị xuất hiện hai lần: có một số cặp i và j phân biệt sao cho . Khi điều này xảy ra, chuỗi tiếp tục chu trình một cách định kỳ, bằng cách lặp lại chuỗi giá trị từ  tới . Tìm chu trình là bài toán tìm i và j khi biết  và .

Rất nhiều thuật toán tìm chu trình nhanh và dùng ít bộ nhớ được biết. Thuật toán rùa và thỏ của Robert W.Floyd di chuyển hai con trỏ với vận tốc khác nhau qua chuỗi cho đến khi chúng cùng chỉ một giá trị. Lựa chọn khác, ta có thuật toán của Brent dựa trên ý tưởng tìm kiếm theo cấp số mũ. Cả hai thuật toán trên chỉ dùng một số lượng cố định bộ nhớ và tính giá trị hàm một lượng tỷ lệ thuận với khoảng cách tính từ xuất phát của chuỗi đến giá trị lặp đầu tiên. Các thuật toán khác đổi bộ nhớ lớn hơn để tính ít hơn số lần tính giá trị hàm.

Ứng dụng của phát hiện chu trình bao gồm thử nghiệm chất lượng của bộ sinh số giả ngẫu nhiên và hàm băm mật mã học, các thuật toán trong lý thuyết số tính toán, phát hiện vòng lặp vô hạn trong các chương trình máy tính và các cấu hình tuần hoàn trong tế bào tự động hóa.

Thí dụ 

Hình bên cho biết một hàm  ánh xạ tập  tới chính nó. Nếu ta xuất phát từ  và liên tục áp dụng hàm , ta sẽ được chuỗi sau

 

Chu trình trong chuỗi giá trị này là 6, 3, 1.

Định nghĩa 
Gọi  là tập hữu hạn bất kỳ,   là hàm bất kỳ từ  ánh xạ vào chính nó và  là phần tử bất kỳ trong . Với bất kỳ , đặt . Gọi  là chỉ số nhỏ nhất sao cho giá trị  thường xuyên lặp lại vô hạn trong chuỗi giá trị  và đặt  (độ dài vòng lặp) là số nguyên dương nhỏ nhất sao cho . Bài toán phát hiện chu trình yêu cầu tìm hai giá trị  và .

Ta có thể xét bài toán này bằng lý thuyết đồ thị, bằng cách xây một đồ thị hàm (một đồ thị có hướng mà mỗi đỉnh có một cung đi ra) trong đó mỗi đỉnh là một phần tử của S, và các cung đi ra ánh xạ phần tử giá trị hàm tương ứng, như hình trên.

Các thuật toán 
Nếu input được đưa như một thủ tục con là để tìm f, bài toán có thể giải đơn giản dùng chỉ  lần tính hàm, bằng cách tính chuỗi giá trị  dùng một cấu trúc dữ liệu như bảng băm để lưu các giá trị này và kiểm tra xem các giá trị sau đã được lưu chưa. Tuy nhiên, độ phức tạp bộ nhớ tỉ lệ thuận với , lớn không cần thiết. Do đó nghiên cứu trong khu vực này tập trung vào hai mục tiêu: dùng ít bộ nhớ hơn thuật toán trên và tìm thuật toán con trỏ dùng ít số lần kiểm tra hơn.

Thuật toán rùa và thỏ của Floyd

Thuật toán tìm chu trình của Floyd là thuật toán con trỏ dùng hai con trỏ, di chuyển trên cùng một chuỗi với tốc độ khác nhau. Nó cũng được gọi là "thuật toán rùa và thỏ", dựa trên câu chuyện ngụ ngôn của Aesop.

Thuật toán được đặt tên theo Robert W. Floyd, người được công nhận bởi Donald Knuth. Tuy nhiên, thuật toán không xuất hiện trong các bài của Floyd, và do đó đây có thể là quy kết nhầm: Floyd mô tả các thuật toán liệt kê toàn bộ các chu trình đơn trong một đồ thị có hướng trong tờ nghiên cứu năm 1967, nhưng tờ báo đó không mô tả bài toán tìm chu trình với đồ thị hàm ở đây. Thậm chí, theo lời của Knuth (vào năm 1969), quy nó về Floyd mà không trích dẫn.

Yếu tố quan trọng trong thuật toán như sau. Nếu có một chu trình, thì, với bất kỳ  và , , với  là độ dài vòng lặp cần tìm và  là vị trí của phần tử đầu tiên trong chu trình. Dựa trên đây, ta có thể chứng minh  với một vài số  khi và chỉ khi . Như vậy, thuật toán chỉ cần kiểm tra các giá trị lặp lại dưới dạng đặc biệt trên, với một con trỏ để cách gấp đôi từ vị trí xuất phát, để tìm chu kỳ  cho một lần lặp là bội của . Một khi  được tìm thấy, thuật toán tìm ngược lại từ lúc ban đầu để tìm giá trị đầu tiên  trong chuỗi, khi biết rằng  là ước của  và do đó .  Cuối cùng, một khi  đã được biết, bài toán trở nên đơn giản trong việc tìm độ dài  cho chu trình lặp lại ngắn nhất, bằng việc tìm vị trí đầu tiên của  sao cho .

Thuật toán do đó dùng hai con trỏ, con trỏ đầu tiên (con rùa) nằm tại , và con còn lại (con trỏ) nằm tại . Trong mỗi bước của thuật toán, tăng  bởi một, di chuyển con rùa một bước phía trước và con thỏ hai bước phía trước trong chuỗi, rồi so sánh giá trị chuỗi ở hai con trỏ này. Giá trị nhỏ nhất của  sao cho rùa và thỏ đều trỏ vào cùng một giá trị là giá trị  cần tìm.

Đoạn code Python sau mô tả ý tưởng thuật toán trên:

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Thuật toán chỉ dùng con trỏ để lưu và sao chép giá trị, tính giá trị hàm và kiểm tra bằng nhau, do đó nó thỏa mãn yêu cầu của thuật toán con trỏ.Thuật toán dùng  số phép tính trên, và  bộ nhớ.

Thuật toán của Brent 

Richard P. Brent mô tả một thuật toán tìm chu trình khác, giống thuật toán rùa và con thỏ, chỉ cần hai con trỏ để duyệt dãy số. Tuy nhiên, nó dựa theo nguyên tắc khác: tìm giá trị lũy thừa bậc hai nhỏ nhất  mà lớn hơn cả  và . Với , thuật toán so sánh  với mỗi giá trị phần tử tiếp theo cho đến khi gặp lũy thừa bậc hai tiếp theo, dừng khi nó gặp một cặp bằng nhau. Thuật toán có hai ưu thế so với thuật toán rùa và con thỏ: nó tìm đúng và trực tiếp giá trị  của chu trình, thay vì phải tìm nó trong đoạn mã sau, và các bước của nó chỉ cần một phép tính    hơn là 3.

Đoạn code python sau mô tả lại ý tưởng trên.
def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu

Giống thuật toán rùa và thỏ, đây là thuật toán con trỏ dùng  lần kiểm tra và tính hàm cùng với  bộ nhớ. Đồng thời cũng không quá khó để chứng minh rằng số lần tính hàm không bao giờ cao hơn số lần tính trong thuật toán của Floyd. Brent cho rằng, trên trung bình, thuật toán tìm chu trình của ông chạy khoảng 36% nhanh hơn so với cái của Floyd và nó đẩy tốc độ cho thuật toán Pollard rho bởi tầm 24%. Ông cũng xét phân tích trung bình cho phiên bản ngẫu nhiên của thuật toán trong đó dãy chỉ số xét bởi con trỏ chậm hơn không phải lũy thừa bậc hai như thường, mà là bội ngẫu nghiên của lũy thừa bậc hai. Mặc dù ông định áp dụng chủ yếu cho các thuật toán phân tích số nguyên, Brent cũng có xét tới các ứng dụng cho việc kiểm nghiệm các bộ sinh số giả ngẫu nhiên.

Tham khảo

Thuật toán tổ hợp