Yapay Zeka 6: Koşul Tatmin Problemleri (CSP)

Bu Bölümde Doç.Dr.Şadi Evren Şeker Constratint Satisfaction Problems olarak da geçen (Kitapta 5.Bölüm olarak yer almaktadır) problem tiplerini ve çözüm yöntemlerini anlatıyor. Basitçe gerçek hayatta bu tip problemlerle kaşılaşılabilecek, eşleşme problemleri (matching problems), zamanlama problemleri, planlama problemleri, zaman çizelgelemesi, kaynak atama, iş atama problemleri gibi problemleri ve çözüm için bir koşul tatmin probleminin nasıl bir graf haline dönüştürüldüğü, problem tiplerini (ayrık veya sürekli) veya değişken sayılarına göre problem tiplerini (unary, binary highorder) ve arama algoritmaları ve yerel arama sezgisel algoritmaları ile nasıl çözüldüğü bu bölümde anlatılmıştır.  

Daha önce öğrendiğimiz DFS, BFS gibi algoritmalar ve hill climbing, local beam search veya simulated annealing gibi algoritmaların koşul tatmini için nasıl kullanılabileceğini ve bu algoritmalar üzerinde geri izleme (back-tracking) veya koşul yayılımı (constraint propogation) veya MCV (most constraining variable), LCV (least constraining variable) gibi kavramlar bu derste anlatılmaktadır.

HARİTA RENKLENDİRME PROBLEMİ:

Avusturalya haritasında yer alan boşluklar en az kaç farklı renkle (komşu ülkeler farklı renkte olmak şartıyla) boyanabilir?

harita-renklendirme

Yapay Zeka çalışmalarına kadar bu problemin çözümünün 3 farklı renk olduğu ispatlanamamıştı..

example-map-coloring

CRYPTARITHMETIC

cryptarithmetic

Gerçek Dünyadaki CSP problemleri:
*Atama sorunları (Hangi öğretmenler, hangi sınıfta?)
*Zaman paylaşımı sorunları (Hangi sınıf, ne zaman ve nerede?)
*Nakliyat sorunları
*İmalat planlama

Gerçek dünya sorunlarının büyük kısmı gerçek değerli değişkenlidir

GERİ İZLEME ÖRNEĞİ (BACKTRACKING EXAMPLE): 

australia-backtrack

Koşul Tatmin Problemleri aşağıdaki sorunların özel türüdür:
   Durumlar, belirlenmiş değişkenler kümesinin değerleri ile tanımlanır
   Amaç denemesi, değişkenin değerlerine koyulan sınırlamalarla tanımlanır.
Geriye izleme algoritması = her düğümde bir değişkene değer atamakla derinine arama

Değişkenlerin sırasını ve değer seçimini sezgisel yöntemlerle gerçekleştirmek çözüme yardım eder
İleriyi yoklama, sonradan oluşabilecek başarısızlıklara neden olacak atamaları önler
Kısıtların yayılması (kenarların tutarlığı) değerleri sınırlamaya ve tutarsızlıkları ortaya çıkarmaya yardım eder
En az zıtlık (min-conflicts) pratik olarak etkilidir ve başlangıç durumu verildiğinde çoğu problemde çok hızlı ve verimli çalışır

Bunları da sevebilirsiniz

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir