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?
Yapay Zeka çalışmalarına kadar bu problemin çözümünün 3 farklı renk olduğu ispatlanamamıştı..
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):
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
