Arama Algoritmaları ve Uygulamaları

• Arama algoritmaları farklı alanlarda kullanılmaktadır.

Planlama

• Problem, masadaki küpleri mevcut konumlarından istenen konumlara taşımaktır.
• Olası hareketler arasında küpü tutmak, yere koymak veya başka bir küpün üzerine yerleştirmek bulunur.
• Çözüm, bu hareketlerin belirli bir sırayla uygulanmasını gerektirir.

Robot Yol Planlama

• Amaç, bir robotun başlangıç noktasından hedef noktasına ulaşmasını sağlamaktır.
• Robotun hareketleri sola, sağa, aşağıya veya yukarıya doğru olabilir.
• Her hareketin maliyeti farklı olabileceği için en az maliyetli hareket dizisini bulmak önemlidir.

Cin Ali Nehirde

• Hedef, Ali'nin bir sandalla kurt, keçi ve kabağını nehrin karşısına güvenli bir şekilde geçirmesidir.
• Sandal, Ali ile birlikte sadece bir nesneyi taşıyabilir.
• Kurt-keçi veya keçi-kabak ikilileri yalnız bırakılmamalıdır, aksi takdirde istenmeyen sonuçlar doğabilir.

Problemin Gösterimi

• İfade edilmesi gerekenler arasında 4 nesnenin (kurt, keçi, kabak, Ali) pozisyonu bulunur.
• Nesneler kuzeyde (N) veya güneyde (S) olabilir.
• Sandalın pozisyonu Ali ile aynı olduğundan ayrıca belirtilmesine gerek yoktur.
• Her bir nesnenin pozisyonu bir harf ile ifade edilebilir.
• Başlangıç ​​durumu (S, S, S, S) olup hedef durumu (N, N, N, N)'dir.
• Kurt ve keçinin veya keçi ve kabağın yalnız bırakılması yasaktır.

Operatörler

• Eylemler veya hareketler, durumları birbirine dönüştüren operatörlerdir.
• Örneğin, keçiyi kuzeye taşımak bir operatördür.
• Başlangıç durumu keçinin güneyde olması, bitiş durumu ise keçinin kuzeyde olmasıdır.
• Diğer nesnelerin yerinin önemi yoktur.
• Değişkenler kullanılarak kural sayısı azaltılabilir.
• "Move(Goat, North)" operatörü (S, ?wolf, S, ?cabbage) durumunu (N, ?wolf, N, ?cabbage) durumuna dönüştürür.
• Her nesnenin iki yerde olabilmesi nedeniyle toplam 2⁴ = 16 durum vardır.

Su Bidonları Problemi

• Amaç, 3 ve 4 galonluk iki bidon kullanarak 4 galonluk bidona tam olarak 2 galon su koymaktır.
• Sınırsız bir su kaynağı mevcuttur.
• (x, y) gösterimi kullanılarak durum ifade edilir. x: 4 galonluk bidondaki su miktarı, y: 3 galonluk bidondaki su miktarıdır.
• Başlangıç durumu (0, 0) ve hedef durumu (2, n) olarak belirtilir.

Su Bidonları Problemi için Operatörler

• 4 galonluk bidonu pompa ile doldur (if x < 4).
• 3 galonluk bidonu pompa ile doldur (if y < 3).
• 4 galonluk bidonu yere boşalt (if x > 0).
• 3 galonluk bidonu yere boşalt (if y > 0).
• 4 galonluk bidon dolana kadar 3 galonluk bidondan su doldur (if x + y ≥ 4 ve y > 0).
• 3 galonluk bidon dolana kadar 4 galonluk bidondan su doldur (if x + y ≥ 3 ve x > 0).
• 3 galonluk bidondaki suyun tamamını 4 galonluğa boşalt (if x + y ≤ 4 ve y > 0).
• 4 galonluk bidondaki suyun tamamını 3 galonluğa boşalt (if x + y ≤ 3 ve x > 0).

Su Bidonları Problemi için Bir Çözüm Örneği

• Başlangıç: 4 galonluk bidonda 0, 3 galonluk bidonda 0 (kural 2 uygulanır).
• Adım 1: 4 galonluk bidonda 0, 3 galonluk bidonda 3 (kural 7 uygulanır).
• Adım 2: 4 galonluk bidonda 3, 3 galonluk bidonda 0 (kural 2 uygulanır).
• Adım 3: 4 galonluk bidonda 3, 3 galonluk bidonda 3 (kural 5 uygulanır).
• Adım 4: 4 galonluk bidonda 4, 3 galonluk bidonda 2 (kural 3 uygulanır).
• Adım 5: 4 galonluk bidonda 0, 3 galonluk bidonda 2 (kural 7 uygulanır).
• Hedef: 4 galonluk bidonda 2, 3 galonluk bidonda 0.

8-Puzzle

• Amaç, 8 adet sayının belirli bir düzende sıralanmasıdır.
• Karmaşıklığı azaltmak için taş hareketleri, boş karenin hareketleri olarak temsil edilebilir.
• Operatörler: Boş kareyi sola (L), sağa (R), yukarıya (U) veya aşağıya (D) hareket ettirmek. Her operatörün maliyeti 1'dir.
• 4 hareket ve 8 sayı olduğundan toplamda 32 operatör vardır. Ancak bazı hareketler aynı sonucu verdiği için aslında 4 operatör yeterlidir.

8-Puzzle Arama Ağacı

• 22 derinlik ve ortalama 2.67 dallanma faktörü ile 2.7 milyar duruma bakılması gerekir.
• Ortalama adım sayısı 22 ve ortalama dallanma sayısı 2.67'dir.
• Tekil olmayan 2.7 milyar durum vardır.

Arama Algoritmaları için Tanımlar

• Durum uzayı (State Space, Search Space, Search Tree): Durumları, geçişleri, geçiş parametrelerini ve kısıtları gösteren bir graf/ağaçtır.
• Operatörler, durumlar arası geçişleri sağlarlar.
• Başlangıç durumu (S₀), aramanın başladığı durumu ifade eder.
• Hedef durumu ({G}), aramanın bittiği durumu ifade eder.
• Maliyet (Cost), bir operatörü uygulamanın maliyetidir.
• Çözüm yolu (solution path), başlangıç durumundan hedef duruma giden yoldur.
• Optimum yol (Optimal path), en düşük maliyetli çözüm yoludur. Birden fazla optimum yol olabilir ve maliyetleri eşit olmalıdır.

Arama Neden Zor Olabilir?

• Bir durumdan gidilebilecek durum sayısı veya dallanma sayısı (b) = 10 olsun.
• Saniyede işlenen durum/node sayısı 1000 olsun.
• Bir durum/node için tutulan bellek miktarı 100 bytes olsun.
• Çözümün derinliği arttıkça işlenen durum sayısı, zaman ve bellek ihtiyacı hızla artar.

Arama Algoritmaları / Stratejileri

• Arama stratejileri, bir durumdan diğerine giderken gidilecek durumun olası gidilebilecek durumlar arasından nasıl seçildiğini belirler.
• Stratejiler şu boyutlarda değerlendirilir:
  • Tamlık (Completeness): Bir çözüm varsa mutlaka bulması.
  • Zaman Karmaşıklığı (Time Complexity): Aramanın alacağı süre.
  • Hafıza Karmaşıklığı (Space Complexity): Arama için gereken hafıza miktarı.
  • Optimumluk (Optimality): İlk bulunan çözümün en düşük maliyetli çözüm olması.
• Kullanılan terimler:
  • b: Maksimum dallanma sayısı.
  • d: En az maliyetli çözümün derinliği.
  • m: Arama uzayının maksimum derinliği (bazen ∞).

Kör/Mekanik/Bilgisiz/Blind/Uninformed Arama Stratejileri

• Enlemesine Arama / Breadth-first search
• Düşük Maliyetli Arama / Uniform cost search
• Derinlemesine Arama / Depth-first search
• Sınırlı Derinlikte Arama / Depth-limited search
• Artan Derinlikli Arama / Iterative deepening search
• Çift Yönlü Arama / Bidirectional search

Enlemesine Arama (Breadth-First Search)

• Ağaç veya durumlar başta mevcut değildir, zamanla oluşur.
• Çözüm, bir durum sırasıdır, ancak durum açma sırası farklı olabilir.
• Enlemesine aramayı gerçekleştirmek için kuyruk (ilk giren ilk çıkar) kullanılır.
• Olası ihtimaller baştan çekilir ve sonuna eklenir.

Enlemesine Aramanın Analizi

• Tamlık: Eğer b sonlu ise evet.
• Zaman: 1 + b + b² + b³ + ... + bᵈ = O(bᵈ)
• Bellek: O(bᵈ) (her node hafızada).
• Optimumluk: Her adımın maliyeti eşitse evet.
• Bellek, zamandan daha önemli bir problemdir.
• 4 adımda ulaşılan çözümün maliyeti 2 adımda ulaşılandan daha az olabilir.
• Her adımın maliyeti eşit ise en az adımlı çözüm optimum olacaktır.

Düşük Maliyetli Arama (Uniform Cost Search)

• Enlemesine aramaya benzer.
• Kökten itibaren toplam maliyeti en az olan düğümü seçer ve genişletir.
• Tüm maliyetler eşitse enlemesine aramanın aynısıdır.

Düşük Maliyetli Aramanın Analizi

• Tamlık: Eğer b sonlu ve maliyet > 0 ise evet.
• Zaman: O(bᵈ)
• Bellek: O(bᵈ)
• Optimumluk: Tüm maliyetler pozitif ise evet.
• Bellek, zamandan daha büyük problemdir.
• Bütün maliyetler eşitse enlemesine aramanın aynısıdır.
• Maliyetler eşitse en az adıma sahip olan/kökene en yakın olan seçlir.

Derinlemesine Arama (Depth-First Search)

• Stack (son giren ilk çıkar) kullanılarak gerçekleştirilir.

Derinlemesine Aramanın Analizi

• Tamlık: Sonsuz derinlikli/loop içeren uzaylar için Hayır, algoritma tekrarı önlüyorsa Evet.
• Zaman: O(bᵐ), m > d ise çok kötü.
• Çözümler uzayda yoğunsa enine aramadan hızlı olabilir.
• Space: O(bm), lineer!
• Optimum mu? Hayır.

Sınırlı Derinlikte Arama (Depth-Limited Search)

• Derinlemesine aramanın derinlik sınırlanmış halidir (l).
• L derinliğindeki nodeların genişlemesine izin vermez.
  • Tamlık: L > d ise evet.
  • Zaman: b^L
  • Space: b*L
  • Optimum mu? Hayır.

Artan Derinlikli Arama (Iterative Deepening Search)

• Sınırlı derinlikte aramanın derinlik limiti (l) 0’dan X’e kadar artırılmasıdır.
• Her derinlik limitinde kökten aramaya yeniden başlar.

Artan Derinlikli Arama vs Sınırlı Derinlikte Arama

• d derinlikli ve b dallanma sayılı uzayda üretilen toplam durum/düğüm/node sayıları:
  • NDLS = b⁰ + b¹ + b² + … + bᵈ⁻² + bᵈ⁻¹ + bᵈ
  • NIDS = (d+1)b⁰ + d b¹ + (d-1)b² + … + 3bᵈ⁻² + 2bᵈ⁻¹ + bᵈ
• IDS'de (Iterative Deepening Search) her düğümden birden fazla kez geçilir.

Artan Derinlikli Aramanın Analizi

• Tamlık: Evet.
• Zaman: (d+1)b⁰ + d b¹ + (d-1)b² + … + bd = O(bd)
• Space: O(bd)
• Optimum mu? Evet, eğer tüm maliyetler eşit ise köke yakın çözümü ilk bulur.

İki Yönlü Arama (Bidirectional Search)

• İleri ve geri aramaların her biri sadece yarım yol gider. Enlemesine arama yapılır (Breadth-First Search).
• b:10, d:6 için her bir yön 3 derinliğinde olur ve oluşturulan düğüm sayısı 2,222'dir. Genişlik öncelikli (enlemesine) aramada bu sayı 1,111,111 olur.
• Tamlık: Evet.
• Zaman: O(bd/2)
• Space: O(bd/2)
• Optimum mu? Eğer tüm maliyetler eşitse, evet.

Enlemesine Arama Algoritması

• Kuyruk = [kök durum]
• Bulundu = FALSE
• While (kuyruk <> boş) and (bulundu = FALSE):
• Kuyruktan ilk durumu (N) çek
• Eğer N hedef durumsa, bulundu = TRUE
• N'den gidilebilecek tüm durumları kuyruğun sonuna ekle

Düşük Maliyetli Arama Algoritması

• Kuyruk = [kök durum]
• Bulundu = FALSE
• While (kuyruk <> boş) and (bulundu = FALSE):
• Kuyruktan ilk durumu (N) çek
• Eğer N hedef durumsa, bulundu = TRUE
• N'den gidilebilecek tüm durumları kuyruğun sonuna ekle
• Kuyruktaki durumları kökten maliyetlere göre küçükten büyüğe sırala

Derinlemesine Arama Algoritması

• Stack = [kök durum]
• Bulundu = FALSE
• While (stack <> boş) and (bulundu = FALSE):
• Stack'ten ilk durumu (N) çek
• Eğer N hedef durumsa, bulundu = TRUE
• N'den gidilebilecek tüm durumları stack'in başına ekle

Tekrarlayan Durumlar

• A → D, D → E, E → A,F adımlarını izleyen bir derinlemesine arama örneği verilir.
• Yeni durumlar eklenmeden önce daha önce ziyaret edilip edilmediği kontrol edilir.

Arama Algoritmalarının Karşılaştırılması

• DFS (Derinlemesine Arama):
  • Az bellek gereksinimi vardır (lineer).
  • Döngü içeren uzaylarda sonsuza dek çalışabilir.
  • Optimum çözümü garanti edemez.
  • Hafıza gereksinimi derinlikle üssel büyür.
• BFS (Enlemesine Arama):
  • Optimum çözümü bulur.
  • Döngülerden kurtulabilir.
  • Hafıza gereksinimi derinlikle üssel olarak büyür.
• IDS (Artan Derinlikli Arama):
  • Lineer hafıza gereksinimine sahiptir.
  • Döngülerden kurtulabilir.
  • Aynı şeyi tekrar tekrar dolaştığı için zaman kaybı vardır.
  • Optimum çözümü garantiler.

Stratejilerin Kör Arama Kriterlerine Göre Analizi

• Kör arama stratejileri; zaman, bellek, optimal çözüm ve tamamlanma kriterlerine göre karşılaştırılır.

Uygulama örneği

Olası Dünyalar

• Her gün iki seçenekli kararlar verildiğinde karar etkisine göre iki olası dünyadan birinde yaşanır.
• 32 gün sonra yaklaşık 4.3 milyar olası dünyadan birinde yaşanır.
• Faktörler: Doğumdan itibaren geçen zaman, başkalarının kararları, ikiden fazla seçeneği olan durumlar.