Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde özlelikle graf teorisinde (graph theory) kullanılan ve bir döngüyü (cycle) algılamaya yarayan algoritmadır. (cycle detection).

Basitçe tavşan ve kaplumbağa algoritmasından (hare and tortoise algoritm) esinlenmiştir. Floyd algoritması olarak da isimlendirilen tavşan ve kaplumbağa algoritmasından farklı olarak tavşan, kaplumbağanın iki misli değil 2 üzeri adımla hareket etmektedir.

Yani kaplumbağa, tavşan 2′nin bir kuvveti olan adım attığında hareket etmekte, bu zamana kadar beklemektedir.

Örneğin aşağıdaki dairenin Brent algoritması ile nasıl çözüldüğünü görmeye çalışalım:

Başlangıç değeri olarak A düğümünden iki göstericinin (pointer) başladığını kabul edelim. Bu durumda başlangıçtaki tavşan ve kaplumbağanın şekli aşağıdaki gibi olacaktır :

Kaplumbağa tavşanı beklemektedir. Tavşan birer birer hareket etmekte, şayet hareket ettiği değer 2 üzeri bir değer olursa kaplumbağa da hareket etmektedir. Aynı düğüme geldiklerinde daire bulunmuş demektir.

Yukarıdaki şekil için tavşan ve kaplumbağanın dolaştıkları düğümleri sıralayacak olursak:

K T

—

A B

A C (C tavşanın geldiği 2. düğüm olduğu için kaplumbağa hareket eder)

B D

B E (E  tavşanın 4. adımda geldiği düğüm olduğu ve ikinin kuvveti olduğu için kaplumbağa hareket eder)

C F

C A

C B

C C (C. tavşanın 8. adımda geldiği düğüm olduğu için kaplumbağa hareket edecektir ancak daire bulunmuştur)

Yukarıdaki örnekte iki gösterici de C düğümünde buluşmaktadır dolayısıyla daire yakalanmıştır.

151 views