Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde veriyi modellemek için kullanılan graflarda bir döngü (cycle) olup olmadığını algılamaya yaramak için kullanılan algoritmadır. Floyd Döngü Yakalama Algoritması (Floyd’s Cycle Detection Algorithm) olarak da geçen bu algoritmaya göre bir yol üzerinde hareket eden iki farklı hızdaki gösterici (pointer) aynı değeri gösterebiliyorsa burada bir döngü bulunuyor demektir.
Tosbağa ve tavşan benzetmesinde ise tavşan, tobağadan iki misli hızlı gitmekte ve dolayısıyla bir zamandan şayet döngü bulunuyorsa mutlaka tosbağayı yakalaması beklenmektedir.
Örneğin aşağıdaki döngüyü ele alalım:
Yukarıdaki döngüyü kaplumbağa ve tavşanın dönüşünü inceleyelim. Başlangış düğümü olarak A’dan başlanıyor olsun.
Yukarıdaki örnekte kaplumbağa ve tavşanın başlangıç durumları ele alınmış. Tavşan kaplumbağadan iki misli hızlıl olduğu için daha ileride başlıyor ve birbirlerine eşit olana kadar sürekli hareket ediyorlar. Yani tavşan 2 kaplumbağa ise 1 hızında hareket ediyor.
Durumları aşağıdaki şekilde sıralanabilir:
T K
---
D B
F C
B D
D E
F F
Görüldüğü üzere tavşan her adımda ikişer atlarken kaplumbağa 1 adım ilerlemekte ve sonunda F düğümünde ikisi de aynı yeri göstermektedir. Buradan sonuç olarak bir döngü olduğuna varılabilir. Yani şayet 2 birim hızla giden ve 1 birim hızla giden iki gösterici (pointer) aynı yerde buluşuyorlarsa bunun anlamı ancak bir döngü olmasıdır.
Yukarıdaki graflar üzerinde kullanılan bu yaklaşım sayı teorisinde de (number theory) kullanılabilir. Örneğin dairesel grup (cyclic group) bulunması veya verilen bir sayı grubunun (dizisinin) dairesel olduğunun anlaşılması da mümkündür.
f(x) şeklinde dairesel olup olmadığı bilinmeyen bir fonksiyon düşünelim.
Kaplumbağa : f(x)
Tavşan : f(f(x))
şeklinde sayılar üretsinler. Bu durumda tavşan bir şekilde kaplumbağaya eşitse dairesel bir gruptan bahsediliyor demektir.
Örneğin
f(x) = 3x + 2 mod 7
olarak tanımlansın. Başlangıç değeri olarak
Kaplumbağa : f(1)
Tavşan : f(f(1))
değerleri ile başlıyor olsun. Bu durumda :
Kaplumbağa :5
Tavşan :3
değerini alacaktır.
Bulunan değerlerin tekrarlanması ile
Kaplumbağa : f(5)
Tavşan : f(f(3))
işlemini yapacak ve bu işlemlerin tekrarı aynı olana kadar devam edecektir.
K T
---
5 3
3 0
4 1
0 3
2 0
1 1
Yukarıda görüldüğü üzere kaplumbağa fonksiyonu bir kere işletirken tavşan iki kere işletmektedir. En nihayetinde aynı değerleri göstermesinden de anlaşılacağı üzere fonksiyonumuz dairesel bir fonksiyondur ve ürettiği sayıları tekrar eder.
Bu yaklaşım, hafızanın verimli kullanılmasını amaçlamaktadır. Yani bir dairenin yakalanması için geçilen bütün düğümler ve ya fonksiyon sonuçları bir yerde tutulup aynı değerden geçilip geçilmediğine bakılabilir. Ancak tahmin edileceği üzere bu işlem en kötü ihtimalde veri yapısında bulunan bütün sayıların ikinci bir yerde tutulması ile sonuçlanacak ve hafıza kullanımı artacaktır.
Tavşan ve kaplumbağa algoritmasında bunun tersine 2 gösterici (pointer) yeterlidir. Ancak bu sefer de işlem süresi uzamaktadır. Yukarıdaki örneklerde de görüleceği üzere aynı dairede birden fazla kere dönülmesi gerekebilmektedir.
Ayrıca karmaşık grafiklerde doğru yola karar verilmesi farklı bir problemdir. Örneğin bir ağaç üzerindeki dairenin yakalanması işleminde ağaçtaki yol ayrımlarının seçilmesi farklı bir problem halini alır.