Arama ve Problem Çözme
Arama ve problem çözme, yapay zekanın, görevleri durum veya konfigürasyon uzayının keşfi olarak formüle etme ve bir hedefe ulaşan eylem, atama veya hareket dizilerini bulma ile ilgilenen bir dalıdır.
Tanım
Arama tabanlı problem çözme, bir görevi başlangıç durumu, durumları dönüştüren bir dizi eylem, bir hedef testi ve bir yol maliyeti olarak temsil etmekte ve ulaşılabilir durumları sistematik olarak keşfederek, bir hedef durum (veya ona giden en düşük maliyetli yol) bulunana kadar çözmektedir.
Kapsam
Bu alan, problemlerin durum uzayları olarak formüle edilmesini ve bunları keşfeden algoritmaları kapsamaktadır: genişlik öncelikli ve derinlik öncelikli gibi bilgisiz (kör) arama; A* ve açgözlü en iyi-ilk gibi bilgili (sezgisel) arama; iki oyunculu oyunlar için rakip arama ve kısıt tatmini (constraint satisfaction). Problemlerin durumlar, eylemler ve hedef testleri olarak nasıl modellendiğini ve eksiksizlik, optimallik, zaman ve uzayın nasıl analiz edildiğini ele almaktadır. Arama sezgisellerinin veya değerlendirme fonksiyonlarının verilerden öğrenilmesi bu kapsamın dışındadır; bu konu ayrı bir makine öğrenimi alt alanına aittir.
Alt konular
Temel sorular
- Gerçek dünya görevi, durumlar, eylemler ve bir hedef testi ile bir durum uzayı olarak nasıl formüle edilmektedir?
- Bir arama algoritması ne zaman eksiksiz (bir çözüm varsa bulmayı garanti eden) ve optimal (en düşük maliyetli çözümü bulmayı garanti eden) olmaktadır?
- Sezgisel bir fonksiyon, optimalliği korurken aramayı hedefe doğru nasıl yönlendirmektedir?
- Durum uzayının kombinatoryal patlaması, budama veya bilgili sıralama ile nasıl kontrol edilebilmektedir?
- Bir rakip bazı hamleleri seçtiğinde arama nasıl değişmektedir?
Anahtar kavramlar
- durum uzayı
- arama ağacı ve arama grafiği
- bilgisiz (kör) arama
- sezgisel fonksiyon
- kabul edilebilirlik ve tutarlılık
- A* arama
- dallanma faktörü ve arama derinliği
- eksiksizlik ve optimallik
- kısıt tatmini (constraint satisfaction)
Temel kuramlar
- Kabul edilebilir sezgiseller ve A* optimalliği
- Bir sezgisel, hedefe olan gerçek maliyeti asla abartmazsa (kabul edilebilir ise), A* araması düğümleri f = g + h'nin en iyi-ilk sırasına göre genişletir ve optimal bir çözüm döndürmeyi garanti eder; tutarlılık ayrıca hiçbir düğümün yeniden genişletilmemesini garanti etmektedir.
- Bilgisiz ve bilgili arama arasındaki denge
- Kör stratejiler (genişlik öncelikli, tek maliyetli, derinlik öncelikli, yinelemeli derinleştirme) yalnızca düğüm sıralamasında farklılık gösterir ve alan bilgisi olmaksızın garantiler sunar; oysa kalan maliyetin sezgisel tahminleri, sezgisel kabul edilemez ise optimalliği kaybetme riskiyle birlikte keşfedilen alanı önemli ölçüde azaltabilmektedir.
- Problem formülasyonu durum-uzayı araması olarak
- Eylemlerle birbirine bağlanan durumlar üzerinde arama olarak ele alındığında çok çeşitli görevler çözülebilir hale gelmektedir; bu da durum temsilinin ve operatörlerin seçimini, dallanma faktörünü ve çözüm derinliğini belirleyen merkezi bir tasarım kararı haline getirmektedir.
Klinik önem
Arama, çok çeşitli pratik sistemlerin temelini oluşturmaktadır: rota planlama ve navigasyon (yol ağlarında A*), bulmaca ve oyun motorları, otomatik konfigürasyon ve zamanlama, robot hareket planlaması ve lojistik ile yöneylem araştırmasında kullanılan otomatik planlama ve kısıt çözücülerin omurgasını teşkil etmektedir.
Tarihçe
Arama, yapay zekanın ilk günlerinden itibaren merkezi bir rol oynamıştır; Newell ve Simon'ın Genel Problem Çözücüsü (1950'lerin sonları) zekayı problem uzaylarında arama olarak çerçevelemiştir. A* algoritması (Hart, Nilsson, Raphael, 1968) sezgisel aramaya titiz bir optimallik temeli sağlamış ve Pearl'ün 1984 tarihli monografisi sezgisel arama kuramını sistemleştirmiştir. Bu çerçeve, yapay zeka ders kitaplarında standart bir düzenleyici mercek olarak kalmaktadır.
Öne çıkan isimler
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
İlgili konular
Temel eserler
- hart1968
- pearl1984
- russell2020
Sıkça sorulan sorular
- Bilgisiz ve bilgili arama arasındaki fark nedir?
- Genişlik öncelikli veya derinlik öncelikli arama gibi bilgisiz (kör) arama, bir durumun hedefe ne kadar yakın olduğu hakkında hiçbir bilgi kullanmaz ve tamamen durum uzayının yapısına göre keşif yapar. Bilgili (sezgisel) arama ise, kalan maliyetin hedefe olan tahminini kullanarak hangi durumların genişletileceğine öncelik verir, bu da çok daha verimli olabilmektedir.
- A* neden bu kadar yaygın kullanılmaktadır?
- A*, başlangıçtan itibaren gerçek maliyeti (g) hedefe olan sezgisel bir tahminle (h) birleştirir ve sezgisel kabul edilebilir olduğunda, bilgisiz aramadan tipik olarak çok daha az durumu keşfederken optimal bir çözüm bulmayı garanti etmektedir. Optimizasyon ve verimliliğin bu dengesi, onu yol bulma için varsayılan bir seçim haline getirmektedir.