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.