yazan: Şadi Evren ŞEKER
basitçe bir şehirde kare şeklindeki bloklar arasında yol alarak gidilebilecek mesafeyi verir. Diğer bir deyişle bir taksi kare şeklindeki apartmanlar arasında giderek ne kadar yol alır bunu gösterir.
aşğıdaki şekilde örnek kareler arası mesafe verilmiştir.
yukarıdaki resimde yeşil yol iki nokta arasındaki öklit mesafesini vermektedir ve değeri 
‘dir. diğer bütün yollar (sarı, mavi ve kırmızı) aynı uzunlukta olup ( 12 ) kare uzaklığını vermektedir.
Hesaplama yöntemi olarak verilen iki noktanın koordinatlarının farkının mutlak değeri kullanılabilir. Örneğin p(x,y) ve q(s,t) şeklinde iki nokta için:
Formülüze edilirse : Mesafe = |x-s|+|y-t| olarak gösterilir.
Yani yukarıdaki resimdeki ilk nokta (0,0) koordinatlarında, ikinci nokta ise (6,6) koordinatlarında olarak düşünülürse aradaki mesafe:
|0-6|+|0-6| = 12 olarak bulunur.
Diğer uzaklık ölçüm yöntemleri:
Öklit Mesafesi (Euclidean Distance, Euclidean Metric)
hocam 2 nokta arasındaki mesafeyi ölçmek için nasıl bir algoritma kurabiliriz.mergesort tek başına yeterli değil sanırım
iki nokta ile merge sort arasında nasıl bir ilişki bulunduğunu anlayamadım? Şimdi yorum yazdığınız bu yazıda iki farklı mesafe hesaplama yöntemi bulunuyor (öklit ve manhattan) bunlar için basit dört işlem yeterli (öklit için dört işleme ilave karekök almak belki).
Merge sort (birleştirme sıralaması) ise verilen sayıları sıralamak için (örneğin küçükten büyüğe doğru) kullanılan bir algoritma.
Yani aralarında doğrudan bir ilişki yok. Ancak bilgisayar bilimleri işte ne denebilirki bir yerlerde ilgisi kurulup, gerekmiş olabilir. Bu yüzden sorunuzu daha net sorarsanız yardımcı olmaya çalışayım.
Başarılar
hocam haklısınız anlatamadım
manhattan mesafe kullanarak O(nlogn) li bir algoritma geliştirmem gerekiyor.
algoritma belirteceğim noktalardan birbirine en yakın 2 noktayı bulması ve bu 2 nokta arasında ki sonucu ekrana basmalı
genel hatlarıyla
1.4*4 matris kur
2.noktaların mesafesini olç
3.en yakın mesafeli noktaları ekrana bas
şeklinde algoritma kurdum.
1.adım için 3 tane 2 boyutlu matris tanımladım
2.adım için brute-force algoritması kurdum ve merge sort ile mesafeleri ölçsem sonuç O(nlogn) time complexty li olur mu?
anladım, bu çözüme merge sort demeyelim. Aslında sizin niyetiniz böl fethet (divide and conquere) yaklaşımı uygulamak. Merge sort da aynı yaklaşımı kullanıyor sizin durumunuzda sıralanacak birşey de yok zaten. Siz mesafe ölçümlerini her seferinde matrisi ikiye bölüp sonra ölçüp sonra da birleştirerek yapabilirsiniz.
Örneğin aşağıdaki şekilde matrisi bölebilirsiniz:
sonra bu 4 alt matrisi yeniden işleyip (bölüp ölçüp) birleştirebilirsiniz.
Örneğin matris çarpımını anlattığım bir yazı aşağıda var:
http://www.bilgisayarkavramlari.com/2010/10/07/parcala-fethet-yaklasimi-ile-matris-carpimi/
Anladığım kadarıyla yapmak istediğiniz buna benzer bir durum.
Başarılar