Yol Bulma Algoritmalarına Giriş (Bilmeyenler İçin) [ ÇEVİRİ ]

Arama metodları (Search methods) her problem için harika çözümler olmayabilir ancak kreatif yöntemlerle ve uygulamalarla pek çoğunu çözebilirler.Peki arama algoritmaları bir çözüm ise , hangilerini kullanırsınız ? Hangi method bir çözüm bulmayı garanti eder? Hangisi en verimlisi?

Aşağıdaki psuedocode ağacın / ağ aramanın en temel biçimini temsil eder.Sezgisellik veya varsayımlar içermez.Tartışılan arama metodlarının her birisi gösterilebilecek şekilde değiştirilecektir.

Pseudocode(Sözde kod):

Aşağıdaki koşulların sağlandığı varsayılarak

  • Ağacın veya ağın başlangıç düğümü (Start Node) ,  S ile gösterilecek
  • Hedef düğüm (Goal Node) , G ile gösterilecek

Ayrıca izlenecek yolları içeren ağacın veya ağın bulunduğu da varsayılır.(Bu yöntem Dijkstra  algoritmasına benzer türdedir.Ancak okunabilir olması için metin şeklinde yazılmıştır.)

  • Bir P listesi oluştur
  • P’ye bir eleman vererek ,başlangıç düğümü S’i ekle .
  • P’nin ilk yolu G ile bitene kadar , veya P boşalana kadar
    • P’den ilk yolu çıkar
    • X tane yeni yolu tüm komşulara bir adım uzat
    • Döngüye giren yolları at
    • Kalan her yolu P ‘ye ekle
  • Eğer G bulunduysa -> Başarılı , bulunmadıysa -> Başarısız

Basit bir örnek yapalım:

Her düğüm bir harf ile temsil edilir.Başlangıç düğümü (start node) S , hedef düğümü ( goal node) G ile gösterilir. A ve B düğümleri ara hedeflerdir.Her iki düğüm arasında yeni düğümlere ulaşabilmek için bağlantı olarak bir hat vardır.Dikkat edilirse her yol bir numaraya  , veya öneme/ağırlığa(weight) , sahiptir.Bu numaralar oraya ne kadar süreceği gibi , mesafe veya seyahat zorluğunu veya seyahat süresini gösterir(zor arazi örneği gibi).

Öncelikle , başlangıç düğümü( start node)  S ve hedef düğümü G ‘yi arama fonksiyonuna geçiyoruz .Listeye ilk S eklenir ve sonra ana döngüye gireriz(Yukarıdaki pseudocode da gördüğümüz gibi).

S eklendikten sonra fonksiyon tarafından döngüden dolayı listeden çıkartılıp bir adım sonrası için komşularına gidilir.Resimde de gördüğünüz gibi S ‘nin tek bir komşusu var o da A .Yani tek bir yol söz konusu  , S->A şeklinde , bu yolu ekledikten sonra listemizde tekrardan bir eleman var o da S->A (S’yi sildik unutmayın ).

Bir sonraki seferde döngü sayesinde , S->A çıkarılır ve bir adım daha genişletilir A’nın komşuları için .Bu sefer üç yol elimize geçer : S->A->S , S->A->B ve S->A->G . Dikkat edilirse S->A->S bir döngü (Yani S ‘den başlayıp tekrar S’e dönüyor ) ve onu atmak gerekir.Sonuç olarak S->A->S i atarsak elimizde S->A->B ve S->A->G kalacak ve bunları listeye alabiliriz.Şimdi liste iki tane eleman içerir.

Bir sonraki iterasyonda buna benzer işliyor : S->A->B yine çıkarılır ve komşularına genişletilir bu da bize : S->A->B->A ve S->A->B->G verir.Yine dikkat edilirse S->A->B->A bir döngü (S->[ A->B->A ] şeklinde) , bunu da eliyoruz.S->A->B->G  listeye eklendi.Liste şuan iki eleman içeriyor  : S->A->G ve S->A->B->G.

Sonunda bitti.Döngü koşulu kontrol eder yani S->A->G ‘yi. Sonunda G ile bittiği için ve hedefe vardığı için döngüden çıkacak yani atlayacak , bize “Başarılı” olarak geri döndürecek.

Bu en verimli method muydu?Duruma bağlı…Öyle görünüyor , yani demek istediğim iki tane gidilebilecek yol var : S->A->G  iki adıma sahip (S->A ve sonra A->G) ve S->A->B->G üç adıma sahip ( S->A , A->B ve B->G).En kısa yol olan en az adım olandır , değil mi?

Bu şart değil : eğer mümkün olan yolların numaralarını/önemini/ağırlığını (weight) toplarsan S->A->G için 7 ve S->A->B->G için 6 elde edersin.Yani , ikinci yol daha fazla adımı olsa da gerçekte daha kısadır. Hangisini isterseniz artık … Bu en basit method size en az adımı veriyor , ama en düşük numara toplamı/ağırlığı (weight) olmayabilir.

Keşfedilebilecek başka bir olasılıkta şudur:

S’den G’ye gitmesi mümkün olmayan bir yol olması.Bu durumda ne olacak?

  • S komşusu A’ya genişleyecek S->A
  • A komşusu B’ye genişleyecek S->A->B
  • S->A->B ‘den sonra B’nin genişleyebileceği komşusu yok , liste boş kalacak

 

Sonuç olarak liste boş kaldığı için döngü bitecek , G bulunabilir değil ve bize hata verecek.

Bir sonraki derslerde biraz daha karmaşıklaştırarak DFS(Depth First Search ) ,BFS (Breadth-first search) ve rastgele aramayı yapacağız.

 

 

 

Reklamlar

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap /  Değiştir )

w

Connecting to %s

Bu sitenin arkasında WordPress.com'un gücü var.

Yukarı ↑

%d blogcu bunu beğendi: