Kod ve Us: Arama ile Problem Çözme

Arama, problemin durum uzayında sistematik olarak araştırma yapmaya dayanan bir problem çözme tekniğidir. Durum uzayı bir problemin farklı durumlarını barındıran bir kümedir. Bu durumlar bir oyun tahtası ve üzerindeki taşların konumları, çıkarsama sürecindeki ara adımlar, satıcının gezdiği şehirler olabilir. Bu durumların oluşturduğu küme içerisinde arama yapılarak problemin çözümü bulunmaktadır. Başka bir ifadeyle aramayı, formülleştirme ve alternatifleri inceleme süreci olarak tanımlayabiliriz.

Arama ile ilgili olarak Russell ve Norvig'in kitabında problem çözme etmeni anlatılmıştır. Bu etmen istenen durum(lar)a ulaşmak için sonraki durumları (adımları) bularak karar verir. Böylece etmenimizin bir hedefi, bu hedefe ulaşmak için geçebileceği durumlar (adımlar) vardır.

Varolan duruma göre hedef formülasyonu problem çözmedeki ilk aşamadır. Hedefi bir durumlar kümesi olarak düşüneceğiz, bu durumlar bizim hedefe ulaştığımız durumlar olacaktır. Bu durumlar arasındaki geçişler de eylemlerimizi oluşturacaktır.

Problem çözmede ikinci aşama problemin formüle edilmesidir. Problemin formüle edilmesi hangi eylemlerin ve durumların değerlendirileceğine karar verme sürecidir.

Hedefimizi ve problemimizi tanımlama sürecini daha iyi anlamak konuyu bir örnekle gösterelim:

Problem : İzmir'den İstanbul'a gitmek
Hedef : İstanbul
Başlangıç durumu : İzmir
Durumlar : Belli bir şehirde olma (aradaki herhangi bir şehir de olabilir)
Eylemler : Bir şehirden başka bir şehire geçiş

Bu bilgileri oluşturup etmenimize verdikten sonra problemi, hedefi, durumları ve eylemleri tanımlamış oluyoruz. Etmenin yapması gereken başlangıç durumundan (İzmir), bitiş durumuna (İstambul) geçiş için uygun adımları (eylemleri) bulmasıdır. İzmir'den İstanbul'a gitmek için geçilebilecek yolları bilmeden etmenin bu işi yapması mümkün değildir. Yapılması gereken etmene bir yol haritası vermektir. Bu haritanın amacı etmenin şehirler arasında yapabileceği geçişleri göstermektir. Böylece gidebileceği şehirleri (durumlar) ve yapabileceği eylemleri (hangi şehirler arasında yolculuk yapabileceği) öğrenmiş olur. Etmen bu bilgilere de sahip olduktan sonra, farklı eylemleri ve durumları sınayarak yapması gereken eylemleri bulur ve adım adım durumlar arasındaki geçişlerle hedef duruma ulaşmaya çalışır. Sonraki durumlara geçişte farklı kriterleri göz önüne alabilir (en kısa yol, en iyi yol, vb.).

Bu anlatılan sürece arama adı verilmektedir. Bir arama algoritması problemi girdi olarak alır ve çıktı olarak bu probleme bir çözüm (yapması gereken eylem aşamaları) üretir. Bir çözüm bulunduğu zaman, bu çözümün önerdiği eylemler gerçekleştirilebilir. Buna çalıştırma aşaması adı verilmektedir. Böylece etmen için basit bir "formüle et, ara, çalıştır" tasarımı elde etmiş oluyoruz. Buraya kadar anlatılanları yine Russell ve Norvig'in kitabındaki bir algoritma ile gösterelim: