Kısıtlılık Sağlama Problemleri
Bir kısıtlılık sağlama problemi, birçok kombinatoryal problem için tek tip bir temsil sağlayarak, bir değişken kümesine atanan değerlerin aralarındaki tüm kısıtları aynı anda karşılamasını gerektiren bir problem türüdür.
Tanım
Bir kısıtlılık sağlama problemi, bir değişken kümesinden, her biri için olası değerlerin bir etki alanından ve izin verilen değer kombinasyonlarını belirten bir kısıtlar kümesinden oluşmaktadır; bir çözüm, hiçbir kısıtı ihlal etmeyen eksiksiz bir atamadır.
Kapsam
Bu konu, kısıtlılık sağlama problemi (KSP) formalizmini (değişkenler, etki alanları, kısıtlar) ve onu çözen algoritmaları kapsamaktadır: değişken ve değer sıralama sezgisel yöntemleriyle geri izlemeli arama, kısıt yayılımı ve tutarlılık teknikleri (AC-3 algoritması gibi düğüm, yay ve yol tutarlılığı) ve problem yapısının kullanılması (ağaç yapılı KSP'ler, kesit koşullandırma (cutset conditioning)). KSP'ler için yerel arama ve kısıt programlamanın daha geniş uygulamalarıyla bağlantılıdır. Benzer problemlerin sürekli optimizasyon ve öğrenme tabanlı formülasyonları bu kapsamın dışındadır.
Temel sorular
- Çeşitli problemler (çizelgeleme, harita renklendirme, bulmacalar) değişkenler, etki alanları ve kısıtlar olarak nasıl tek tip bir şekilde ele alınmaktadır?
- Kısıt yayılımı, geri izlemeyi azaltmak için arama öncesinde ve sırasında değerleri nasıl budamaktadır?
- Hangi değişken ve değer sıralama sezgisel yöntemleri, geri izlemeli aramayı verimli hale getirmektedir?
- Kısıt grafiğinin yapısı (örneğin, ağaç şeklinde olması) verimli çözüm için nasıl kullanılabilmektedir?
Anahtar kavramlar
- değişkenler, etki alanları, kısıtlar
- kısıt grafiği
- geri izlemeli arama
- ileri kontrol
- yay tutarlılığı ve AC-3
- minimum kalan değerler sezgiseli
- kısıt yayılımı
- ağaç yapılı KSP'ler ve kesit koşullandırma (cutset conditioning)
Temel kuramlar
- Yay tutarlılığı ve kısıt yayılımı
- Bir KSP, her değişkenin her değerinin her komşu değişkende tutarlı bir eşleşmeye sahip olması durumunda yay tutarlıdır; AC-3 gibi algoritmalar, desteklenmeyen değerleri tekrar tekrar kaldırarak bunu sağlamaktadır, bu da genellikle arama öncesinde veya sırasında etki alanlarını önemli ölçüde küçültmektedir.
- Sezgisel yöntemlerle geri izlemeli arama
- KSP'ler, geri izlemeli derinlemesine ilk atama ile çözülmektedir; bu, en kısıtlı değişkeni (minimum kalan değerler) seçme, en az kısıtlayıcı değeri seçme gibi sezgisel yöntemler ve çıkmazları erken tespit etmek için ileri kontrol veya yayılımı araya katma yoluyla pratik hale getirilmektedir.
- Yapıdan faydalanma
- Kısıt grafiği bir ağaç olduğunda, bir KSP değişken sayısına göre doğrusal zamanda çözülebilmektedir ve ağaca yakın yapılar, kesit koşullandırma (cutset conditioning) veya ağaç ayrıştırma yoluyla bu duruma indirgenebilmektedir.
Klinik önem
KSP teknikleri, çizelgeleme ve zaman çizelgesi oluşturma, kaynak tahsisi, ürün yapılandırması, donanım ve yazılım doğrulama ve Sudoku gibi bulmaca çözücülerin arkasındaki itici güçtür; bu fikirler üzerine inşa edilen kısıt programlama dilleri ve çözücüleri, endüstriyel planlama ve yöneylem araştırmasında yaygın olarak kullanılmaktadır.
Tarihçe
Kısıt ağları, 1970'lerde sahne etiketleme ve ilişkisel tutarlılık üzerine yapılan çalışmalardan ortaya çıkmıştır; Mackworth'un 1977 tarihli makalesi düğüm, yay ve yol tutarlılığını formüle etmiştir. 1980'ler ve 90'lar boyunca alan kısıt programlamaya dönüşerek olgunlaşmış, 2006 tarihli Kısıt Programlama El Kitabı'nda pekiştirilmiş ve standart bir yapay zeka konusu olarak kalmaya devam etmektedir.
Öne çıkan isimler
- Alan K. Mackworth
- Rina Dechter
- Eugene C. Freuder
- Ugo Montanari
İlgili konular
Temel eserler
- mackworth1977
- dechter2003
- rossi2006
Sıkça sorulan sorular
- Bir kısıtlılık sağlama problemi, genel bir arama probleminden nasıl farklıdır?
- Genel bir arama problemi durumları kara kutular olarak ele alırken, bir KSP bir durumun iç yapısını kısıtlara tabi değişkenlere yapılan bir atama olarak ortaya koymaktadır. Bu yapı, KSP çözücülerinin genel aramanın faydalanamayacağı kısıt yayılımı ve sıralama sezgisel yöntemlerini kullanmasına olanak tanımaktadır.
- Yay tutarlılığı ne işe yaramaktadır?
- Yay tutarlılığı, bir değişkenin etki alanından, aralarındaki kısıt göz önüne alındığında, komşu bir değişkende uyumlu bir değeri olmayan değerleri kaldırmaktadır. Arama öncesinde ve sırasında bunu uygulamak, arama alanını budamakta ve bazen bir problemi geri izleme olmaksızın doğrudan çözebilmektedir.