Hledání cyklu funkce

Příklad funkce na devítiprvkové množině a její reprezentace orientovaným grafem

Hledání cyklu funkce je úloha z oblasti matematické informatiky. Předpokládá zadanou funkci $f$ na konečné množině $M$ a posloupnost hodnot

$x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots$

Protože se jedná o posloupnost na konečné množině, musí se časem nějaká hodnota zopakovat, a od té chvíle se bude jednat o periodickou posloupnost, neboť od dané zopakované hodnoty jsou odvozeny stejně i všechny hodnoty následující. Cílem úlohy je zjistit, od jaké položky je posloupnost periodická a jakou má délku periody. Délka periody se tradičně v tomto kontextu označuje řeckým písmenem λ, délka předperiody řeckým písmenem μ.

Algoritmy úlohu řešící jsou aplikovány například pro testování kvality generátorů pseudonáhodných čísel a kryptografických hašovacích funkcí, detekce nekonečných cyklů v počítačových programech a stavech celulárních automatů, případně i nalezení cyklu v lineárních seznamech.

Algoritmy

Floydův algoritmus želvy a zajíce

Ilustrace algoritmu na krátké posloupnosti 2,0,6,3,1,6,3,1,…

Floydův algoritmus hledání cyklu je značně prostorově úsporný, stačí mu trvale udržovat vždy jen dvě hodnoty funkce. Americkému matematikovi Robertu Floydovi jej připsal ve svém vlivném díle Umění programování informatik Donald Knuth, ovšem v žádné Floydově publikaci algoritmus popsán není a tak je otázka původního autorství otevřená. Rozšířený název algoritmu odkazuje k Ezopově bajce Želva a zajíc, ve které figurují rovněž dva protagonisté, „rychlejší“ a „pomalejší“.

Principem algoritmu je vlastně postupný výpočet dvou posloupností, které obě začínají na počátku vstupní posloupnosti na hodnotě $x_{0}$, ale zatímco jedna z nich („pomalejší, želva“) odpovídá vstupní posloupnosti a postupuje v každé iteraci jen o jedno místo, tj. $z_{i+1}=f(z_{i})$, druhá („rychlejší, zajíc“) postupuje v každé iteraci o dvě místa, tj. $y_{i+1}=f(f(y_{i}))$.

Protože „želva“ neustále postupuje, jistě musí časem přejít přes předperiodickou část do cyklu. A protože se vzdálenost mezi „želvou“ a „zajícem“ v každém kroku zvětšuje o jedna, jistě musí následně v nějakém kroku být násobkem periody a „zajíc“ i „želva“ tak budou na stejné hodnotě.

Následující zdrojový kód v Pythonu dává představu o možné implementaci:

def floyd(f, x0):
    # Hlavní část algoritmu sloužící k nalezení indexu i, tak že x_i = x_2i.
    # Zajíc se pohybuje dvakrát rychleji a tak je v každém kroku
    # od želvy o jedna dál než v předchozím.
    # Časem se ocitnou oba v periodické části a následně
    # dojde i k tomu, že jejich vzdálenost bude násobkem periody
    zelva = f(x0) 
    zajic = f(f(x0))
    while zelva != zajic:
        zelva = f(zelva)
        zajic = f(f(zajic))
  
    # V tuto chvíli je vzdálenost želvy od zajíce, 
    # která je rovna vzdálenosti želvy od počátku,
    # násobkem délky periody.
    # Pokud teď necháme zajíce pobíhat dál po cyklu rychlostí 1
    # a želvu pustíme znovu od počátku rychlostí 1, potkají se,
    # jakmile želva vstoupí do cyklu, čímž získáme délku předperiody
    my = 0
    zelva = x0
    while zelva != zajic:
        zelva = f(zelva)
        zajic = f(zajic)   
        my += 1
 
    # Nakonec necháme želvu na místě a zajícem půjdeme pomalu 
    # po cyklu, čímž spočítáme délku cyklu
    lambda = 1
    zajic = f(zelva)
    while zelva != zajic:
        zajic = f(zajic)
        lambda += 1
 
    return lambda, my

Brentův algoritmus

Australský matematik Richard P. Brent navrhl velmi podobný algoritmus, který rovněž využívá vždy současně jen dvě hodnoty funkce, ovšem postupuje jiným způsobem, který nevyžaduje tolikrát vyhodnocovat funkci $f()$. Postupuje po prodlužujících se úsecích délky mocniny dvou, ve kterých vždy želva vyčkává na jejich počátku a zajíc je pečlivě projde, aby se pak želva přesunula na jeho místo a pokračovalo se stejným způsobem dále.

def brent(f, x0):
    mocnina = lambda = 1
    zelva = x0	   # želva začíná na začátku
    zajic = f(x0)  # zajíc o krok dál
    while zelva != zajic:
        if mocnina == lambda:  # dosáhli jsme nové mocniny dvou?
            zelva = zajic
            mocnina *= 2
            lambda = 0
        zajic = f(zajic)
        lambda += 1

    # lamdu už máme, teď najdeme mý
    my = 0

    # umístíme zajíce do vzdálenosti lambda od želvy
    zelva = zajic = x0
    for i in range(lambda):
        zajic = f(zajic)

    # a pak oběma hýbeme o jedna, dokud nedojde ke shodě
    while zelva != zajic:
        zelva = f(zelva)
        zajic = f(zajic)
        my += 1
 
    return lambda, my

Reference

V tomto článku byly použity překlady textů z článků Hase-Igel-Algorithmus na německé Wikipedii a Cycle detection na anglické Wikipedii.

Portály: Matematika