Yapay Zekâ 6: Koşul Tatmin Problemleri (CSP)

0
1578

Bu Bölümde Doç.Dr.Sadi Evren Şeker Constratint Satisfaction Problems ( Koşul Tatmin Problemleri ) 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.  

Ayrıca bkz;
1. Ders (Yapay Zekâ 1: Giriş, Dersin İçeriği ve İnsan / Rasyonellik Ayrımı)
2. Ders (Yapay Zekâ 2: Zeki / Akıllı Ajanlar (Intelligent Agents))
3. Ders (Yapay Zekâ 3, Dr. Racket (Lisp) Giriş)
4. Ders (Yapay Zekâ 4: Arama Problemleri)
5. Ders (Yapay Zekâ 5: Sezgisel Algoritmalar)

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

 

Dersin anlatımını yazıya döken Müslüm Yıldız‘a teşekkürler

Facebook Yorumları