Yapay Zeka - Arama Algoritması

Öngörüsel (heuristic) arama işlemlerinden gerçekleştirmesi en kolay olanlardan birisi Best First Search ya da diğer adıyla Hill Climbing Search olarak adlandırılan bu arama stratejisidir. Hill Climbing algoritmasında arama işleminde o anda aktif olan düğüm genişletilir ve çocuk düğümler değerlendirilir. Bunlardan en iyi değerlere sahip olan düğüm bir sonraki genişletme işleminde kullanılmak üzere seçilir.

Arama işlemi çocukların hepsinden daha iyi bir duruma erişildiğinde sona erer. Bu sistemde hatalı öngörüsel (heuristic) değerler sonsuz yollara, dolayısıyla arama işleminin başarısızlıkla sonuçlanmasına neden olur. Bu nedenle bu algoritmanın başarısı için öngörüsel değerlerinin doğru belirlenmesi büyük önem taşır. Algoritmada önceki basamaklarla ilgili bilgi tutulmamaktadır dolayısıyla hata durumu ile karşılaşıldığında eldeki yanlış çözüm üzerinde bir düzeltme yapılabilmesi söz konusu değildir. Algoritma, tüm çocuklardan daha iyi durumdaki bir düğüme erişildiğinde sona erdiğinden yele maksimum noktaları da sorun yaratmaktadır. İyi mutlak açıdan en iyi olmak zorunda değildir. Hill Climbing algoritması yerel ve global maksimum arasındaki ayrımı yapamamaktadır. Algoritmamızda AÇIK olarak adlandıracağımız gidilebilecek durumların tutulduğu bir liste ve KAPALI olarak adlandırdığımız ziyaret ettiğimiz durumların tutulduğu bir liste kullanılmaktadır. Algoritma aşağıdaki gibidir.

Best First Search Algoritmasının Açık Metin Hali:

1. AÇIK listesine Start düğümünü ekle
2. KAPALI listesini boşalt
3. AÇIK listesinde eleman olduğu surece
4. AÇIK listesinin en solundaki elemanı listeden çıkart . Bu elemanı X olarak adlandıralım.
5. X'ın çocuklarını bul
6. X'in tüm çocukları için
6.1. Eğer child AÇIK ve KAPALI listesinde değil ise 
6.1.1. Child'e bir herustik değer ver ve AÇIK listesine ekle.
6.2. Child AÇIK Listesinde ise
6.2.1. Eğer daha kısa bir yol ile ulaşılmış ise AÇIK lisesindeki Child kayıdının Herustik değerini değiştir.
6.2.2. Child'ın ebeveyn bilgisini günceller.
6.3. Eğer child KAPALI listesinde ise
6.3.1. Eğer daha kısa bir yol bulunmuş ise KAPALI listesinden çıkartıp yeni bilgilere göre güncelleyip AÇIK listesine ekle.
7. X nodunu KAPALI listesine ekle
8. AÇIK listesini herustik değerlerine göre yeniden sırala (En iyi seçenek sola gelecek şekilde)

Best First Search Algoritmasının Arakod Hali:

Procedure best_first_search* (Hill Climbing Search)
Begin
  Open := [Start];
  Closed :=[];
  While open <> [] do Begin
    Remove the leftmost state from open, call it X;
    If  X =goal then return the return the path form the Start to X
    Else begin
      Generate children of X;
      For each child of X do
      Case
        The child is not on open or closed: Begin
          Assign the child a herustic value;
          Add the child to open
        End;
        The child is already on open:
          If the child was reached by a shorter path
          Then give the state on open the shorter path
        The child is already on closed:
        If the child was reached by a shorter path then Begin
          Remove the state from closed;
          Add the child to open
        end
      end;
      put X on closed;
      re-order states on open by heuristic merit (best leftmost)
    end;
  return failure
end.


Algoritma her iterasyonda AÇIK listesinden bir elemanı (anlık olarak en iyi -çözüme en yakın- olan elemanı) çıkartır. Eğer algoritma hedef şartlarına erişirse hedefe ulaşılmasını sağlayan yol bilgisini geri döndürür. Burada dikkat edilecek nokta algoritmanın her düğümün kendi (babası) ebeveyni hakkında bilgi içerdiğini kabul ettiğidir.

kaynak: www.yapay-zeka.org