شناسایی دور

فلوید «لاک‌پشت و خرگوش» چرخه تشخیص الگوریتم‌های اعمال شده به توالی ۲, ۰, ۶, ۳, ۱, ۶, ۳, ۱, ...

الگوریتم یافتن دور فلوید الگوریتمی است که از دو اشاره‌گر استفاده می‌کند، که با سرعت‌های متفاوت در دنباله حرکت می‌کنند. همچنین به نام «الگوریتم لاک‌پشت و خرگوش» نامیده می‌شود با اشاره به حکایت لاک‌پشت و خرگوش از ازوپ.

الگوریتم پس از نام رابرت فلوید با اعتبار اختراع آن توسط دانلد کنوت نام‌گذاری شد.[3][4] با این حال به نظر نمی‌رسد این الگوریتم در کارهای منتشر شده از فلوید باشد، و این ممکن است یک سوءتفاهم باشد: فلوید توصیف الگوریتم را با لیست کردن تمامی دورها در یک گراف جهت دار سال ۱۹۶۷ سال در یک مقاله انجام داد،[5] اما این مقاله مسئله یافتن دور در یک گراف تابعی که موضوع این مقاله است را شرح نداد. در واقع بیانیه کنوت (در سال ۱۹۶۹)، و نسبت دادن آن به فلوید، بدون استناد، اولین ظهور آن به‌طور چاپی است و آن را در نتیجه ممکن است یک قضیه منتسب به یک فرد است.[6]

نکته اصلی در درک این الگوریتم این است که، برای هر عدد صحیح i ≥ μ و k ≥ ۰ داریم x_i = x_{i + kλ}که در آن λ طول حلقه یافت شده و μ اندیس اولین عنصر چرخه است. به‌طور خاص، i = kλ ≥ μاگر و تنها اگر x_i = x_2i. این الگوریتم تنها نیاز به بررسی مقادیر تکراری این فرم خاص، تا آنجا که یکی از مقادیر پس از شروع دنباله تکرار شود، برای یافتن دوره تناوبv برای تکرار که مضربی از λ می‌باشد. به محض اینکه v یافت شد، الگوریتم دنباله را دوباره از آغاز بررسی می‌کند تا اولین مقدار تکراری x_μ، با توجه به این مسئله کهv بر λ بخشپزیر است به همین دلیل x_μ = x_{μ + v}. سرانجام پس از یافتن مقدار μ به‌طور بدیهی به دنبال طول λ می‌گردیم که کوچکترین طول دور می‌باشد، با یافتن اولین مکان μ + λ که در آن x_{μ + λ} = x_μ.

این الگوریتم در نتیجه دو اشاره گر را در طول دنباله داده شده حفظ می‌کند، یکی (لاک‌پشت) در x_iو دیگری (خرگوش) در x_2i. در هر مرحله از الگوریتم،i را با حرکت لاک‌پشت یک گام به جلو یک واحد افزایش می‌دهد و خرگوش دو گام به جلو در دنباله، و سپس مقدار دنباله در این دو اشاره گر را مقایسه می‌کند. کوچکترین مقدار i > 0 که در آن نقطه مقدار لاک‌پشت و خرگوش برابر است که مقدار ν مورد نظر ماست.

کد پایتون زیر این ایده به عنوان یک الگوریتم پیاده‌سازی می‌شود:

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

این کد تنها به دنباله با ذخیره‌سازی و کپی کردن اشاره گرها، مقداریابی تابع و آزمون برابری دسترسی دارد؛ بنابراین، آن را به عنوان یک الگوریتم اشاره‌گری می‌نامیم. این الگوریتم از O(λ + μ) عملیات از این نوع و O(1) فضای ذخیره‌سازی استفاده می‌کند.[7]

ریچارد پیرس برنت یک الگوریتم یافتن دور جایگزین را توصیف می‌کند، که همانند الگوریتم لاک‌پشت و خرگوش تنها نیاز به دو اشاره گر در دنباله دارد.[8] با این حال، بر اساس اصل مختلف دیگری بنا شده‌است: جستجو برای کوچکترین توان دو 2ⁱ که بزرگتر از هر دو λ و μ باشد. برای i = ۰, ۱, ۲, ...، الگوریتم x_2ⁱ−1 را با هر یک از مقادیر پس از آن دنباله مقایسه می‌کند، و هر گاه عدد مورد نظر را یافت متوقف می‌شود. این الگوریتم نسبت به الگوریتم لاک‌پشت و خرگوش دو مزیت دارد: مقدار صحیح λ برای دور را به‌طور مستقیم می‌یابد به جای اینکه نیاز به جستجو برای آن در مرحله بعدی داشته باشد، و مراحل آن شامل تنها یک مقداریابی از f می‌باشد.[9]

کد پایتون زیر با جزییات نشان می‌دهد این تکنیک چگونه کار می‌کند.

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 λ
    mu = 0
    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
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    return lam, mu

مانند الگوریتم لاک‌پشت و خرگوش، این یک الگوریتم اشاره‌گری است که از O(λ + μ) تست و مقدار یابی تابع و O(1) فضای ذخیره‌سازی استفاده می‌کند.

سخت نیست که نشان دهیم تعداد مقداریابی‌های تابع نسبت به الگوریتم فلوید هیچگاه بیشتر نمی‌شود. برنت ادعا می‌کند که به‌طور متوسط الگوریتم یافتن دور او حدود ۳۶ درصد سریعتر از الگوریتم فلوید می‌باشد و الگوریتم پولارد رو را تا حدود ۲۴٪ تسربع می‌کند. او همچنین یک آنالیز حالت متوسط برای یک نسخه تصادفی الگوریتم اجرا کرد که در آن دنباله‌ای از شاخض‌های دنبال شده خود توانی از ۲ نبودند اما یک مضربی از توان دو به صورت تصادفی بودند. اگرچه برنامه اصلی او در رابطه با تجزیه عوامل اول اعداد صحیح بود، برنت همچنین در رابطه با برنامه تست کردن اعداد شبه تصادفی نیز بحث کرد.

الگوریتم گسپر[10][11] دوره تناوب را می‌یابد اما نقطه شروع اولین پریود را مشخص نمی‌کند. از ویژگی‌های اصلی آن است که هیچ‌گاه برای مقداریابی تابع مولد بر نمی‌گردد که این عمل از نظر زمانی و حافظه بهینه است.

برخی از نویسندگان روش‌هایی را مورد بررسی قرار داده‌اند که نسبت به الگوریتم فلوید و برنت حافظهٔ بیشتری نیاز دارد اما دور را سریعتر شناسایی می‌کند. به‌طور کلی این روش‌ها دنباله‌ای از مقادیر از پیش محاسبه‌شده را ذخیره می‌کنند، و بررسی می‌کنند که آیا مقادیر جدید ما مقادیر قبلاً محاسبه شده برابرند یا خیر. به منظور انجام سریع آن‌ها، به‌طور معمول از یک جدول درهم‌سازی یا یک داده ساختار مشابه برای ذخیره مقادیر از قبل محاسبه شده‌استفاده می‌شود، و در نهایت هیچ الگوریتم اشاره‌گری در کار نیست: به‌طور خاص آن‌ها قابل پیاده شدن به روی الگوریتم پولارد نیستند. تفاوتی که این الگوریتم‌ها دارند در این است که کدام مقادیر برای ذخیره شدن انتخاب شوند. ما به بررسی این روش‌ها به‌طور خلاصه می‌پردازیم:

• مدل‌های مختلف روش برنت به این صورت است که اندیس‌های دنباله‌های ذخیره شده توانی از یک عدد نزدیک به یک R به غیر از ۲ باشد. با انتخاب R به عنوان عددی نزدیک به یک، و ذخیره کردن دنباله مقادیری که اندیس‌هایشان نزدیک به دنباله توان‌های R می‌باشد، یک الگوریتم تشخیص دور می‌تواند از تعدادی از مقایسه‌ها از میان عوامل λ + μ استفاده کند.[12][13]
• Sedgewick, Szymanski و Yao روشی ارائه دادند که به M سلول از حافظه نیاز دارد و در بدترین حالت به ${\displaystyle (\lambda +\mu )(1+cM^{-1/2})}$ مقداریابی تابع برای برخی مقادیر ثابت c نیاز دارد، که نشان‌دهنده بهینگی است. این روش شامل حفظ یک پارامتر عددی مانند d، ذخیره کردن مکان‌هایی از دنباله که مضربی از d می‌باشند در یک جدول، و پاک کردن جدول و دو برابر کردن مقدار d هر زمان که مقادیر زیادی ذخیره شد.
• تعدادی از نویسندگان روش‌های نقاط متمایز را توصیف کرده‌اند که مقادیر تابع را در یک جدول بنابر معیارهایی مثل مقدار آن‌ها (به حای مکان آنها) ذخیره می‌کنند. برای مثال، برای بعضی مقادیر d چون بر صفر بحش‌پذیر هستند مقادیر مساوی با صفر ذخیره می‌شوند[14].[15] به‌طور ساده‌تر ،Nivasch با اعتبار دادن به Woodruff با پیپشنهاد ذخیره کردن تصادفی مقادیری که قبلاً مشاهده شده، اقدام به انتخاب یک عدد تصادفی مناسب کند تا نمونه به‌طور تصادفی باقی بماند.
• Nivasch الگوریتمی را توصیف می‌کند که از مقدار حافظه معین و ثابت استفاده نمی‌کند اما مقدار حافظه مورد انتظارش (تحت این فرض که ورودی تابع تصادفی می‌باشد) به صورت لگاریتمی از طول دنباله می‌باشد. در این روش یک بخش زمانی در جدول حافظه ذخیره می‌شود به‌طوری‌که هیچ‌کدام از بخش‌های بعدی مقدار کوچکتری از آن نداشته باشند. همان‌طور که Nivasch نمایش داد، می‌توان آیتم‌های این روش را با استفاده از داده ساحتار پشته حفظ کرد، و در برای هر عضو متوالی دنباله کافی است تنها آن را با عنصر روی پشته مقایسه کنیم. الگوریتم زمانی متوقف می‌شود که عنصر تکرار شونده با کمترین مقدار یافت شود. با اجرای الگوریتم مشابه در چندین پشته، با استفاده از جایگشت‌های تصادفی مقادیر دنباله برای ترتیب‌های محتلف آن‌ها در پشته، منجر به یک بهینگی زمانی یا حافظه می‌شود همانند الگوریتم‌های قبلی. حتی نسخه‌ای از این الگوریتم که با یک پشته است یک الگوریتم اشاره‌گری نیست، با توجه به این که نیاز به مقایسه برای تعیین مقدار کوچکتر از میان دو مقدار را دارد.

هر الگوریتم شناسایی دور که اقدام به ذخیره M مقدار از دنباله ورودی در حافظه می‌کند، حداقل نیاز به اجرای ${\displaystyle (\lambda +\mu )(1+{\frac {1}{M-1}})}$ مقداریابی تابع دارد.[16][17]