شناسایی دور

تعاریف

S را مجموعه متناهی دلخواهی فرض کنید، f تابعی دلخواه از S به خودش، و x₀ هر عنصر دلخواه از Sباشد. برای هر i> 0، فرض می‌کنیم xᵢ = f(xᵢ − 1). فرض می‌کنیم μ کوچکترین اندیسی باشد به‌طوری‌که مقدار xμ به‌طور بینهایت در دنباله مقادیر xᵢ ظاهر شود، و فرض می‌کنیم λ (طول دور) باشد کوچکترین عدد صحیح مثبت باشد به‌طوری‌که xμ = xλ ₊ μ. تشخیص دور مسئله یافتن λ و μ می‌باشد.
همین مسئله را در نظریه گراف،با ساخت یک گراف تابع (که یک گراف جهت دار خوانده می‌شودد که در آن هر راس دارای یک یال خارج شونده است) که رئوس آن عناصر S و یال‌های آن یک عنصر را به مقدار تابع مربوط به آن نگاشت می‌کنند، همان‌طور که در شکل نشان داده شده‌است. مجموعه رئوس قابل دسترسی با شروع از راس x₀ از یک زیر گراف با یک شکل شبیه رو (ρ): یک مسیر با طول μ از x₀ به یک دور با λ راس.

بیان کامپیوتری

به‌طور کلی، f را نمی‌توان به صورت جدولی از مقادیر، طوری‌که در شکل بالا نشان داده شده نمایش داد. بلکه، یک الگوریتم تشخیص دور ممکن است یا با دنباله مقادیر xᵢ، یا یک تابع برای محاسبه f داده شود. هدف پیدا کردن λ و μ با بررسی چند مقدار از دنباله یا پیدا کردن مقدار تابع در چند مرتبه با کمترین استفاده از سلول‌های حافظه می‌باشد. به‌طور معمول، پیچیدگی فضا در مسئله تشخیص دور اهمیت دارد: ما مایل به حل این مسئله با استفاده ماز مقداری از حافظه هستیم که کمتر از حافظه مورد نیاز برای ذخیره کل دنباله اعداد می‌باشد.
در برخی از برنامه‌ها، و به ویژه در الگوریتم رو پولارد برای تجزیه اعداد طبیعی،الگوریتم دسترسی محدودتری به S و f دارد. در الگوریتم پولارد، به عنوان مثال، S مجموعه‌ای از اعداد صحیح می‌باشد که عامل اول عدد مورد تجزیه به آن بخشپذیر است، بنابراین حتی اندازه S هم نامعلوم است. برای اینکه تشخیص دور با چنین اطلاعات محدودی قابل استفاده باشد، باید براساس توانایی‌های زیر بنا شوند. در ابتدا فرض می‌شود الگوریتم حافظه مخصوص به خود را دارد که یک نشانگر به مقدار شروع یعنی x₀ دارد. در هر مرحله ممکن است یکی از سه عمل زیر را انجام دهد: ممکن است هر نشانگری را به شئ دیگری کپی کند، ممکن است f را اعمال کند و هرکدام از نشانگرهایش را با یک نشانگر به شئ بعدی جایگزین کند یا ممکن است با اجرای یک تابع تشخیص دهد که دو نشانگر به یک مقدار برابر در دنباله اشاره دارند یا نه. آزمون برابری می‌تواند بعضی از محاسبات غیربدیهی دربرداشته باشد: برای مثال، در الگوریتم پولارد رو، این عملیات این‌گونه پیاده می‌شود که آیا اختلاف بین دو مقدار ذخیره شده بزرگترین مقسوم علیه مشترک بغیر بدیهی با عدد مورد تجزیه دارد یا خیر. در این زمینه، با قیاس با مدل محاسباتی ماشین اشاره گر، یک الگوریتم که تنها از کپی کردن یک اشاره گر، پیشروی در دنباله، و آزمون‌های برابری استفاده می‌کند، الگوریتم اشاره‌گری نامیده می‌شود.

الگوریتم‌ها

اگر ورودی به عنوان یک رابطه برای محاسبه f داده شده باشد، مسئله تشخیص چرخه ممکن است به‌طور بدیهی با تنها λ + μ اجرای تابع حل شود، به سادگی با محاسبه دنباله‌ای از مقادیر xᵢ و با استفاده از یک ساختار دادهمانند یک جدول درهم ساز برای ذخیره این مقادیر و تست اینکه آیا هر مقدار در حال حاضر ذخیره شده‌است یا خیر. اما پیچیدگی فضایی این الگوریتم متناسب با λ + μ، به‌طور بی‌ارزشی بزرگ است. علاوه بر این برای اجرای این روش به عنوان یک الگوریتم اشاره‌گر، نیاز به استفاده از آزمون برابری برای هر جفت از مقادیر و در نتیجه به زمان از مرتبه دو می‌انجامد؛ بنابراین تحقیقات در این زمینه بر روی دو هدف متمرکز شده: استفاده از فضای کمتر از این الگوریتم ساده، و پیدا کردن الگوریتم‌های اشاره‌گری که با استفاده از آزمون برابری کمتر.

الگوریتم فلوید

الگوریتم یافتن دور فلوید الگوریتمی است که از دو اشاره‌گر استفاده می‌کند، که با سرعت‌های متفاوت در دنباله حرکت می‌کنند. همچنین به نام «الگوریتم لاک‌پشت و خرگوش» نامیده می‌شود با اشاره به حکایت لاک‌پشت و خرگوش از ازوپ.
الگوریتم پس از نام رابرت فلوید با اعتبار اختراع آن توسط دانلد کنوت نام‌گذاری شد. با این حال به نظر نمی‌رسد این الگوریتم در کارهای منتشر شده از فلوید باشد، و این ممکن است یک سوءتفاهم باشد: فلوید توصیف الگوریتم را با لیست کردن تمامی دورها در یک گراف جهت دار سال ۱۹۶۷ سال در یک مقاله انجام داد، اما این مقاله مسئله یافتن دور در یک گراف تابعی که موضوع این مقاله است را شرح نداد. در واقع بیانیه کنوت (در سال ۱۹۶۹)، و نسبت دادن آن به فلوید، بدون استناد، اولین ظهور آن به‌طور چاپی است و آن را در نتیجه ممکن است یک قضیه منتسب به یک فرد است.
نکته اصلی در درک این الگوریتم این است که، برای هر عدد صحیح i ≥ μ و k ≥ ۰ داریم xᵢ = xᵢ ₊ kλکه در آن λ طول حلقه یافت شده و μ اندیس اولین عنصر چرخه است. به‌طور خاص، i = kλ ≥ μاگر و تنها اگر xᵢ = x₂ᵢ. این الگوریتم تنها نیاز به بررسی مقادیر تکراری این فرم خاص، تا آنجا که یکی از مقادیر پس از شروع دنباله تکرار شود، برای یافتن دوره تناوبv برای تکرار که مضربی از λ می‌باشد. به محض اینکه v یافت شد، الگوریتم دنباله را دوباره از آغاز بررسی می‌کند تا اولین مقدار تکراری xμ، با توجه به این مسئله کهv بر λ بخشپزیر است به همین دلیل xμ = xμ ₊ ᵥ. سرانجام پس از یافتن مقدار μ به‌طور بدیهی به دنبال طول λ می‌گردیم که کوچکترین طول دور می‌باشد، با یافتن اولین مکان μ + λ که در آن xμ ₊ λ = xμ.
این الگوریتم در نتیجه دو اشاره گر را در طول دنباله داده شده حفظ می‌کند، یکی (لاک‌پشت) در xᵢو دیگری (خرگوش) در x₂ᵢ. در هر مرحله از الگوریتم،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) فضای ذخیره‌سازی استفاده می‌کند.

الگوریتم برنت

ریچارد پیرس برنت یک الگوریتم یافتن دور جایگزین را توصیف می‌کند، که همانند الگوریتم لاک‌پشت و خرگوش تنها نیاز به دو اشاره گر در دنباله دارد. با این حال، بر اساس اصل مختلف دیگری بنا شده‌است: جستجو برای کوچکترین توان دو 2ⁱ که بزرگتر از هر دو λ و μ باشد. برای i = ۰, ۱, ۲, ...، الگوریتم x₂ⁱ−1 را با هر یک از مقادیر پس از آن دنباله مقایسه می‌کند، و هر گاه عدد مورد نظر را یافت متوقف می‌شود. این الگوریتم نسبت به الگوریتم لاک‌پشت و خرگوش دو مزیت دارد: مقدار صحیح λ برای دور را به‌طور مستقیم می‌یابد به جای اینکه نیاز به جستجو برای آن در مرحله بعدی داشته باشد، و مراحل آن شامل تنها یک مقداریابی از f می‌باشد.
کد پایتون زیر با جزییات نشان می‌دهد این تکنیک چگونه کار می‌کند.
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) فضای ذخیره‌سازی استفاده می‌کند.
سخت نیست که نشان دهیم تعداد مقداریابی‌های تابع نسبت به الگوریتم فلوید هیچگاه بیشتر نمی‌شود. برنت ادعا می‌کند که به‌طور متوسط الگوریتم یافتن دور او حدود ۳۶ درصد سریعتر از الگوریتم فلوید می‌باشد و الگوریتم پولارد رو را تا حدود ۲۴٪ تسربع می‌کند. او همچنین یک آنالیز حالت متوسط برای یک نسخه تصادفی الگوریتم اجرا کرد که در آن دنباله‌ای از شاخض‌های دنبال شده خود توانی از ۲ نبودند اما یک مضربی از توان دو به صورت تصادفی بودند. اگرچه برنامه اصلی او در رابطه با تجزیه عوامل اول اعداد صحیح بود، برنت همچنین در رابطه با برنامه تست کردن اعداد شبه تصادفی نیز بحث کرد.

الگوریتم گسپر

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