Arama algoritmaları yapay zeka uygulamalarında önemli yere sahiptirler. Birçok problemin çözümünde arama algoritmaları hızlı ve etkili çözümler sunmaktadır. Yapay zeka problemlerinin çözümünde arama evrensel bir tekniktir.

Bir problem için doğru arama stratejisini seçmek gerekir. Burada arama stratejilerinden hangisini seçeceğini belirlerken aşağıdaki kriterlere bakmak gerekir:

  • Tamlık-Bütünlük(Completeness): Problemin bir çözümü olduğunda seçilecek olan strateji bu çözümü bulabilecek mi?
  • Zaman Karmaşıklığı(Time Complexity): Bir çözüm bulmak ne kadar zaman alacak?
  • Uzay Karmaşıklığı(Space Complexity): Aramayı yapmak için ne kadarlık bir hafıza(memory) gerekli olacak? Rekürsif olan algoritmalarda bir önceki durum saklanacağından dolayı problemin çözümü için gerekli hafıza alanı rekürsif olmayan algoritmalara göre daha  fazla olacaktır.
  • Optimalite-Optimallık-Eniyileme(Optimality): Farklı çözümler mevcut iken seçilen stratejinin çözümü optimal olan mı?
  • Körüne Arama-Bilgisiz Arama(Blind Search): Burada sonuca varmak için içinde bulunan durumun sonuç ile arasındaki adım sayısı veya mesafesinin bilinmemesidir. Yani çözüme ne zaman varılacağı bilinmemektedir. Burada sadece bilinen şey içinde bulunan durumun hedef durum olup olmadığıdır.

Enine Arama (Breadth-First Search)

Yaygın olan bir arama stratejisidir. Bu stratejide bulunan durum yani düğüm başlangıçta kök düğüm olduğundan ilk önce kök düğüm genişletilir. Genişletmekten kasıt kök düğümden giden bütün yolların ziyaret edilmesidir. Böylece kök düğümün bütün komşuları keşfedilmiş olur. d derinliğinde bulunan tüm düğümler  arama ağacında d+1 derinlikte bulunan düğümlerden önce açılırlar(genişletilirler). Bir problemin çözümü varsa enine arama algoritması çözümü garanti eder. Eğer birkaç çözüm var ise en üstte olan yani ilk bulunan çözümü çözüm olarak kabul eder. Yukarıdaki kriterlere göre enine arama tamdır, çünkü çözüm var ise bulmayı garanti eder.

Enine arama algoritması, problemin çözümü daha  derinlerde ise verimsiz bir algoritmadır. Çünkü açılan düğüm sayısı artacaktır. Çözümün derinde olması dallanma etmeni(branching factor) olarak bilinmektedir. Başlangıç düğümü de dahil olmak üzere her düğümün b sayıda çocuğu olduğunu varsayalım. Kök ilk genişletildiğinde b sayıda dal olacaktır bir sonraki derinlikte  dallanma olacaktır. Bu şekilde d. derinlikte b üzeri k olacaktır.

Toplamda değerlendirilmesi gereken düğüm sayısı=1+b+b²+b³… olacaktır. Bu da zaman karmaşıklığı bakımından önemlidir.

Örnek olarak eğer her düğümün dallanma sayısı  b=10 alırsak ve derinliği de d=10 alırsak,

toplam düğüm sayısı=10 000 000 000

gereken zaman=128 gün

gerekli bellek=1 terabyte

Yukarıdaki örnekte de görüldüğü gibi enine arama algoritması dallanma faktörüne göre verimli olup olamadığı belli olmaktadır.

Algoritmanın adımları

  1. Öncelikle bir başlangıç düğümü seçilir ve bu düğüm işaretlenir.
  2. Bu düğümün komşuları sırasıyla bir K listesine yazılır. Bu K listesi komşulukları tutan bir listedir.
  3. Bu komşu düğümler teker teker ziyaret edilir ve işaretlenerek Z listesine eklenir. Z listesi ziyaret edilen düğümleri tutan listedir.
  4. K listesindeki ilk düğüm alınarak işaretlenir ve K listesinden silinir.
  5. Silinen düğümün komşuları  K listesine eklenir. Bu ekleme yapılırken eğer eklenecek düğüm Z listesinde varsa yani daha önce ziyaret edilmişse eklenmeyecektir.
  6. Silinen düğümün ziyaret edilen düğümleri Z listesine eklenir (var olanlar eklenmeyecek).
  7. Bu şekilde K listesindeki tüm düğümler silininceye kadar devam edilir.

Derinine Arama(Depth-First Search)

Derinlik öncelikli aramada, arama ağacı fazla dallanmadan kökten gidilebilecek en uzak düğüme kadar ilerlenir. Burada kök olarak herhangi bir düğüm alınabilir. Kök düğümden yaprak düğüme giden, tek yol gibi düğümler her iterasyonda saklanır ve düğümler doğrusal bir yapıda depolanırlar. Bundan dolayı kullanılan veri yapısı LIFO Last Input First Out(son giren ilk çıkar)’dur. Bu şekilde kökten yaprağa tek yol olarak tutulmasından dolayı bellek gereksinimi oldukça makuldür.

Dallanma faktörüne baktığımızda ise b dallanma sayısı ve d derinliği için gerekli bellek alanı b*d olacaktır. Enine aramaya göre ne kadar verimli olduğu görülmektedir.

Derinine aramada olası sorunlar problemin çözümünde gidilen yanlış yolda sıkışıp kalmaktır. Birçok problemin sonsuz veya çok derin ağaçları olabilmektedir böyle durumlarda derinine arama uygun bir çözüm bulamayacaktır. Bu şekilde arama bir önceki duruma dönmeden sürekli devam edecektir, hatta bir önceki seviyede bir çözüm bulunmuşsa bile yine devam edecektir. Böylece derinine arama algoritması bu tür sonsuz veya çok derin ağaçlarda sonsuz döngüye girer ve asla bir çözüme ulaşamaz çözüm bir önceki seviyede olsa bile. Bir diğer durum ise algoritma bir çözüm bulabilir ama bu optimal çözüm olmayabilir. Yani bir üst seviyedeki çözüm ile en son bulunan çözüm arasında zaman, bellek bakımından farklar olacaktır. Derine arama yukarıdaki kriterlere göre tam değildir. Rekürsif çalışan bir fonksiyon olarak yazılabilir.

Algoritmanın adımları

  1. Başlangıç düğümü seçilir ve ziyaret edilir.
  2. Başlangıç düğümünün ziyaret edilmemiş komşularından bir tanesi seçilir ve ziyaret edilir.
  3. Bu ziyaret edilen komşunun da komşularında gidilir ve ve ziyaret edilmeyen bir komşusu seçilerek ziyaret edilir.
  4. Bu şekilde sürekli derine inilir, en son derinlikte ziyaret edilmeyen düğüm kalmayınca tekrar yukarı çıkılır ve işlemler aynı şekilde devam edilir.

Özet olarak; verilen tüm düğümler gezilecek şekilde, sırayla ziyaret edilir, gezilmemiş bir komşusu var ise ona gidilir ve daha sonra sıradaki kendi komşusundan önce komşusunun komşusuna gidilir böyle devam eder.

Çift Yönlü Arama(Bidirectional Search)

Aramaya başlangıç durumundan ileri doğru ve sondan geriye doğru arama yapar belirlenen bir durumda ikisi karşılaşana kadar devam eder. Baştaki arama ve sondaki arama her birisi toplam yolun yarısını almış olur.

Tek Maliyetli Arama(Uniform Cost Search)

Bir düğüme olan yolları maliyetlerine göre artacak şekilde sıralar. Genişlemeyi yani komşuları ziyaret etmeyi maliyeti en az olan, en yakın olanı seçer ve genişlemeyi bu düğümle yapar.

Eğer tüm yolların maliyeti aynı ise enine arama gibidir. Yolları, maliyeti artan şeklinde genişletir(ziyaret eder).

Sezgisel Arama Stratejileri(Heuristic Search Strategies)

Büyük boyutlu problemleri büyük sayılabilir olası durumlarla çözmek ve algoritmaların verimliliğini arttırmak için probleme özgü bilgilerin eklenmesi gerekir.

Sezgisel Değerlendirme İşlevleri

Bu işlevler iki durum arasındaki en uygun maliyetli yolu hesaplarlar. Bir sezgisel işlev puzzle oyunlarında her karenin gitmesi gereken hedef durum için hamle sayısını ve tüm karelerin toplam gerekli hamle sayısını hesaplar.

Saf Sezgisel Arama(Pure Heuristic Search)

Bu yöntem düğümleri sezgisel değer sıralarına göre genişletir. İki tane liste oluşturur biri kapalı genişletilmiş düğümler için, diğeri de açık genişletilmemiş düğümler için.

Her iterasyonda minimum sezgisel değere sahip olan düğüm genişletilir, tüm çocukları oluşturulur ve kapalı listeye eklenir. Sonra çocuk düğümlere sezgisel işlev uygulanır ve sezgisel değerlerine göre açık listeye eklenirler. Kısa olan yollar tutulur, uzun olan yollar ise silinir.

A* Algoritması

Maliyeti fazla olan yolların genişletilmesini engeller, sadece en faydalı olabilecek yolları genişletir.

Başlangıç s düğümünden x düğümüne kadar olan yolu g(x) ile x düğümünden ise f hedef düğümüne olan yol değerini h(x) ile ifade edersek bu algoritma için aşağıdaki bağıntı elde edilir.

f(x)=g(x)+h(x),

g(x) x durumunun gerçek olan o anki değeri,

h(x) ise x düğümünden çözüme olan gidişlerin sezgisel değeridir.

f(x) ise toplam n yolun içinden hedefe olan toplam tahmini maliyettir. Artan sırada öncelikli kuyruk veri yapısı uygulanır.

Açgözlü En İyi İlk Arama(Greedy Best First Search)

Hedef düğüme en yakın olduğu tahmin edilen düğümü genişletir. Düğümleri f(x)=h(x) baz alarak açar. Yani toplam maliyet sezgisel(tahmini)’dir. Öncelikli kuyruk veri yapısı uygulanır.

Yerel Arama Algoritmaları

Bu algoritmalar olası bir çözümden başlarlar ve çözümü diğer komşuya taşırlar. Bu algoritmalar sonlanmasalar da yine geçerli bir çözüm mevcuttur, çünkü başlangıçtaki olası çözüm taşınır.

Tepe-Tırmanma Araması(Hill-Climbing Search)

İteratif bir algoritmadır probleme yönelik keyfi bir çözüm alınır ve her seferinde tek bir unsuru aşamalı olarak değiştirerek en iyi çözümü bulmaya çalışır. Eğer değişim daha iyi bir çözüm üretirse yeni çözüm olarak alınır. Bu süreç başka değişimler olmayana kadar devam eder.

Yerel Işın Arama(Local Beam Search)

Bu algoritma, herhangi bir zamanda verilen k durum sayısını tutar. Başlangıçta bu değerler rastgele üretilir. Bu k durumun bir sonraki yeni değerleri yardımcı bir fonksiyonla hesaplanır. Eğer yeni değerlerden herhangi biri yardımcı fonksiyonun maksimum değeri ise algoritma durur.

Diğer türlü bu  k durum bir havuzda toplanır(havuzda başlangıçtaki k durum ve sonrasında yardımcı fonksiyonla oluşturulan k durum daha yani 2k durum vardır) ve sayısal olarak sıralanır. En yüksek k durum yeni başlangıç durumu olarak seçilir.Bu süreç maksimum değere ulaşan kadar devam eder.

Gezgin Satıcı Problemi(Travelling Salesman Problem)

Bu algoritmada satıcı herhangi bir şehirden başlayarak tüm şehirlere yalnız bir kez uğrayarak yeniden geri dönmektedir.Şehirler arası uzaklıklar verildiğinde minimum uzunluklu yolun bulunması istenmektedir.

n şehir sayısı olduğunda (n-1)! olası çözümü bul,

(n-1)! olası çözümün her birinin minimum yol maliyetlerini bul,

içlerinde minimum olanı tut.