Yapay Zeka‘da arama, problemleri çözmenin önemli bir yoludur. Bir arama problemi, başlangıç durumundan hedef duruma ulaşmak için hangi adımların atılması gerektiğini belirlemeyi içerir. Bu yazıda, arama problemlerinin nasıl formüle edildiği ve çeşitli arama algoritmalarıyla nasıl çözüldüğü ele alınacaktır.

Arama Problemleri

Bir arama problemi şu altı bileşenle tanımlanabilir:

1. Durum Tanımı: Ajanın içinde bulunduğu durumun tanımı.
2. Başlangıç Durumu (initial state): Ajanın başladığı durum.
3. Aksiyonlar: Ajanın mevcut durumda yapabileceği eylemler.
4. Geçiş Modeli (transition model): Aksiyonların, ajanı bir durumdan diğerine nasıl geçirdiğini tanımlar.
5. Hedef Testi (goal test): Bir durumun hedef durum olup olmadığını belirler.
6. Yol Maliyeti Fonksiyonu (path cost): Bir yolun her adımına bir maliyet atar.

Örnekler

• Romanya Problemi: Arad şehrinden Bükreş’e ulaşmak için en uygun yolu bulma problemi. 
  Initial state (başlangıç durumu): Arad
  Actions (aksiyonlar): Sibiu, Timisoara ve Zerind’e gidebilir.
  Transition (geçiş) modeli: Result(In(Arad),Go(Zerind) = In(Zerind) 
  Goal test: Bükreş’e ulaşmak
  Path cost (yol maliyeti): kilometre uzunluğu

  

• Elektrikli Süpürge Problemi: Ajanın kirli alanları temizleyerek tüm evi temizlemesi gereken problem. 
  Initial state: n lokasyonlu ortam için n.2^n mümkün durum
  Actions: sol, sağ, emmek
  Goal test: hiç kir kalmaması konumlarda
  Path cost: eylem başına 1 hareket

  

Durum Uzayı (State Space)

Arama problemlerinde durum uzayı, çevredeki tüm olası durumların bir matematiksel temsili olarak kabul edilir.

Bir arama durumu (search state) yalnızca planlama için gereken ayrıntıları tutar. Abstraction (soyutlama).

Problem: Yol belirleme
States: (x,y) konumları
Actions: yukarı, aşağı, sağa, sola
Successor: sadece yolu güncelleme
Goal test: is(x,y) = END

Problem: Tüm noktaların yenilmesi
States: {(x,y), dot booleans}
Actions: yukarı, aşağı, sağa, sola
Successor yolu güncelleme ve noktalar
Goal test: noktaların hepsinin false olduğu durum

Problem: Güvenli geçiş
Nasıl pacman diğer agentlar tarafından öldürülmeden geçiş yapar ?
Ajan pozisyonları: 120 pozisyon (10 sütün, 12 satır var 120 pozisyon yapar)
Yiyecek nokta sayısı: 30 adet
Hayalet (ghost) ajanların pozisyonları: 12 pozisyon 
Ajanların yönleri: yukarı, aşağı, sağa, sola
Kaç farklı dünya durumu vardır ?
 120 ajan pozisyonları * 2^30 yiyecek konfigürasyonu * 12^2  hayalet pozisyonu * 4 (gidilebilecek yön sayısı)
Tüm noktalar yenmesi için kaç durum vardır ?
120 * 2^30  

State Space Graphs

State Space Graphs, bir arama probleminin matematiksel sunumudur.

Nodes (düğümler) soyutlanmış (abstracted) dünya konfigürasyonlarıdır.
Arcs (yaylar) ardılları (eylem sonuçlarını) temsil eder.
Hedef testi (goal test) bir dizi hedef düğümüdür (belki sadece bir tane).
Bir durum uzayı grafiğinde (state space graph), her durum sadece bir kez gerçekleşir!
Tam grafiği bellekte nadiren oluşturabiliriz (çok büyüktür), ancak bu yararlı bir fikirdir.

Search Trees (Arama Ağaçları)

Bu yazıda, x x x hakkında bilgi verdim. 

Bir sonraki yazıda, xxx konusuna geçeceğiz.

KAYNAKÇA:
Berkeley CS188 Intro to AI — Course Materials