YAPAY ZEKA
Günlük yaşantıda zihinsel kapasite çok önemli olduğu için insanlar bilimsel olarak akıllı insan ( Homo sapien) olarak isimlendirilmiştir. Yapay zeka, YZ, (AI-Artificial Intelligence) alanı zeki varlıkları anlamaya çalışır. Bu nedenle YZ çalışmalarının bir amacı kendimiz hakkında daha fazla şey öğrenmektir. Felsefe ve psikolojiden farklı olarak YZ yalnız zekayı anlamaya değil aynı zamanda zeki varlıklar yapmaya çabalar. YZ çalışmalarının bir diğer nedeni de başlangıç aşamasında bile ilginç ve yararlı ürünler yapılmış olmasıdır. Şeklen 1956′da başlayan YZ en yeni disiplinlerden biridir. Fizik gibi disiplinler de çalışanlar bütün iyi fikirlerin Galileo, Newton, Einstein ve diğer bilim adamları tarafından üretildiğini ve yeni bir fikrin ortaya çıkması için yıllar boyu süren çalışmaların gerektiğini düşünebilir. Ama YZ çok yeni bir disiplin olduğu için üretilecek çok fikir vardır.
YZ; algılama, mantıksal muhakeme gibi genel amaçlı alanlar ve satranç oynama, şiir yazma, matematik teoremlerinin ispatlanması ve hastalıkların teşhisi gibi özel amaçlı alt alanları içerir.
YZ nedir ?
Değişik şekillerde yapılan YZ tanımları aşağıdaki 4 gruptan birine düşer
İnsan gibi düşünen sistemler.
İnsan gibi davranan sistemler.
Rasyonel düşünen sistemler.
Rasyonel davranan sistemler.
Yukarıda görüldüğü tanımlar insana veya rasyonelliğe göre yapılmıştır. Bu da insanların her zaman rasyonel davranmadıklarını belirtmektedir. İnsan merkezli yaklaşım hipotez ve deneysel doğrulamayı içerirken, rasyonalist yaklaşım matematik ve mühendisliği içermektedir. Aşağıda her tanım ayrıntılı olarak incelenmiştir.
İnsan gibi Davranmak: Turing Test yaklaşımı
Turing Test, zekanın işlemsel tanımını sağlamak için Alan Turing (1950) tarafından tasarlanmıştır. Turing zeki davranışı, soru soran kimseyi tüm anlamaya ait işlemlerde şaşırtacak şekilde insan seviyesinde davranma olarak tanımlamıştır. Sorular bir hat üzerinden uzaktan sorulmakta ve hattın ucunda insan mı yoksa bilgiayar mı olduğu anlaşılmaya çalışılmaktadır. Bu testi geçmek için bilgisayarın insan seviyesinde performans göstermesi gerekir. Şimdilik bu testi geçmek çok zor görünmektedir. Bu test için bilgisayarın aşağıdaki yeteneklere sahip olması gerekmektedir:
Doğal dil işleme: Türkçe veya İngilizce (insan dilleri) haberleşebilmeyi sağlamak için.
Bilgi Gösterimi : Soruşturma sırasında veya öncesinde bilgi depolamak için.
Otomatik Muhakeme : Depolonan bilgiyi kullanarak cevap verebilme veya yeni sonuçlar çıkarma.
Öğrenme : Yeni koşullara adapte olma ve kalıpları saptama.
Turing test’te soruşturmayı yapan ve bilgisayar birbirini kesinlikle görmez. Buna karşın Toplam Turing Test’te vidyo sinyali de kullanılır. Böylece soruşturmayı yapan kişi fiziksel nesneleri algılama yeteneğini de ölçebilir. Bu test için bilgisayarın aşağıdaki yeteneklere sahip olması gerekir:
Görme : Nesneleri algılamak için.
Robotik : Nesneleri hareket ettirmek için.
YZ’de Turing Testi geçmek için yapılan büyük bir çalışma yoktur. İnsan gibi davranma meselesi insanlarla etkileşen YZ programları için geçerlidir. Örneğin kullanıcı ile iletişimde bulunan bir dil işleme sistemi insan gibi konuşmalıdır.
İnsan Gibi Düşünmek
Verilen bir programın insan gibi düşündüğünü söyleyebilmek için insanların nasıl düşündüğünü saptamanın bir yolunu bulmamız gerekir. İnsanın nasıl düşündüğünü iki şekilde öğrenebiliriz. Birincisi kendi düşüncelerimizi gözleme, ikincisi ise psikolojik deneyler yapmaktır. Düşünme ile ilgili yeterince kesin teorilere erişilirse bu teoriler bilgisayar programı olarak ifade edilebilir.
Bazı araştırmacılar pogramları herhangi bir yöntemi kullanarak doğru sonucu bulacak şekilde yazarken bazı araştırmacılar da sonucun doğru ya da yanlış olmasına bakmaksızın insanların düşündüğü şekilde çözümü arayan programlar yazmaktadır.
Rasyonel Düşünme: Düşünme Kanunları
Doğru düşünmeyi kodlamaya ilk çalışanlardan biri Aristotle’dır. Aristottle mantığına göre doğru önermeler verildiğinde daima doğru sonuç elde edilir. Aşağıda buna ait bir örnek verilmiştir:
Socrates insandır. İnsanlar ölümlüdür. à Öyleyse Socrates ölümlüdür.
Bu düşünme kanunlarının düşünme işlemini yönettiği kabul edildi ve Mantık alanını başlattı. YZ’de mantık taraftarları problemleri mantıksal notasyonla tanımlayarak akıllı sistemler oluşturmaya çalışmışlar. Bu konuda karşılaşılan iki büyük engel:
Konuşma diline özgü bilgilerin %100 kesinlik ifade etmediği durumda mantık formunda belirtme güçlüğü
Problemleri prensipte çözmekle, pratikte çözmek arasındaki fark. Birkaç düzine önerme bile bilgisayarın sınırını aşabilir. Bu da prensip olarak çözülebilecek problemlerin pratikte çözümünü güçleştirmektedir.
Rasyonel Davranma: Rasyonel Ajan Yaklaşımı
Rasyonel davranma, inanışları baz alarak amaca erişecek şekilde davranmaktır. Farklı YZ çalışmalarına benzer şekilde yaklaşabilmek için ajan(agent) sözcüğü kullanılmaktadır. Buradaki kullanım normal anlamının dışındadır. Ajan algılayan ve davranan herhangi bir şeydir. Ajan yaklaşımında YZ çalışmaları; rasyonel ajan çalışmaları ve rasyonel ajan oluşturmadır.
Düşünme kanunlarında vurgulanan doğru çıkartımdır. Doğru çıkartımda bulunmak bazen rasyonel ajanın (RA) bir parçası olabilir. Çünkü rasyonel davranmanın bir yolu, mantıksal olarak bir davranışın istenen amacı sağlayacağı sonucu çıkartılırsa bu sonuç üzerine belirlenen şekilde davranılır. Diğer yandan doğru çıkartım tam rasyonellik değildir. Bazen yapılacak şeyin doğru olacağı ispat edilmeden yapılması gerekebilir. Örneğin kızgın bir sobadan elin çekilmesi reflekstir ve kızgınlığı hissettikten sonra hangi hareketin yapılacağını düşünerek yapılan yavaş haraketten daha etkilidir. Sobadan elin çekilmesi bir doğru çıkartım sonucu olmamakta ama rasyonel bir davranıştır. Mükemmel rasyonellik daima doğru şeyi yapmaktır ve karmaşık bir çevrede daima doğru şeyi yapmak mümkün değildir.
RA yaklaşımının iki üstünlüğü vardır:
Düşünme kanunları yaklaşımından daha geneldir. Çünkü rasyonel davranmak için doğru çıkartım faydalı bir mekanızma olmasına karşın gerekli değildir.
Rasyonelliğin tanımı açıkça yapıldığı için bilimsel gelişmeye insan davranışından veya insan düşüncesinden daha yatkındır.
ZEKİ AJANLAR
Ajan, sensorlarıyla çevresini algılayan ve efektörleriyle bu çevre üzerinde davranan herhangi bir şeydir. İnsan sensor olarak göz kulak ve diğer organlara, efektör olarak da el, kol, ağız ve diğer vücut kısımlarına sahiptir. Robotik ajan, kamera ve infrared bulucuları sensor olarak değişik motorları da efektör olarak kullanır.
Ajanlar Nasıl Davranmalı
Rasyonel ajan doğru şeyi yapan ajandır. Bu yanlış bir şey yapmaktan daha iyidir ama doğru şeyi yapmak ne demektir? İlk yaklaşım, doğru haraket ajanı en başarılı yapacak harakettir. Bu durumda ajanın başarısına ne zaman ve nasıl karar verileceği sorusunu ortaya çıkarır.
Performans Ölçüsü
Ajanın ne kadar başarılı olduğunu saptayan kritere performans ölçüsü denir. Performans ölçüsünün dikkatli bir şekilde saptanması gerekmektedir. Örneğin kirli zemini temizleyen bir ajanı gözönüne alalım. Burada performans ölçüsü olarak 8 saatlik çalışmada temizlenen kir miktarı alınabilir. Daha karmaşık performans ölçüsü yalnız temizlenen kir miktarını değil aynı zamanda tüketilen enerji ve çıkarılan gürültüyü de dikkate alabilir.
Değerlendirme Zamanı
Performansın ne zaman değerlendirildiği de önemlidir. Örneğin temizlik ajanının performansını ilk saat sonunda değerlendirirsek işe hızlı başlayan ama sonra yavaşlayan belki de hiç çalışmayan ajan ödüllendirilmiş, sürekli çalışan cezalandırılmış olur. Bu nedenle performansı günlük veya ömür boyu şeklinde daha uzun vadede değerlendirmek gerekir.
Mükemmellikle rasyonelliğin ayırt edilmesi gerekir. Mükemmel ajan davranışlarının vereceği sonucu bilir ve buna göre davranır. Fakat gerçekte mükemmellik imkansızdır. Aşağıdaki örneği göz önüne alalım:
Okula gelirken demiryolunun karşısında bir arkadaşınızın gitmekte olduğunu gördünüz. Demiryolu geçiti açıktı ve arabalar geçiyordu. Arkadaşınıza başka türlü erişemeyeceğiniz için demiryolundan geçmeye başladınız. Bu sırada bir yolcu uçağının kapısı üzerinize düştü.
Demiryolundan geçmek rasyonel olmayan bir davranışmıdır?
Rasyonellik algılananlara bağlı olarak beklenen başarı ile ilgilidir. Çoğu zaman demiryolundan geçmek başarılı sonuç verdiği ve üzerinize uçak kapısı düşeceğini tahmin edemeyceğiniz için demiryolundan geçmek rasyonel bir davranıştır. Eğer ajanın düşen kapıyı saptayabilecek bir radarı varsa o zaman haraket rasyonel değildir. Benzer şekilde demiryolu geçidi kapalı iken geçmek de rasyonel olmayan bir davranıştır. Diğer bir deyişle ajanı algılayabileceği bir durumu dikkate almayarak başarısız olduğu zaman suçlayabiliriz.
Sonuç olarak herhangi bir andaki rasyonellik dört şeye bağlıdır:
Başarı derecesini belirten performans ölçüsü,
Ajanın o ana kadar algıladığı her şey (algı serisi-percept sequence),
Ajanın çevre hakkında bildikleri,
Ajanın yapabileceği hareketler.
İdeal Rasyonel Ajan
Yukarıdaki sonuçlardan yola çıkarak ideal rasyonel ajan aşağıdaki şekilde tanımlayabiliriz:
Her olası algı serisi için, algı serisi ve sahip olduğu bilgileri kullanarak performans ölçüsünü maksimize edecek şekilde davranan ajan ideal ajandır.
Demriyolu geçidinin kapalı olup olmadığına bakmaz isek algı serisi bize hızla yaklaşan bir treni söyleyemez. Demiryolu geçidine bakmadan geçmek riski çok yüksek olduğu için rasyonel bir davranış değildir. İdeal rasyonel ajan adımını atmadan önce bakma eyleminde bulunmalıdır. Çünkü bakmak beklenen performansı artırır. Bu nedenle yararlı bilgileri elde etmek amacıyla yapılan eylemler rasyonelliğin bir parçasıdır.
Algı Serisinden Eyleme İdeal Eşleme
Ajanın davranışı yalnız algı serisine bağlı ise olası tüm algı serilerine karşı gelen eylemler tablo haline getirilerek bir ajan tanımlanabilir. Çoğu zaman bu tablo çok uzun olacaktır. Oluşturulan tabloya algı serisinden eyleme eşleme denir. Eğer eşleme ajanı tanımlıyorsa ideal eşleme de ideal ajanı tanımlar. Eşleme için tablonun herbir elemanının ayrı ayrı belirtilmesi gerekmez. Örneğin hesap makinesindeki karekök fonksiyonunu basit bir ajan olarak göz önüne alalım. Bu ajanın algı serisi basılan tuşlardır. İdeal eşleme; girilen pozitif sayı x ise z2»x olacak şekilde 4 basamak doğrulukta z’yi göstermektir. Bu amaçla tablo kullanmak yerine Newton yöntemi kullanılarak yazılan program ile ajan tanımlanabilir. Tablo çok uzun olmasına karşın ajan çok kısa bir programdır. Aşağıda tablo ve program görülmektedir:
Otonomi
Eğer bir ajanın eylemleri tamamen sahip olduğu bilgilere bağlıysa yani algı serisini dikkate almıyorsa otonom değildir. Eğer bir sistemin davranışları kendi deneyimleri ile saptanıyorsa otonomdur. Otonom kelimesi insanın doğrudan kontrolü altında olmayan anlamında da kullanılır. Örneğin otonom kara aracı (insansız). Otonom olan ajanlar çevre koşulları değiştiğinde yeni koşullara adapte olarak görevini başarı ile sürüdürebilir. Eğer sadece önceden verilen bilgileri kullanırsa başarısız olma olasılığı yüksektir.
Zeki Ajanların Yapısı
YZ ajan programı yazma işidir. Bu programlar algıdan eyleme eşleme yapan programlardır. Yazılan programlar bir yapı üzerinde çalıştırılacaktır. Bu yapı bilgisayar olabileceği gibi özel amaçlı donanım da olabilir. Yapı sensorlardan gelen algıları programa aktarır, programı çalıştırır ve efektörler ile programın davranışını gerçekleştirir. Ajan yapı ve programdan meydana gelmektedir:
Ajan = Yapı + Program
Ajan programı tasarlamadan önce ajanın çalışacağı çevrenin, algılamaların, eylemlerin ve amaçların tanımlanması gerekir. Aşağıdaki tabloda bazı ajan tipleri verilmiştir.
Ajan Tipi
Algılama
Eylem
Amaç
Çevre
Tıbbi teşhis sistemi
Bulgular, hastanın cevapları
Sorular, testler
Sağlıklı hasta, minimum maliyet
Hasta, hastahane
Uydu görüntü analiz sistemi
Değişik yoğunluk ve renkte pikseller
Görüntüyü sınıflandır, bas
Doğru sınıflandırma
Uydudan gelen görüntü
Rafineri Kontrolörü
Sıcaklık, basınç okumaları
Valfleri aç, kapa; sıcaklığı ayarla
Saflığı ve emniyeti maksimum yap
Rafineri
İnteraktif İngilizce öğreticisi
Yazılı kelimeler
Alıştırmalrı, önerileri, düzeltmeleri yaz
Öğrencinin notunu maksimize et
Öğrenci kümesi
Ajan Programları
Zeki ajanlar oluşturulurken aynı iskelet kullanılacaktır: çevreyi algılamak ve eylem üretmek. Ajan programının en basit hali aşağıda görülmektedir:
Eşleme algı serisinden eyleme yapılmaktadır ama ajana yalnız o anki algı gelir. Bu algıların seri halinde saklanıp saklanmaması ajana bağlıdır. Bazı çevrelerde algı serisi saklanmaksızın oldukça başarılı olunabilir. Karmaşık çevrelerde ise tüm algıların saklanması fizibil olmamaktadır.
Ajan programı yazmanın en basit yolu tablo kullanmaktır (look-up table). Bu durumda olası tüm algı serisinin bellekte tutulması ve indeks kullanarak erişilmesi gerekir. Tablo kullanımında aşağıdaki olumsuzluklar ortaya çıkar:
Yalnız satranç oynayabilen basit bir ajan için bile gerekli tablonun 35100 girişi olması gerekir.
Tasarımcnın tabloyu oluşturması çok uzun zaman alır.
Ajan otonom değildir. Çünkü en iyi eylem hesabı tamamen önceden girilmiştir.
Ajana bir derece otonomi tanınarak öğrenme mekanizması oluşturulsa bile tüm girişler için tablonun doğru değerlerini bulması sonsuza kadar sürer.
Basit Refleks Ajanlar
Bir kameradan gelen görüntü 50 Mbyte/sn. hızındadır (saniyede 25 çerçeve, her çerçeve 1000*1000 piksel ve her piksel 8 bit renk ve 8 bit yoğunluk bilgisi). Bir saat için gerekli look-up tablosu 260*60*50M girişli olacaktır. Genel giriş çıkış ilişkileri kullanılarak tablo kısaltılabilir. Örneğin öndeki araç fren yaparsa fren lambaları yanar ve sürücü buna dikkar ederek frene basar. Aynı işlem görsel giriş kullanılarak “öndeki araç fren yapıyor” koşulu ile ajan programındaki “fren yap” eylemi ilişkilendirilebilir. Bu ilişkiye koşul-eylem (condition-action) kuralı denir ve aşağıdaki şekilde yazılabilir:
EĞER Öndeki_Araç_Frenliyor İSE frenle ( if/then)
İnsanlarda benzeri davranışlar bir öğrenmenin sonucunda ( araba sürme gibi ) veya refleks olarak ( kızgın sobadan elin çekilmesi gibi) yapılır. Aşağıda koşul-eylem kuralının ajana algıdan eyleme bağlantıyı nasıl sağladığı görülmektedir.
Basit Refleks ajanın şematik diyagramı.
Basit Refleks ajan. Algılamayla tanımlanan mevcut duruma uyan kuralı bularak çalışır.
Giriş_Yorumla : Algılanan mevcut durumu soyut olarak tanımlar (abstraction).
Kural_Eşleme : Kural kümesinde mevcut duruma uyan ilk kuralı verir.
Kural_Eylem : Kurala bağlı olarak yapılacak eylemi verir.
Değişimleri İzleyen Ajan
O anki algılamaya bağlı olarak doğru karar verilebiliyor ise basit refleks ajanlar başarılı olabilir. Arabanın arkasında fren lambalaraırına ek olarak dönüş sinyal lambalarıda yer almaktadır. Frene basılıp basılmadığını saptamak için arabanın her iki kenarındaki lambanın komtrol edilmesi ferekmektedir. Bu amaçla bir önceki görüntünün saklanması gerekmektedir. Bir önceki görüntüde her iki lamba sönükse ve o anki görüntüde ikisi de yanıyor ise frene basıldığını söyleyebiliriz. Bu nedenle doğru eylemin seçilebilmesi için bazı bilgilerin saklanması gerekmektedir. Buna iç durum ( internal state) adı verilir.
Sensorlardan gelen bilgi daha önceki duruma bağlı olarak farklı sonuçlar verebiliyor ise önceki durumun da saklanması gerekir. Dünyanın durumu yalnız o anki girişe değil bir önceki duruma da bakılarak saptanır. Aşağıda iç durumlu bir refleks ajan görülmektedir.
İç durumlu refleks ajan
Yenile_Durum: Sensorlardan gelen bilgiye veya yapılan eyleme bağlı olarak yeni iç durumu oluşturur.
Amaç tabanlı Ajanlar
Çevrenin o anki durumunu bilmek ne yapılacağına karar vermeye yetmeyebilir. Örneğin bir kavşakta araba sağa, sola dönebilir veya doğru gidebilir. Doğru karar arabanın nereye gideceğine bağlıdır. Diğer deyişle ajan o anki durumla birlikte amaçla ilgili bilgilere de gereksinim duyar. Ajan programı, olası kararların sonuçları ile bu bilgiyi birleştirerek doğru eylemde bulunabilir. İstenen amaca bazı durmlarda kolayca erişilebileceği gibi bazen çok karmaşık işlemler yapılması gerekebilir. Ajanın amacına erişebilmesi için yapacağı eylem sırası YZ’nin alt alanları olan arama (search) ve planlama (planning) da incelenmektedir.
Bu şekilde karar verme daha önce anlatılan koşul-eylem kurallarından temel olarak farklıdır. Refleks ajan fren lambasını gördüğü zaman fren yapar. Amaç tabanlı ajan ise öndeki aracın fren lambaları yandığı zaman onun yavaşlayacağını çıkarır. Öndeki araca çarpmama amacını gerçekleştirecek eylem ise fren yapmaktır. Her nekadar amaç tabanlı azan etkin görünmese de esnektir. Örneğin yağış başladığı zaman frenlerin etkin bir şekilde kullanılabilmesi için bilgisini yenileyebilir. Diğer yandan refleks ajan için çok sayıda koşul-eylem kuralı yazmak gerekir. Amaç tabanlı ajanlarda amacı değiştirerek farklı noktalara erişmek mümkündür. Refleks ajanlar ise sadece bir noktaya giderler. Aşağıdaki şekilde amaç tabanlı ajanın yapısı görülmektedir.
Amaç tabanlı ajan.
Fayda Tabanlı Ajanlar
Amaçlar yalnız başına yüksek kalitede davranış üretmek için yeterli değildir. Örneğin arabanın istenen yere gidebilmesi (amaca erişmek) için izleyebileceği bir çok yol olabilir. Bu yolların bazıları diğerlerinden daha hızlı, daha güvenli veya daha ucuz olabilir. Amaçlar “mutlu” ve “mutsuz” durumları arasında kaba bir ayırım sağlar. Oysa daha genel performans ölçüleri amaca erişirken ne kadar mutlu olduğunu gösterebilir. Mutlu kelimesi bilimsel görülmediği için bunun yerine fayda (utility) kelimesi kullanılmaktadır. Fayda fonksiyonu; mevcut durumu, mutluluk derecesini gösteren bir gerçel sayıya dönüştürür. Fayda fonksiyonları tanımlanırken çelişkiye düşülebilir. Örneğin hız ve emniyetin ağırlıkları uygun şekilde seçilmelidir. Birden fazla amaç olduğu zaman bu amaçların da önem sırasına göre sıralanması gerekebilir.
Amaçlar her nekadar kaba olsada istenen amaca erişmek için gereken eylemi kolayca bulurlar. Bazı durumlarda fada fonksiyonu bir amaç kümesi şeklinde de ifade edilebilir. Aşağıdaki şekilde fayda tabanlı ajanın yapısı görülmektedir.
Fayda tabanlı ajan.
ÇEVRE
Bu bölümde ajan ve çevre ilişkileri incelenecektir. Önce ajanların çalışacağı farklı çevreler ve bu çavrelerin ajan tasarımındaki etkileri incelenecektir.
Çevre Özellikleri
Çevre aşağıdaki temel özelliklere bağlı olarak sınıflanlandırılabilir.
Erişimli / Erişimsiz (Accessible vs. inaccessible)
Eğer ajanın sensorları çevrenin durumunu tamamen saptayabiliyorsa çevre ajan için erişilebilirdir. Çevrenin erişilebilir ise değişimleri izlemek için durum saklaması gerekmez.
Deterministik/ Deterministik olmayan ( Deterministic vs. nondeterministic)
Eğer çevrenin gelecek durumu o anki durum ve ajanın eylemine bağlı olarak tespit edilebiliyor ise çevre deterministiktir. Eğer çevre erişimli değil ise deterministik olmadaığı kabul edilebilir.
Bölümlü/ Bölümsüz ( Episodic vs. nonepisodic)
Bölümlü çevrede ajanın deneyimleri bölümlere ayrılmıştır. Her bir bölüm ajanın algı ve eyleminden oluşur. Eylemin kalitesi sadece o bölüme aittir. Bir önceki bölümdeki eylemin o anki bölümde bir etkisi yoktur. Bölümlü çevre, ajanın ileriyi düşünmesi gerekmediği için daha basittir.
Statik / Dinamik ( Static vs. dynamic)
Ajan karar verirken çevre değişiyorsa dinamik değişmiyor ise statiktir. Ajan karar verirken dünyanın değişimini izlemesi gerekmediğinden ve zaman önemli olmadığından statik çevrede çalışmak daha kolaydır. Eğer çevre zamanla değişmiyorsa ama ajanın performansı zamana göre değişiyorsa çevre yarı dinamik (semidynamic) olarak adlandırılır.
Ayrık / Sürekli ( Discrete vs. continuous)
Eğer sınırlı sayıda farklı ve iyi tanımlanmış algı ve eylemler var ise çevre ayrıktır. Satranç ayrıktır çünkü her hamlede olası hareketler sabit sayıdadır. Araba sürme süreklidir, çünkü arabanın ve diğer araçların pozisyonu ve hızı sonsuz sayıda sürekli değerler alabilirler.
Aşağıdaki tabloda bazı çevreler ve karakteristikleri verilmiştir.
Çevre
Erişilebilir
Deterministik
Bölümlü
Statik
Ayrık
Santranç(saatle)
Evet
Evet
Hayır
Yarı
Evet
Satranç (saatsiz)
Evet
Evet
Hayır
Evet
Evet
Poker
Hayır
Hayır
Hayır
Evet
Evet
Tavla
Evet
Hayır
Hayır
Evet
Evet
Araba sürme
Hayır
Hayır
Hayır
Hayır
Hayır
Tıbbi teşhis
Hayır
Hayır
Hayır
Hayır
Hayır
Görüntü analiz
Evet
Evet
Evet
Yarı
Hayır
Parça toplama robotu
Hayır
Hayır
Evet
Hayır
Hayır
Rafineri kontrolörü
Hayır
Hayır
Hayır
Hayır
Hayır
İnteraktif İng.öğretici
Hayır
Hayır
Hayır
Hayır
Evet
Çevre Programları
Ajan proogramlarını test etmek içiin çevre simülatörü kullanılır. Simülatörler bir veya daha fazla ajanı giriş olarak alır, herbir ajana doğru algıları ileterek geriye eylemlerini alır. Simülatör ajanların eylemine bağlı olarak çevreyi yeniler. Yenileme işleminde ajan eylemine ek olarak bazı dinamik özellikler de eklenebilir. Bu nedenle çevre başlangıç durumu ve yenileme fonksiyonu ile tanımlanır. Aşağıda çevre simülatör programı görülmektedir.
Simülatör programına her bir ajanın performansını değerlendirecek performans fonksiyonu da eklenebilir
PROLOG ve LOJİK PROGRAMLAMA
Son yıllara kadar bilgisayar programlama bir problemin çözümü için yapılması gerekenlerin adım adım yazılması şeklindeydi. Yani bilgisayara işlemlerin NASIL YAPILACAĞI (procedural) söylenmekteydi. Fortan, C, Pascal gibi diller bu yaklaşımı kullanmaktadır.
Programlamada bir diğer yaklaşım ise doğru cevabın özelliklerinin verilerek yapılacak işlemlerin belirtilmesidir. Yani bilgisayara işlemlerin nasıl yapılacağı değil NE YAPACAĞI (declarative) söylenmektedir. Bu tip programlama LOJİK PROGRAMLAMA olarak isimlendirilir. Bu amaçla Lisp ve PROLOG gibi programlama dilleri geliştirilmiştir.
Deklaratif dillerin üç önemli üstünlüğü vardır.
Lojik programlama işlemlerin mekanizmaları yerine mantığına odaklandığından doğal olarak yüksek seviyelidir. İşlemlerin nasıl yapılacağı makinaya bırakıldığı için karmaşık fikirler kolay bir şekilde ifade edilebilir.
Lojik, verilerin gerçek (fact) ve kural (rule) olarak belirtilmesine olanak sağlar. Örneğin A noktası B noktasına bağlıdır, B noktası C noktasına bağlıdır şeklinde gerçekler belirtilebilir. X Y’ye ve Y Z’ye bağlı ise X Z’ye bağlıdır şeklinde genel kurallar belirtilebilir.
Lojik programlama dilleri kullanılarak bilgisayar programları daha hızlı ve kolay bir şekilde geliştirilebilir. Programcının karmaşık fikirleri ifade edebilmesi ve veri yapılarını hızlı bir şekilde oluşturmasına olanak tanır.
PROLOG’A GİRİŞ
Prolog dünyayı ifade etmek için nesneleri (object) ve aralarındaki ilişkiyi (relation) kullanır. Aşağıdaki bildirime bakalım:
Ali ders verir.
Bu cümle iki nesne (Ali ve ders) arasındaki ilişkiyi belirtmektedir. İlişki nesnelerden daha soyut bir kavramdır. Bu nedenle aynı ilişkiyi diğer nesneler için de kullanabiliriz:
Oya ders verir.
Ali seminer verir.
Hasan ders verir.
Yukarıda verilen gerçekler kullanılarak bu dünya için sorular sorabiliriz. Yalnız belirtilen gerçek ve kurallar doğru kabul edilmektedir. Bunların dışındakiler yanlış kabul edilir.
Örneğin; Ali’nin ders verdiği doğru mu ? şeklinde bir soru sorarsak cevap Evet olmalıdır. Oya’nın seminer verdiği doğru mu? Sorusunun cevabı Hayır olmalıdır. Kimler ders vermektedir? Şeklindeki bir sorunun cevabı : Ali, Oya, Hasan olmalıdır. Çünkü bu kişiler ders ilişkisini gerçeklemektedirler.
Gerçeklerin yanında nesneler arasında daha soyut ve daha genel ilişkileri belirten kurallar vardır. Örneğin ders veren herkesin hoca olduğunu kabul edersek aşağıdaki kuralı yazabiliriz:
eğer KİŞİ ders veriyor
ise KİŞİ hocadır. (if/then)
Burada KİŞİ bir değişkendir. Kuralın eğerli kısmı dünya hakkındaki koşulu vermektedir. Verme ilişkisini kullanarak ders nesnesi ile bilinmeyen KİŞİ nesneler kümesini belirtir. KİŞİ yerine kim uyarsa onun hoca nesnesi ile ilişkisi olduğunuu söyleyebiliriz.
Yukarıdaki kural ve gerçekleri kullanarak yeni ilişkileri çıkarabiliriz:
Ali hocadır.
Oya hocadır.
Hasan hocadır.
Çünkü Ali, Oya ve Hasan kuralın koşulun gerçeklemektedir : KİŞİ ders veriyor.
Benzer şekilde, gerçekler kümesi ve kuralı kullanarak sorgulama yapabiliriz. Örneğin; Oya hoca mı? Şeklinde bir sorunun cevabı Evet olmalıdır.
Kim hocadır şeklinde daha karmaşık bir sorunun cevabı: Ali, Oya ve Hasan olmalıdır.
Bu Prolog’un temel olarak çalışma şeklidir. Gerçekler kümesi bildirilir, nesneler kümesini belirten kurallar bildirilir ve soruları cevaplamak içiin kurallar kümesi ile gerçekler kümesi birleştirilir.
PROLOG SÖZDİZİMİ (syntax)
İlişkiler yüklem (predicate) olarak aşağıdaki formda belirtilir:
* verir(ali, ders). % Ali ders verir.
Burada “verir” yüklemi iki nesne arasındaki ilişkiyi belirtmektedir. Nesne sayısı 0 veya herhangi bir sayıda olabilir. Bu sayı “arity” olarak isimlendirilir.
Kuralların yazımında bazı sınırlamalar vardır:
Nesne ve yüklem isimleri küçük harf ile başlar.
Önce yüklem yazılır. Eğer nesneler var ise parantez içinde virgülle ayrılmış şekilde yazılır.
Her gerçek nokta karakteri ile sonlandırılır.
Bu sınırlamalara bağlı olarak yukarıda verilen gerçekleri aşağıdaki şekilde yazabiliriz:
verir(ali,ders).
verir(oya,ders).
verir(ali,seminer).
verir(hasan,ders).
Gerçekleri Sorgulama:
Gerçekler kümesi verildikten sonra onların hakkında sorular sorulabilir. Prolog’da sorgulama programı başlatma şeklidir. Yazım olarak sorgulama gerçeğe (fact) benzer ama yüklemde değişken kullanılabilir. Değişkenler büyük harf ile başlar.
Sorgulama sonucu Evet/Hayır veya nesneler kümesi şeklinde olabilir. En basit şekli Evet/Hayır şeklinde olanıdır:
verir(oya,ders). sorusunun cevabı Evet,
verir(oya,seminer) sorusunun cevabı Hayır olmalıdır.
Daha genel sorgulama nesneler kümesini içerir. Örenğin Kimler ders verir? Şeklinde bir soru prologda:
verir(X,ders).
Şeklinde yazılır. X ders ile arasındaki ilişkiyi gerçekleyen herhangi bir nesneyi temsil eden değişkendir. Yukarıdaki sorunun cevabı aşağıdaki şekilde olmalıdır:
X = ali
X = oya
X = hasan
Diğer yandan, Ali ne verir? Şeklindeki bir soru aşağıdaki şekilde yazılabilir:
verir(ali,X).
Bu sorunun cevabı
X = ders
X = seminer
olmalıdır.
Kim ne verir şeklinde bir soru aşağıdaki şekilde sorulabilir:
verir(X,Y).
Bu sorunun cevabı aşağıdaki şekildedir.
X = ali , Y = ders
X =oya, Y = ders
X =ali, Y = seminer
X =hasan, Y = ders
KURALLAR
Kurallar gerçekler ve soyutlanmış gerçekler arasındaki ilişkiyi ifade eder. Yukarıda verilen gerçekler verir(X,Y) şeklinde soyutlanabilir. Burada X kişinin adı Y ise sunuş şeklidir. Kural türkçe aşağıdaki şekilde yazılabilir:
eğer KİŞİ ders veriyor ise KİŞİ hocadır. (if/then)
Kuralın “eğer” kısmı, “ise” kısmının işlem görebilmesi için gerçeklenmesi gereken koşullar kümesidir. Prologda, önce yalnız bir koşulun yer alabildiği İSE kısmı daha sonra EĞER kısmı yazılır:
hoca(X) :- verir(X,Y).
Yukarıda ifade ” X’in hoca olduğu doğrudur EĞER X’in Y’yi verdiği doğruysa” şeklinde okunabilir. Bu durum koşulu gerçekleştiren tüm X’ler için geçerlidir.
Ebeveyn ve çocuklar arasındaki ilişki hakkında aşğıdaki gerçekler kümesini gözönüne alalım:
ebeveyn(a,b).
ebeveyn(a,c).
ebeveyn(b,d).
ebeveyn(e,f).
Burada ebeveyn(X,Y)’nin anlamı X Y’nin ebeveynidir. Bu bilgilere ek olarak nesnelerin cinsiyetiyle ilgili bilgilerede gereksinim duyulabilir:
erkek(X).
bayan(X).
Bu bilgiler kullanılarak nesneler arasındaki ilişkiler için kurallar yazılabilir. Örneğin herhangibir kişinin erkek kardeşi kimdir? Erkek kardeşi: ” X ile ebeveyni aynı olan erkek” şeklinde tanımlayabiliriz. Basit olması için sadece anne veya babanın kardeşlik için yeterli olduğunu kabul edelim. Bu amaçla aşağıdaki ifade yazılabilir:
EĞER ebeveyn(E,X),
ebeveyn(E,Y),
erkek(Y)
İSE erkekkardeş(Y,X).
Bu ifade: ” Verilen X kişisi için, eğer X’in ebeveyni E ise ve Y kişisinin ebeveyni de E ise ve Y erkek ise Y X’in erkekkardeşidir”. Burada X’in cinsiyeti önemli değildir. Bu kural prologda aşağıdaki şekilde yazılabilir:
erkekkardes(Y,X) :- ebeveyn(E,X),
ebeveyn(E,Y),
erkek(Y).
X ve Y’nin farklı olduğunu belirtmediğimiz için bir kişi kendisinin erkek kardeşi olabilir. Bu sorunu gidermek için X ve Y’nin farklı olması gerektiğini belirtmeliyiz:
erkekkardes(Y,X) :- ebeveyn(E,X),
ebeveyn(E,Y),
erkek(Y),
not ( X==Y). % + X == Y
Burada not(X==Y) ifadesi X Y’ye eşit değil anlamındadır. Not ifadesi yerine “+ Y==X” yazılabilir.
Prologda bütün değişkenler yereldir. Yani sadece kural içinde geçerlidirler. Bu nedenle bir kuraldaki X değişkeni bir diğer kuraldaki X değişkeni ile aynıı değildir.
Yineleme (Recursion)
Prolog’un en ilgi çekici özelliklerinden birisi yineleme kapasitesidir. Yineleme bir şey kendisi ve sonlandırma koşulu kullanarak tanımlanırsa olur. Faktöriyel tanımı klasik bir örnektir:
N’in faktöriyeli N kere N-1′in faktöriyeline eşittir.
Sıfırın faktöriyeli 1′dir.
Faktöriyelin bu tanımı prologda kolayca ifade edilebilir:
faktoriyel(0,1). à gerçek
faktoriyel(N,X) :- M is N-1, à kural
faktoriyel(M,Y),
X is N * Y.
Bu örnekte gerçek kuraldan önce yazılmalıdır. Prolog’da gerçek ve kurallar programdaki yazılış sırasına göre işlem görmektedir. Prolog kuralın içinde faktoriyel(M,Y)’yi bulurken programda yüklemin ilk geçtiği yerden başlayarak çözümü arar. M sıfıra kadar azaltılmaktadır. M sıfır olduğunda “gerçeğe” erişildiği zaman geri dönüş işlemi başlar. Eğer gerçek kuraldan sonra yazılırsa sonsuz döngüye girilir.
Yineleme, programlarıın basit ve kısa olmasını sağladığı için çok kullanışlıdır ama program yazılırken çok dikkatli olmak gerekir. Yineleme yalnız rakam ile değil veri yapıları ile de yaplabilir. Prolog’da veri atom (tek değer) veya liste (çok değer) olabilir. Liste elemanlar kümesidir. Elemanlar; sayı, harf, karakter dizisi hatta liste olabilir.
Liste [ ] içinde ve elemanları virgül ile ayrılmış şekilde yazılır. Aşağııda basit listeler görülmektedir:
[printer, monitor, mouse, cpu ]
[123, 45, 667]
[a, b, c, d, e, f, g]
Liste, elemanlar kümesi olduğu için kesişim, bileşim, fark gibi temel işlemler prologda yapılabilir. Örneğin; X, L litesinin üyesi ise doğru olan üye(X,L) yüklemi prologda aşağıdaki gibi tanımlanabilir:
uye(X,[X
_]).
uye(X,[_
L]) :- uye(X,L).
operatörü listeyi ilk eleman(baş) ve geri kalanı (kuyruk) şeklinde ikiye ayırır. Eğer X listenin ilk elemanı ise 1.satırdaki uye(X,[X
_]) yüklemi doğrudur. Altçizgisi “_” değişkenin değerini dikkate alma anlamındadır. Burada kuyrukta ne olduğuna bakılmamaktadır. Eğer birinci satır yanlış ise ikinci satıra bakılır. Bu satırda listenin ilk elemanı uzaklaştırılarak tekrar ilk elemanın X’e eşit olup olmadığına bakılır.
Not: üye yüklemi prologda “member(X,L)” şeklinde tanımlanmıştır.
Üye yüklemini bir dosyaya yazarak aşağıdaki sorgulamaları yapın:
uye(a,[b,c,a,d]).
uye(a,[b,c,d,e]).
uye(2,[1,2,3,34]).
uye(2,[1,5,3,34]).
Altküme işlemi de yararlı bir işlemdir. X listesinin tüm elemanları Y listesininde elemanı ise altkume(X,Y) yüklemi doğrudur. Bu problemi çözmemiz için X’in tüm elemanlarının Y’nin de elemanıı olup olmadığına bakmamız gerekir. X listesinde kontrol edilecek eleman yoksa durur aksi takdirde başarısızlıkla (fail) karşılaşılır. Program aşağıdaki şekilde yazılabilir:
altkume([],_).
altkume([X
L],Y) :- uye(X,Y), altkume(L,Y).
Burada [] boş kümedir. X’deki tüm elemanlar kontrol edilince 1.satır doğru olur.
Uye yüklemini ve altküme yüklemini aynı dosyaya yazarak aşğıdaki sorgulamaları yapınız:
altkume([a,b,c],[x,a,g,b,f,c,k]).
altküme([1,5,10],[10,5,1,4]).
altküme([1,5,10],[10,5]).
Evirme (negation)
Bazı koşulların doğru olmadığını bulmak faydalı olabilir. Bu durum prologda “not” yüklemi veya
“+” sembolleriyle sağlanır. not’ın anlamı: verilen gerçek ve kuralları kullanarak koşulun “doğru” olduğunu ispatlamak olası değildir, bu nedenle “yanlış”tır. Bu kapalı dünya kabulu olarak bilinir. Örneğin; D doğu, B batı, G güney, K kuzey şeklinde 4 duvarlı bir oda yüklemini oda(D,B,K,G) şeklinde tanımlayalım. Her değişken; kapı için ‘k’, duvar için ‘d’, pencere için ‘p’ değerlerden birini alabilsin. Eğer kuzeyde kapısı olmayan bir oda istiyorsak aşağıııdaki kuralı yazabiliriz:
oda1(D,B,K,G) :- oda(D,B,K,G),
not(K==k).
Oda1 kuzeye kapısı olmayan odaları içerir. Oda1 yüklemini test etmeden önce oda yüklemini yazmak gerekir. Tüm olasılıkları belirtmek için 81 tane gerçek yazmak yerine bir yüklem tanmlayarak bu işlemi yapabiliriz.
duvar_tip(d). % duvar
duvar_tip(k). % kapı à gerçekler.
duvar_tip(p). % pencere
oda(D,B,K,G) :- duvar_tip(D),
duvar_tip(B), à kural
duvar_tip(K),
duvar_tip(G).
oda, oda1 kuralları ile duvar_tip gerçeklerini bir program olarak yazarak aşağıdaki sorgulamaları yapınız:
oda1(D,k,K,G). à kuzeyde kapı yok, batıda kapı var , doğu ve güney serbest.
oda1(D,B,K,G). à kuzeyde kapısı olmayan tüm odalar.
Sonuçları Göstermek
Sorgulama sonucu istediğimiz cevaplara erişmekteyiz. Bu cevapları farklı formatta yazdırmak için write yüklemini kullanabiliriz. Örneğin yukarıdaki odaları yazdırmak için yaz_oda (D,B,K,G) yüklemini aşağıdaki şekilde yazabiliriz:
yaz_oda(D,B,K,G) :- write(D), write(’ ‘),
write(B), write(’ ‘),
write(K) write(’ ‘),
write(G) write(’ ‘), nl.
Burada nl yüklemi satırbaşı yaptırmak için kullanılmaktadır. Yaz_oda yüklemi oda1 yükleminin son satırına eklenerek kullanılabilir.
Cut & Fail (Kesme ve Başarısızlık )
Prolog alternatif çözüm ve kanıtları bulacak bir sisteme sahiptir. Programları daha basit kodlarla çözebilmek için prologun davranışını değiştiren iki yüklem vardır: cut, fail.
Cut (kesme)
Cut ‘! ‘ karakteri ile gösterilir. Prolog alternatif çözümleri bulmak için geriye dönerek arama yapar (baktracting). Cut alternatif çözüm arayışını durdurur. Örneğin; 1-3 kademesinde verilen rakamı yazıyla yazdırmak için aşağıdaki program yazılabilir:
yaz(1) :- write(’bir’).
yaz(2) :- write(’iki’).
yaz(3) :- write(’üç’).
yaz(X) :- X<1, write(’Sınır dışı’).
yaz(X) :- X>3, write(’Sınır dışı’).
Bu program doğru çalışır ama herhangi bir X değeri için tüm satırlara bakılır. Yani tüm alternatifler gözden geçirilir. İstenen satır işlem gördükten sonra diğer satırlara bakılmaması Cut ile sağlanabilir:
yaz(1) :- !, write(’bir’).
yaz(2) :- !, write(’iki’).
yaz(3) :- !, write(’üç’).
yaz(_) :- write(’Sınır dışı’).
Burada arguman 1 ise ekrana “bir” yazar ve diğer cümlelere bakılmaz. write yüklemi alternatif çözümler üretmediği yalnız bir değer yazdığı için deterministiktir. Kesme işaretinin deterministik yüklemden önce veya sonra olması farketmez.
İki sayıdan büyük olanını veren max(X,Y,Z) yüklemi aşağıdaki gibi tanımlanabilir:
max(X,Y,X) :- X>=Y.
max(X,Y,Y) :- X
max(X,Y,X) :- X>=Y, !.
max(X,Y,Y).
X>=Y olduğunda birinci kural işlem görür ve kesme sembolu diğer max yüklemlerine bakılmasını engeller.
Fail (başarısızlık)
Prolog verilen soruya cevap bulmak için arama yapar ve cevabı bulursa ekrana yazar. Bulamazsa yani başarısız (fail) olursa geriye dönerek varsa alternatif çözüm yollarını dener. Aşağıdaki programı gözönüne alalım:
hayvan(kus).
hayvan(kedi).
hayvan(aslan).
yaz: hayvan(X), write(X), nl.
Programı yükleyip yaz dediğimiz zaman prolog sadece kuş yazar. Eğer geri dönerek olası tüm çözümleri yazmasını istersek fail kullanarak kuralı aşağıdaki şekilde yazabiliriz:
yaz: hayvan(X), write(X), nl, fail.
Fail prologa başarısız olduğunu başka bir çözüm bulmasını söyler. Böylece prolog tüm olasılıkları denemek zorunda kalır. Bakılacak çözüm kalmadığında program başarısızlıkla “no” yazıp durur. Eğer programın bu işlemlerden sonra başarı olduğunu belirtmek istiyorsak son satıra “yaz” ekleyerek programın “yes” ile sonlanmasını sağlayabiliriz:
hayvan(kus).
hayvan(kedi).
hayvan(aslan).
yaz: hayvan(X), write(X), nl, fail.
yaz.
Bilgi tabanını değiştirme
Prolog’un en büyük gücü programların kendilerini değiştirebilme yeteneğidir. Programlar gerçek ve kurallara bağlı olarak çalıştığı için bunların değiştirilmesi veya yenilerinin eklenmesi programın işleyişini değiştirecektir. Assert, asserta ve assertz bilgi tabanına ekleme yapmak için kullanılır. Assert bulunulan pozisyona, asserta başlangıca, assertz ise sona ekleme yapar. Örneğin yukarıda verilen programa aşağıdaki ifade ile bir gerçek eklenebilir:
assert(hayvan(sinek)).
Bilgi tabanından çıkarma işlemi için retract kullanılır. Örneğin kedi’yi bilgi tabanından silmek için aşağıdaki ifadeyi yazabiliriz:
retract(hayvan(kedi)).
Ekleme ve silme işlemlerinin yapılabilmesi için yüklemlerin dinamik olduğunun prrogramın başında belirtilmesi gerekir. hayvan yüklemi aşağıdaki şekilde dinamik olarak tanımlanabilir:
:- dynamic hayvan/1.
Burada 1 sayısı hayvan yükleminin arguman sayısıdır.
Herhengi bir yüklemle ilgili tüm cümleleri silmek için abolish yüklemi kullanılır. Örneğin bilgi tabanındaki tüm hayvan tanımları aşağıdaki ifade ile silinebilir.
Abolish(hayvan/1).
Ekleme ve silme işlemleri program çalışırken bellekte yapıldığı için yazdığınız program değişmeyecektir. İstenirse programın son hali bir dosyaya yazdırılabilir.
Terim okuma: read
read yüklemi prolog terimlerinin tuş takımından okunmasını sağlar. Tuş takımından girilen bilginin formatı program yazarken kullanılan formatın aynısı olamalıdır ve nokta ile sonlandırılmalıdır.
?- read(X). à soru
selam. à kullanıcı girişi
X = selam à X değeri
yes. à sonuç
Eğer read yükleminin argumanına bir değer atanmış ise prolog bu değer ile girilen değeri karşılaştırır:
?- read(evet). ?- read(evet).
evet. hayır.
yes no
Örneklerde görüldüğü gibi girilen değer argumanla aynı ise yes farklı ise no sonucu elde edilmektedir. Bu nedenle programın çalışması sırasında kullanıcıya sorulan evet/hayır tipindeki sorularda herhangi bir ek kontrol yapmadan programın işleyişi düzenlenebilir.
Örnek programlar:
Öğrenen program
Öğrenen program kendi bilgi tabanını değiştiren programdır. Bu amaçla önce başkentlerin saklandığı bir bilgi tabanı hazırlayalım:
:- dynamic (baskent/2).
baskent(turkiye,ankara).
baskent(irak, tahran).
baskent(yunanistan, atina).
Bu bilgi tabanını “bt.pl” ismiyle kaydedelim. Hazırladığımız BT’yi kullanan ve gerektiğinde ekleme yapan program aşağıdaki şekilde yazılabilir.
% Baskent programı
basla :- reconsult(’bt.pl’), nl,
write(’isimleri küçük harfle yazın ve nokta ile sonlandırın’),nl,
write(’cıkış için “dur.” yazınız’), nl, nl,
sorgula.
sorgula :- write(’Ulke? ‘),
read(Ulke),
cevap(Ulke).
% Kullanıcı “dur.” yazdı ise bt’yi sakla ve çık.
cevap(dur) :- write(’ BT saklanıyor…’), nl,
tell(’bt.pl’), àçıkış dosyaya yönlendiriliyor.
write(’:-dynamic( baskent/2).’), nl,
listing(baskent), à tüm baskentler listeniyor.
told, à dosya kapatıldı.
write(’saklandı.’), nl.
% Eğer baskent kb’de ise göster ve sorgula’ya dön.
cevap(Ulke):- baskent(Ulke,Sehir),
write(Ulke),
write(’ nin baskenti ‘),
write(Sehir), nl, nl,
sorgula.
% Eğer baskent kb’de yok ise kullanıcıya sor kb’ye ekle ve sorgula’ya dön.
Cevap(Ulke):- + baskent(Ulke,_),
write(’Bilmiyorum, yardımcı olurmusunuz..’),nl,
write(’Baskent? ‘),
read(Sehir),
write(’tesekurler’), nl, nl,
assertz(baskent(Ulke,Sehir)),
sorgula.
PROBLEM ÇÖZME
Arama ile Problem Çözme
Temel refleks ajan daha sonraki durumları gözönüne almaz. Refleks ajanın eylemi o anki algılamalarının bir sonucudur. Üstelik ne eylemlerinin sonucu hakkında bir bilgisi ne de amacını bilmektedir. Bu bölümde amaç tabanlı ajanın bir türü olan problem çözme ajanı (PÇA) tanımlanacaktır. PÇA istenen duruma erişmek için ne yapmak gerektiğine eylem sırasını bularak karar verir.
Problem Çözme Ajanı - PÇA
Çevre durum değiştirirken zeki ajanların performans ölçüsünü maksimize edecek şekilde davrandıkları kabul edilir. Bu tanıma bağlı olarak başarılı ajan tasarımı güçtür. Ajana bir amaç verilirek tasarım basitleştirilebilir. İzmit’ten İzmir’e gitmek bir amaç olarak verilirse izlenebilecek çok sayıda yol bulunabilir. Yürüyerek gitmek de seçeneklerden biri olabilir. Ama İzmir’e varılması gereken zaman belirtilirse ajan başarısızlıkla sonuçlanacak yürüme seçeneğini dikkate almayacaktır. Amaçlar ajanın göz önüne alacağı seçenekleri sınırlayarak davranışlarını organize etmede yardımcı olur. Bu işlem için amacın formülize edilmesi gerekir. Amaç formülasyonu problem çözmede ilk adımdır.
Amaç bir durum olarak düşünülebilir. Eylemler ise durumlar arasında geçiş yapmayı sağlar. Bir şehirden diğerine gitmek için 100m ileri git, sağa dön, 50m ilerle şeklinde çok ayrıntılı eylemleri dikkate alırsak park yerinden dışarı çıkamayız. Ajanın eylemini bir şehirden diğerine gitmek şeklinde üst seviyede düşünürsek, durumlar herhangi bir şehirde bulunmak olacaktır. Problem formülasyonu istenen amaca erişmek için hangi durum ve eylemlerin gözönüne alınacağını belirleme işlemidir.
Herhangibir durumdan istenilen duruma varmak için olası eylem sıralarını deneyerek en iyi olanını seçme işlemine arama (searching) denir. Arama algoritmaları problemi giriş olarak alır ve çözümü eylem sırası olarak verir. Çözüm bulunduktan sonra önerilen eylemler icra edilir ( icra aşaması). Böylece ajan için “formülize etme, arama ve icra” şeklinde bir tasarım elde edilir.
Problemlerin Formülüze Edilmesi
Bilgi ve Problem Tipleri
Çevre olarak temizlik dünyasını ele alalım. Bu dünyada yalnız iki yer vardır. Herbir yerde kir olabilir veya olmayabilir. Ajan iki yerin birinde bulunabilir. Aşağıdaki şekilde görüldüğü gibi 8 farklı dünya durumu vardır.
Süpürge
Süpürge
Kir
Kir
Kir
Kir
Süpürge
Süpürge
Kir
Kir
Süpürge
Süpürge
Kir
Kir
Süpürge
Süpürge
Basitleştirilmiş temizlik dünyasında 8 olası durum
Temizlik dünyasında ajan 3 farklı eylemde bulunabilir: sağ, sol ve em. Şimdilik emmenin %100 başarılı olduğunu kabul edelim. Amaç bütün kiri temizlemektir. Yani amaç {7,8} durum kümesine eşittir.
İlk olarak ajanın sensorları ile hangi durumda olduğunu tespit edebildiğini kabul edelim (erişimli dünya). Aynı zamanda ajan eylemlerinin ne sonuç vereceğini de kabul edelim. Bu durumda ajan izleyeceği herhangi bir eylem sırası sonucunda hangi duruma erişeceğini hesaplayabilir. Örneğin başlangıçta 5. Durumda ise [sağ, em ] eylem sırasının amaç durumuna getireceğini hesaplayabilir. Bu en basit durumdur ve tek durumlu problem (single-state problem) olarak adlandırılır.
İkinci olarak, ajanın eylemlerinin sonucunu bildiğini ama bulunduğu durumu tespit edemediğini kabul edelim. Ajan başlangıç durumunun {1,2,3,4,55,6,7,8} durum kümesindeki herhangi bir durum olduğunu bilir. Bu şartlar altında bile ajan çalışabilir. Çünkü sağ eyleminin sonucunda {2,4,6,8} durumlarından birine erişeceğini hesaplayabilir. Aslında başlangıç durrumu ne olursa olsun [sağ, em, sol, em] eylemleriyle ajan amaç duurumuna erişir. Özetle, dünya tam olarak erişimli değil ise ajan bir durum yerine içinde bulunabileceği durumları tahmin edebilmelidir. Bu çok durumlu problem (multiple-state problem) olarak adlandırılır.
Ajanın pozisyon ve kir sensörü olduğunu ama diğer karedeki kiri algılayamadığını kabul edelim. Sensörün {1,3} durumlarından birinde buluunulduğunu söylediğini kabul edelim. Ajan eylem sırasını [em, sağ, em] şeklinde formülize edebilir. Emme eylemiyle {5,7} durumlarından birine geçilir. Sağa hareket edildiğinde {6,8} durumlarından birine geçilir. Gerçekte 6 durumunda ise eylem sırası başarılı olacak 8 durumunda ise başarısız olacaktır. Bu nedenle problemin çözümünü garanti eden sabir bir eylem sırası yoktur.
Ajanın {1,3} durumunun birinden başlayarak problemi çözmesinin yolu vardır: em, sağa git, eğer kir var ise em. Yani problemin çözülmesi icra aşamasında algılama gerektirir. Ajanın bir eylem yerine tüm eylem ağacını hesaplaması gerektiğine dikkat ediniz. Genel olarak, ağacın her dalı doğabilecek koşula bağlıdır. Bu tip problemler koşullu problem (contingency problem) olarak adlandırılır. Gerçek dünyadaki bir çok problem koşullu problemdir, çünkü mutlak tahmin imkansızdır. Bu nedenle insanların çoğu yürürken veya araba kullanırken gözlerini açık tutar.
Tek durumlu ve çok durumlu problemler benzer arama teknikleri kullanılarak çözülürler. Koşullu problemler ise çok daha karmaşık algoritmalar gerektirir. Ajan garantili çözümü bulmadan eylem yapmak zorunda kalabilir. Ajan tam çözümü bulmadan eylem yapmaya başlar icra aşamasında önüne çıkan koşullara bağlı olarak yeni eylemde bulunur. Diğer deyişle arama ve icra dönüşümlü olarak yapılır.
So olarak ajanın eylemlerinin etkileri hakkında bilgisi olmadığını kabul edelim. Bu bilinmeyen bir ülkede haritasız dolaşmaya benzer. Ajan gerçek dünyada eylemlerinin sonuçlarını ve farklı durumları yaşayarak öğrenecektir. Bu zeki ajanlar için en zor görevdir. Dikkatsiz bir ajan büyük tehlikelerle karşılaşır eğer ölmezse çevrenin haritasını çıkararak daha sonraki eylemleri için kullanabilir. Bu tip problemler keşif problemi (exploration) olarak adlandırılır.
İyi Tanımlanmış Problemler ve Çözümleri
Problem, ajanın ne yapacağına karar verirken kullanacağı bilgiler kümesidir. Problem tanımlamanın temel elemanları durumlar ve eylemlerdir:
Ajanın içinde bulunduğunu bildiği duruma başlangıç durumu (initial state) denir.
İşlem herhangi bir durumda yapılacak eylemle erişilecek durum şeklinde eylemi tanımlanamak için kullanır. Alternatif formülasyon S izleme fonksiyonu (successor function)dur. S(x); bir eylemle verilen x durumundan geçilebilecek durumların kümesini verir.
Başlangıç durumundan eylem sırası ile erişilebilecek durumlara problemin durum uzayı ( state space) denir. Durum uzayında yol (path) bir durumdan diğerine geçişi sağlayan eylem sırasıdır.
Amaç testi, ajanın istenen duruma erişilip erişilemediğini saptamada kullanacağı durum tanımıdır. Amaç durumu birden fazla ise herhangibirine erişilip erişilemediği test edilir. Amaç bazen soyut bir özellik de olabilir. Örneğin santrançta amaç şah mat durumuna erişmektir.
Birden fazla yol izlenerek amaca erişilebiliyor ise daha kısa veya az maliyetli olan seçilir. Yol maliyet (path cost) fonksiyonu yola bir maliyet atar.
Başlangıç durumu, İşlem kümesi, amaç testi ve yol maliyet fonksiyonu problemi tanımlar. Problemi temsil etmek için bu elemanlardan oluşan bir veri tipi tanımlanabilir.
veri tipi : problem
elemanları : Başlangıç-Durumu, İşlem-Kümesi, Amaç-Testi, Yol-Maliyet-Fn
Arama algoritmasının çıkışı başlangıç durumundan amaç testini sağlayan duruma olan yoldur yani çözüm dür.
Poblem Çözme Performansının Ölçülmesi
Aramanın etkinliği en az üç şekilde ölçülebilir:
Hiç çözüm buldu mu ?
Düşük yol maliyetli iyi bir çözüm mü ?
Problemi çözmek için gerekli zaman ve belleğe ilişkin arama maliyeti (search cost) nedir?
Toplam maliyet (total cost), arama maliyeti ile yol maliyetinin toplamıdır.
İki şehir arasında izlenecek güzergahı tespit etmede yol maliyeti kilometre olabilir. Arama maliyeti ise yolun durumu veya yapılabilecek hız olabilir. Toplam maliyeti hesaplarken kilometre ile dakikayı toplamak gerebilir. Bu durumda ajan hangisine daha fazla ağırlık vereceğini tespit etmelidir.
Durum ve Eylemlerin Seçilmesi
Romanya’nın basitleştirilmiş yol haritası.
Yukarıdaki şekilde verilen haritada A’dan B’ye gitmek şeklinde basit bir problemle başlayalım. Uygun durum uzayı her durumun bir yeri gösterdiği 20 duruma sahiptir. Başlangıç durumu “A”dır. Amaç testi “B mi?” dir. İşlemler şehirler arasındaki yollarda araba sürmeye karşı gelir.
Bir çözüm yolu AàSàRàPàB şeklindedir. Çözüm için bir çok yol vardır. Bu çözümlerin en iyisinin hangisi olduğuna karar vermek için yol maliyet fonksiyonunun neyi ölçtüğünü bilmek gerekir. Bu mesafe veya beklenen zaman olabilir. Mevcut haritada bunların hiç biri tanımlanmadığı için adım sayısını maliyet fonksiyonu olarak alabiliriz. S ve F’den geçen yolun maliyeti 3 olduğu için en iyi çözümdür.
Burada, durum tanımında yol ve hava durumu sürücünün aç olup olmadığı gibi detaylar B’ye giden bir yol bulma problemi ile ilgili olmadığı için dikkate alınmamıştır. Gösterimden detayların çıkarılması işlemine soyutlama (abstraction) denir. Durum tanımı soyutlandığı gibi eylemler de soyutlanmalıdır. A’dan Z’ye gitmenin aracın yer dağiştirmesi, yakıt eksilmesi, kirlilik yaratması gibi bir çok etkisi vardır. Formülasyonda yalnız yer değiştirme dikkate alınacaktır. İyi bir soyutlama, soyut eylemlerin kolayca yapılabileceği şekilde mümkün olduğu kadar detayın çıkarılmasını gerektirir.
Örnek Problemler
Problemler; değişik problem çözme yöntemlerini denemek amacıyla kullanılan oyuncak problemler (toy problems) ve çözümü daha güç olan ve insanlar için önemli olan gerçek dünya problemleri (real-world problems) olamak üzere ikiye ayrılabilir. Oyuncak problemlerin tanımı iyi bir şekilde yapılabildiği için algoritmaların performansını karşılaştırmak için değişik araştırmacılar tarafından kullanılabilir. Gerçek dünya problemlerinin ise üzerinde anlaşılmış tek bir tanımı yoktur.
Oyuncak Problemler
8-puzzle
8-puzzle, 3*3′lük tahtada 1′den 8′e kadar numaralandırılmış taşlar ve bir boşluk yer alır. Taş bitişikteki boşluğa hareket edebilir.
Başlangıç durumu Amaç durum
4′ü boş yere götür yerine, boşluğu solundaki taşla değiştir demek daha az sayıda İşlem gerektirir ve daha mantıklıdır. Oyunun formülasyonu aşağıda verilmiştir:
Durumlar: Durum tanımı 8 taşın herbirinin 9 kareden birinde bulunduğunu belirtir. Boşluğun yerini belirmek de faydalı olur.
İşlemler : Boşluk sol, sağa, yukarı veya aşağı hareket edebilir.
Amaç testi : Yukarıdaki şekilde gösterilen durum.
Yol maliyeti : Her bir adımın maliyeti 1′dir. Yol maliyeti de yolun uzunluğuna eşittir.
8-Vezir Problemi
Amaç satranç tahtasına 8 veziri biribirini tehdit etmeyecek şekilde yerleştirmektir. Bu amaçla geliştirilmiş özel algoritmalar olmasına karşın n-Vezir problemleri arama algoritmalarının testinde ilgiyi korumaktadır. Temelde iki çeşit formülasyon vardır: artışsal (incremental) formülasyonda vezirler tek tek yerleştirilmektedir, tam durum (complete-state) formülasyonunda ise 8 vezir tahta üzerine yerleştirilip hareket ettirilmektedir. Sadece son durum dikkate alındığı için yol maliyeti dikkate alınmaz yalnız arama maliyetine bakılır:
Amaç testi: Tahtada birbirini tehdit etmeyen 8-vezir.
Yol maliyeti: sıfır.
Farklı durum ve İşlemler de vardır:
Durumlar: 0-8 vezirin herhangi bir düzenlemsi.
İşlemler: Herhangi bir kareye vezir koymak.
Bu formülasyonda araştırılacak 648 olası sıra vardır. Eğer İşlem:
İşlemler: Tehdit edilmeyen en soldaki boş kareye vezir koy.
Bu şekilde tehdit edilmeyen durumları tespit etmek kolaydır. Ama 7 vezirden sonra mümkün eylem kalmamaktadır. Bu nedenle arama işlemi başka bir seçeneği denemelidir. Hızlı bir hesap araştırılacak yalnız 2057 olası sıra olduğunu gösterir. Doğru formülasyon arama uzayının boyutunu büyük ölçüde küçültür.
Tehdit edilen veziri aynı kolonda başka bir kareye götürme işlemi de zaman alsa da sonunda çözümü bulur.
Kripto Aritmetik
Kripto aritmetik (cryptarithmetic) problemlerinde rakamların yerini harfler almıştır. Amaç toplama işleminin doğru olabilmesi için harflerin rakam karşılığını bulmaktır:
FORTY
TEN
+ TEN
SIXTY
29786
850
+ 850
31486
Çözüm: F = 2, O = 9, R = 7 …
Diğer örnekler:
SEND CROSS
+MORE +ROADS
MONEY DANGER
En basit formülasyon aşağıdaki gibi olabilir:
Durumlar: Bazı harflerin rakamlarla değiştirildiği kripto aritmetik bulmaca.
İşlemler: Bir harfin bulunduğu tüm yerleri bulmacada daha önce kullanılmayan bir rakam ile değiştir.
Amaç testi: Yalnız rakamlardan oluşan bulmaca doğru aritmetik sonucu veriyor.
Yol maliyeti: Sıfır. Tüm çözümler aynı geçerlilikte.
Misyonerler ve Yamyamlar ( Missionaries & cannibals)
Problem şu şekilde tanımlanır: 3 misyoner ve 3 yamyam nehrin bir kenarındadır ve bir veya iki kişiyi taşıyabilecek bir bot vardır. Misyonerlerin sayısı herhangi bir yerde yamyamların sayısından az olmayacak şekilde herkesin nehrin karşısına geçebilmesinin yolunu bulunuz.
Bu problem, problem formülasyonuna analitik açıdan yaklaşan ilk makalenin konusu olduğu için çok ünlüdür ( Amarel,1968). Problem çözme yöntemlerini uygulamadan önce gerçek yaşam problemlerinin soyutlanması gerekir.
Şöyle bir sahne hayal edelim: Arawaskan kabilesinin üç üyesi, Alice, Bob ve Charles timsah kaynayan Amazon nehrinin kenarında yeni arkadaşları Xavier, Yolanda ve Zelda ile durmaktadır. Bu esnada yağmur yağmakta ve kuşlar ötmektedir. Xavier, Yolanda ve Zelda misyonerdir ve yeni arkadaşlarına yalnız veya az sayıda yakalanırlarsa ne olacağı konusunda şüpheleri vardır. Hepsi kıyaya bağlı küçük teknenin nehrin iki yakasında geçişi sağladığı konusunda emin değillerdir.
Bu problemi formülüze etmek için: ilk adım yağmur, timsah gibi çözüme etkisi olmayan tüm detayları ihmal etmektir. Bir sonraki adım doğru işlem kümesinin ne olduğuna karar vermektir. İşlemin bir veya iki kişiyi botla nehrin karşısına geçirmek olduğunu biliyoruz. Ama, botun içinde geçen zamanı gösteren bir duruma gereksinim olup olmadığına karar vermemiz gerekir. Botta iki kişi olabileceği için yamyamlar sayıca misyonerlerden fazla olamaz. Bu nedenle geçişin sadece uç noktaları önemlidir. Bireylerin de soyutlanması gerekir. Çözüm için misyonerlerin veya yamyamların isimleri gereksizdir. 3 misyoner ve 3 yamyamın herhangii bir permütasyonu aynı sonucu verir. Bu yaklaşımla problem aşağıdaki şekilde tanımlanabilir:
Durumlar: Durum, misyonerlerin ve yamyamların sayısı ile botun nehrin hangi kenarında olduğunu gösteren 3 rakamdan oluşur. Başlangıç durumu (3,3,1) dir.
İşlemler: Her durumda olası işlemler; bir misyoner, bir yamyam, iki misyoner, iki yamyam veya herbirinden birer kişiyi botla karşı kıyıya geçirmektir.
Amaç testi: (0,0,0) durumuna erişmek.
Yol maliyeti: Nehri geçiş sayısı.
Durum uzayı oldukça küçük olduğu için bu problem bilgisayarla çözülebilir.
Temizlik Dünyası (Vacuum world)
Bu problem daha önceki bölümde anlatılmıştı.
Hanoi Kulesi ( Tower of Hanoi)
…
Maymun ve Muz problemi (Monkey & Bananas)
Aç bir maymun tavandan muzların asılı olduğu bir odadadır. Odada sandelye ve sopa vardır. Maymunun sandelye üzeerine çıkarak sopayla muzları düşürüp yiyebilmesi için izleyeceği en iyi eylem sırası nedir.
Gerçek Dünya Problemleri
Rota Bulma
Rota bulma algoritmaları; bilgisayar ağları, otomatik seyahat tavsiye sistemleri, havayolu seyahat planlama sistemleri gibi değişik alanlarda kullanılmaktadır. Havaylu uygulaması çok karmaşıktır çünkü yol maliyeti çok karmaşıktır; para, yer kalitesi, zaman, uçak tipi, indirimler .. .Üstelik problemdeki eylemler de tamamen bilinen çıktıları vermez: uçuş geçikebilir, bağlantılar kaçırılabilir, sis veya acil durumlar gecikmeye neden olabilir.
Turlama ve gezen satıcı (travelling salesperson) problemi
Haritada verilen her şehri, B şehrinden başlayıp bitecek şekilde, en az bir kere ziyaret et şeklinde probleme bakalım. Bu rota bulma problemine benzemektedir, her ikisinde de iki şehir arasında seyahat edilmektedir. Ama bu problemde daha fazla bilginin kaydedilmesi gerekir. Ajanın yerine ek olarak, her bir durum ajanın ziyaret ettiği şehirleri de izlemelidir. Amaç testi 20 şehri de ziyaret ettikten sonra B’ de olmaktır.
Gezen satıcı problemi (TSP) ünlü bir turlama problemidir. Amaç en kısa turu bulmaktır. Satıcıların gezilerini planlamaya ek olarak bu algoritmalar otomatik baskılı devre delme düzeneklerinin hareketlerinin planlanmasında da kullanılır.
VLSI çip tasarımı
Silikon çiplerin tasarımı en karmaşık mühendislik işlemlerinden biridir. VLSI çipinde milyonlarca kapı yer alır. Herbir kapının pozisyonu ve bağlantıları çipin başarılı çalışması için hayati önem taşır. İşlrmin her aşamasında CAD kullanılır. En güç işlerden ikisi hücrelerin yayılımı ( cell layout) ve bağlantılarıdır (channel routing). Yayılımdan amaç, kullanılan alanı ve bağlantı uzunluklarını en aza indirerek hızı artırmaktır. Bağlantılar hücreler arasndaki boşlukları kullanarak yapılır. Bu problemler çok karmaşık olmasına rağmen çözmeye değer.
Robot Hareketi
Robot hareketi rota bulma probleminin genel halidir. Düz bir yüzeyde hareket eden dairesel robotda uzay iki boyutludur. Robotun kontrol edilecek kol ve bacakları var ise arama uzayı çok boyutlu olur. Arama uzayını sınırlandırmak için ileri teknikler kullanmak gerekir. Problemin karmaşıklığına ek olarak gerçek robot sensorlardan ve motor kontrolünden gelen hatalarla da uğraşmalıdır.
Montaj Sırası (Assembly sequencing)
Karmaşık nesnelerin robotla birleştirilmesi ilk kez FREDDY robotuyla (Michie,1972) gerçekleştirilmiştir. İlerleme yavaş olmasına rağmen, elektrik motorlarının montajı ekonomiktir. Montaj problemlerinde, problem bir nesnenin parçalrını birleştirmek için gerekli sırayı bulmaktır. Eğer sıra yanlış seçilirse sonradan bazı parçaların yerleştirilmesi olanaksız olacaktır. Tekrar başa dönmek gerekecektir.
Çözüm için Arama
Şimdiye dek problemi nasıl tanımlayabileceğimizi ve çözümün ne olduğuna baktık. Geriye çözümün bulunması kalmıştır. Bu da durum uzayında yapılacak arama işlemidir.
Eylem Sırasını Üretmek
Daha önce verilen harita üzerinde A’dan B’ye rota bulma probleminini çözmek için başlangıç durumu A’dan yola çıkılır. İlk adım bunun amaç durum olup olmadığını test etmektir. Böylece “A’dan başlayarak A’ya gitmek” gibi hileli sorular da çözülebilir. Bu amaç durum olmadığı için diğer durumlara bakılması gerekmektedir. O anki durum üzerinde işlemler yaparak yeni durum kümeleri üretilir. Bu işleme durumun açılması (expanding) denir. Bu şekilde 3 yeni duruma erişilir: S, T ve Z. Yeni durumlar A’ya bir adım uzaklıktadır. Eğer yalnız bir seçenek varsa o durum seçilir ve işleme devam edilir. Birden fazla seçenek varsa hangisinin dikkate alınacağına karar vermeliyiz.
Aramanın temeli: seçeneklerden birini seçmek diğerlerini kenara koymak, eğer yapılan seçim istenen sonucu vermiyorsa diğer seçeneklerden birini denemektir. Seçme, test etme ve açma işlemi çözüm bulunana veya açılacak durum kalmayana dek devam eder. Hangi durumun önce açılacağı arama stratejisi ile saptanır.
A’dan B’ye rota bulmak için kısmi arama ağacı.
Arama işlemini durum uzayının üzerine yerleştirilmiş arama ağacı olarak düşünmek yararlı olur. Arama ağacının kökü başlangıç durumuna denk gelen arama düğümüdür. Ağacın yaprak düğümleri izleyeni olmayan durumlardır. Bunlar ya henüz açılmamıştır ya da açılmış ama boş küme üretilmiştir.
Arama uzayı ve arama ağacını ayırtetmek gerekir. Rota bulma probleminde durum uzayında yalnız 20 durum vardır. Her şehir için bir durum vardır. Fakat durum uzayında sonsuz sayıda yol (path) vardır. Bu nedenle arama ağacında sonsuz sayıda düğüm vardır. Örneğin AàSàA dalı AàSà AàS şeklinde devam eder.
Arama Ağaçları için Veri Yapıları
Düğümleri göstermenin birçok yolu vardır. Ama burada düğümü beş elemanlı bir veri yapısı olarak ele alacağız:
Düğümün durum uzayındaki durum karşılığı,
Bu düğüm (parent node)tarafından üretilen arama ağacındaki düğüm,
Bu düğümü üretmek için yapılan işlem,
Kökten bu düğüme kadar olan yoldaki düğüm sayısı (derinlik-depth)
Başlangıç durumundan bu düğüme olan yolun yol maliyeti.
Düğüm ve durum farklıdır. Düğüm; özel bir algoritma tarafından bir problem için üretilen arama ağacını gösteren kayıt veri yapısıdır. Durum dünyanın konfigürasyonunu temsil eder. Düğümde derinlik ve parent vardır, durumda ise yoktur.
Açılmayı bekleyen düğümlerin de (fringe, frontier) belirtilmesi gerekmektedir. En basit gösterim düğüm kümesi olabilir. Bu düğümlerin queue olarak gerçekleştirildiğini kabul edelim. Queue üzeerinde aşağıdaki işlemler yapılır:
Make-Queue(Element) :Verilen eleman ile queue oluşturu
Tags: 12, access, açma, Algı, altın, araba, araç, aşk, başarı, bilgisayar, birlik, bölüm, Derinlik, din, ekleme, ekran, erkek, etme, fizik, form, haber, hali, hasta, hastalık, hata, hayvan, hepsi,