Durum Uzayı Araması
Durum uzayı araması, bir hedef testini karşılayan bir durum veya ona ulaşan bir yol bulmak amacıyla, başlangıç durumundan mevcut eylemler aracılığıyla erişilebilen durumlar kümesinin sistematik keşfidir.
Tanım
Durum uzayı araması, bir problemi, düğümleri durumlar ve kenarları eylemler olan bir çizge olarak ele almakta ve bir hedef durum bulunana veya uzay tükenene kadar sabit bir stratejiye göre bir sınırdan (frontier) durumları genişleterek ilerlemektedir.
Kapsam
Bu konu, bir problemin durum uzayı (durumlar, eylemler, geçiş modeli, hedef testi, yol maliyeti) olarak formüle edilmesini ve alan özgü rehberlik olmaksızın onu keşfeden bilgisiz arama stratejilerini (genişlik öncelikli, tek maliyetli, derinlik öncelikli, derinlik sınırlı ve yinelemeli derinleştirme araması) ele almaktadır. Ayrıca, bu stratejilerin eksiksizlik, optimalite, zaman karmaşıklığı ve uzay karmaşıklığı açısından analizini ve tekrarlanan durum tespiti ile ağaç araması ile çizge araması arasındaki ayrımı da içermektedir. Sezgisel rehberlik, sezgisel arama ve A* ile ilgili ayrı bir konuda ele alınmaktadır.
Temel sorular
- Bir problem durumlar, eylemler, bir geçiş modeli ve bir hedef testi olarak nasıl temsil edilir?
- Genişlik öncelikli, derinlik öncelikli, tek maliyetli ve yinelemeli derinleştirme aramaları, sınır (frontier) sıralamalarında nasıl farklılık gösterir?
- Her bir bilgisiz stratejinin eksiksizlik, optimalite, zaman ve uzay garantileri nelerdir?
- Çizge araması, ağaç aramasının izin verdiği durumların israflı yeniden keşfini nasıl önler?
Anahtar kavramlar
- başlangıç durumu ve hedef testi
- geçiş modeli ve ardıllar
- sınır (açık liste) ve keşfedilen küme
- genişlik öncelikli arama
- derinlik öncelikli arama
- tek maliyetli arama
- yinelemeli derinleştirme
- ağaç araması ve çizge araması
Temel kuramlar
- Sınır sıralaması stratejiyi belirler
- Bilgisiz arama algoritmaları, durumları sınırdan (frontier) çıkarma sıralamalarıyla ayırt edilir: bir FIFO kuyruğu genişlik öncelikli arama, bir LIFO yığını derinlik öncelikli arama ve yol maliyetine göre bir öncelik kuyruğu tek maliyetli arama sağlar.
- Uzay açısından verimli bir optimum olarak yinelemeli derinleştirme
- Derinlik öncelikli yinelemeli derinleştirme araması, artan sınırlar ile derinlik sınırlı derinlik öncelikli aramayı tekrar tekrar çalıştırarak, derinlik öncelikli aramanın doğrusal uzayını genişlik öncelikli aramanın eksiksizliği ve optimalitesi (birim maliyetlerde) ile birleştirir.
Klinik önem
Bilgisiz durum uzayı araması, yol bulma, bulmaca çözme, model kontrolünde erişilebilirlik analizi için kavramsal ve uygulama temelini oluşturmakta ve sezgisel ve rakip aramanın üzerine inşa edildiği bir alt tabaka olarak hizmet etmektedir. Karmaşıklığını anlamak, kör aramanın ne zaman uygulanabilir olduğunu ve sezgisellerin ne zaman gerekli olduğunu belirlemede yol göstermektedir.
Tarihçe
Sistematik durum uzayı araması, Moore ve Dijkstra'nın en kısa yol çalışmalarını da içeren 1950'lerin çizge geçiş algoritmalarından gelmekte ve erken yapay zekada problem çözme modeli olarak çerçevelenmiştir. Korf'un 1985'teki yinelemeli derinleştirme analizi, doğrusal uzaya sahip kabul edilebilir ağaç aramaları arasında optimalitesini ortaya koymuştur.
Öne çıkan isimler
- Nils J. Nilsson
- Richard E. Korf
- Edward F. Moore
- Edsger W. Dijkstra
İlgili konular
Temel eserler
- nilsson1971
- russell2020
Sıkça sorulan sorular
- Genişlik öncelikli arama ne zaman optimaldir?
- Genişlik öncelikli arama, her adımın aynı maliyete sahip olduğu durumlarda optimaldir, çünkü en sığ hedefi ilk bulur. Adım maliyetleri farklı olduğunda, tek maliyetli arama (sınırı birikmiş yol maliyetine göre sıralayan) en düşük maliyetli çözümü garanti eden bilgisiz stratejidir.
- Neden düz genişlik öncelikli arama yerine yinelemeli derinleştirme kullanılır?
- Genişlik öncelikli arama, tüm sınırı depolar ve derinliğe göre üstel bellek gerektirebilir. Yinelemeli derinleştirme, artan derinlik sınırları ile derinlik öncelikli aramayı tekrar tekrar yaparak, sığ düğümlerin yeniden genişletilmesi pahasına, birim maliyetli problemlerde hala eksiksiz ve optimal olurken yalnızca doğrusal bellek kullanır.