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.
kare uzaklık taksi uzaklığı şehir mesafe uzaklığı
yukarıdaki resimde yeşil yol iki nokta arasındaki öklit mesafesini vermektedir ve değeri alti kok iki‘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)

Yorumlar

  1. ali

    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

  2. Şadi Evren ŞEKER Article Author

    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

  3. ali

    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?

  4. Şadi Evren ŞEKER Article Author

    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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    
    ****
    ****
    ****
    ****
    Bu şekildeki 4x4 matrisi aşağıdaki şekilde 4'e 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

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


7 × = ondört