Dinamik Programlama'da Hatırlama Metodu

Dinamik Programlama'da Hatırlama Metodu

Dinamik programlama bize her hangi bir problemin çözümünde klasik olarak kullandığımız algoritmalardan daha etkili algoritmalar oluşturmamızı sağlar.Memorize,Bottom-Up gibi bir çok yöntemle algoritmalarımızı geliştirebiliriz.Ben bu anlatımda Hatırlama* (Remember) yöntemini kullanarak fibonacci sayılarının nasıl daha etkili hesaplanabileceğini anlatacağım.

Öncelikkle bazı temel mantık öğelerini ve klasik algoritmamızın çalışma zamanından başlayalım;

F(1)=F(2) = 1

F(n) = F(n-1) + F(n-2) bu formüller fibonacci serisinin formülleştirilmiş halidir.

T(n) ise T (n-1)+ T(n-2) + O(1) e eşittir.Klasik impelementasonumuza bakarsak

Fib(n):

if n<=2 : f =1

else : f = fib(n-1) + fib(n-2)

return f

Yukarıdaki çözüm recursive şeklinde fibonacci sayılarının hesaplanmasını sağlayan algoritma.Biz bu algoritmayı çalıştırdığımızda programımız aşşağıdaki ağacın kollarındaki tüm elemanları hesaplayarak kökde duran sonucu bulmaya çalışıyor.

Görev ağacına baktığımızda aslında bazı değeri zaten önceden hesapladığınızı üst seviyeye geçerken boş yere aynı değeri hesapladığımızı görmüşsünüzdür hatta kökün sağındaki koldaki n-2 değerinin diğer sol kolun bir alt seviyesinde hesaplandığını görülüyor ,o halde bizim komple o sağ kolu hesaplamamız gereksiz.Peki bundan nasıl kurtulacağız ? Hatırlayarak ! . Her hesapladığımız değeri bir key-value sisteminde(programlama dillerine göre değişir) saklayarak boş hesaplamalardan kurtuluyoruz.Örneklemek gerekirse aşşağıdaki kodla ;

memo = {}

Fib(n):

   if n in memo return memo[n]

   if n<=2 : f=1

   else : f = Fib(n-1) + Fib(n-2)

   memo[n] = f

   return f

Peki bu çözümümüzün T(n)'ı kaça eşit derseniz .

Zaman = parçalanmış çözümler * zaman/parçalanmış çözümler zaman = zaman ? Yani yukarıdaki T(n-1)+T(n-2)+O(n) ? Tabikide hayır. Zaman/Parçalanmış çözümler kısmını biz hatırlama yöntemini kullanarak O(1) olarak hesaplıyoruz parçalanmış çözümlerde n e eşit olduğundan T(n) = O(n) oluyor.

*Farklı kaynaklarda Memorize,Remember,memoize şeklinde geçebilir bu kavram.

En Yakın Komşu Problemi Ve K-d Ağacı

En Yakın Komşu Problemi Ve K-d Ağacı

x ve y kordinatları düzleminde tüm noktalar x ve y olmak üzere iki kordinat değerine sahiptir.Birinci noktanın kordinatları x1,y1 ikinci noktanınkiler ise x2,y2 olmak üzere iki nokta arasındaki en yakın uzunluk kök içerisinde (x1-x2)^2 + (y1-y2)^2 olarak hesaplanır.K-d ağaçları sayesinde tüm noktaların aradığımız noktaya olan uzaklıklarını bu formülle hesaplayıp sıralama derdinden kurtulmuş oluyoruz.K-d ağacında x ve y kordinat değerlerine göre alandaki noktaları parçalara bölerek bir ağaç oluşturuyoruz.

Peki nedir bu k-d ağacı ve nasıl oluşturulup nasıl kullanacağız.K-d ağacı öncellikle bir BST(binary search tree,ikili arama ağacı)dir.Oluştururken yararlanacağımız kurala gelecek olursak;normal bst'lerde sayısal değer olarak büyüklük küçüklük durumuna bakardık burda da kordinatların değerine bakarak ağacı oluşturacağız ancak bir seviyede x kordinatını bir seviyede ise y kordinatını dikkate alacağız.Kök(root) seviyede x kordinatına bakılarak oluşturma işlemine başlarız bir örnek yapacak olursak.;

Ağaça yerleştirme sıralamam B,A,C,D,E olarak oldu ancak bu keyfi bir sıralamaydı siz istediğiniz sırayla oluşturabilirsiniz gerekli şartları sağlamak üzere ancak x kordinatı olarak en ortadaki kordinatı bulup kök kabul etmek ağacın daha dengeli olmasını sağlayarak çalışma zamanını iyileştirebiliriz.K-d ağacında arama,ekleme,silme işlemleri avarege case (ortalama zamanda)'de log(n) olarak ,worst case(en kötü durumda)'de n olarak çalışır.Aşşağıda örnek bir k-d ağacı ;

Peki en yakın komşu problemini nasıl çözeceğiz.Bu problemi k-d ağaçlarını kullanırken çözerken kullanacağımız algoritma yinelemeli(recursively) bir algoritmadır.İlk kök node'unu şampiyon ilan ederek algoritmamıza başlarız.Ardından aramamızı devam ettirerek sağ'da veya solda yinelemeli yaparak şampiyonları değiştirip en sondaki şampiyonu bularak noktamızı belirlemiş oluruz peki o an belirlediğimiz şampiyonun sağına'mı soluna mı gideceğiz buna karar vermek için geometriden bir örnekle açıklamak istiyorum aşşağıdaki resim aydınlatıcı olacaktır.

Resimdekileri açıklayayım.İlk olarak B'yi biz şampiyon ilan ettik , ardından rastgele olarak bu ağacın sol kolunda araştırma yapmaya başladık .Normalde yenilemeli olarak algoritmayı tüm ağaca uygulayacağımız için bunu rastgele olarak yaptık.Ardından baktık'ki yeni noktamız olan A aradığımız noktaya daha yakın.Şekilde yeşil noktalarla çizilen çizgiler B 'nin X eksenine göre A nın Y eksenine göre çizilmiş uzantıları.Bunları çizmemizin nedeni ise eğer A , B den daha büyükse A dan daha yakın bir nokta varsa onunda maviyle karalanmış olan bölgede olacağını anlatmaktır.Demekki bu noktalar B'nin kesinlikle solunda(x kordinatı değeri B'den daha küçük) ise demekki B'nin ağaçtaki sağ kolunu aramamıza gerek kalmadığını gösterir.Bu işlemleri sonuna kadar yaptığımızda C'nin en son şampiyonumuz olduğu açığa çıkar ve algoritmamız başarıyla sonuçlanmış olur.