Geri İzleme ve Dal-Sınır Yöntemi
Geri izleme ve dal-sınır yöntemleri, aday çözüm uzayını bir ağaç olarak keşfeden sistematik arama paradigmalarıdır. Bu yöntemler, geçerli veya optimal bir çözüme yol açamayacak alt ağaçları budayarak, aksi takdirde üstel olan aramaları pratikte yönetilebilir hale getirmektedir.
Tanım
Geri izleme, kısmi aday çözümler ağacının derinlemesine bir aramasıdır ve kısmi adayın geçerli bir çözüme tamamlanamayacağı anda bir dalı budar; dal-sınır yöntemi ise bunu hedefe ilişkin sayısal sınırlar ile genişleterek, mümkün olan en iyi değeri mevcut en iyi çözümü geçemeyen dalların elenmesini sağlar.
Kapsam
Bu konu, bir arama ağacı etrafında organize edilmiş kapsamlı arama tekniklerini ele almaktadır: kısmi adayları bir kısıtlamayı ihlal ettikleri anda terk eden geri izleme ve optimizasyonda alt ağaçları budamak için en iyi ulaşılabilir hedefin sınırlarını kullanan dal-sınır yöntemi. Kısıt tatmini örneklerini (N-vezir problemi, çizge renklendirme, Sudoku) ve kombinatoryal optimizasyon örneklerini (gezgin satıcı problemi, tam sayı programlama) içermekte olup, en kötü durumdaki üstel maliyete rağmen bu yöntemlerin NP-zor problemler için neden değerli kaldığını tartışmaktadır.
Temel sorular
- Bir problemin çözüm uzayı, kısmi atamaların bir arama ağacı olarak nasıl modellenmektedir?
- Hangi kısıt kontrol mekanizmaları, geri izlemenin uygulanamaz dalları erken budamasını sağlamaktadır?
- Optimizasyonda dalları budamak için alt ve üst sınırlar nasıl hesaplanmaktadır?
- Dallanma ve sınırlama sırası pratik performansı nasıl etkilemektedir?
- En kötü durumdaki üstel maliyetlere rağmen bu yöntemler neden NP-zor problemler için kullanılmaktadır?
Anahtar kavramlar
- arama ağacı
- derinlemesine keşif
- kısıt yayılımı
- budama
- sınırlama fonksiyonları
- mevcut en iyi çözüm
- N-vezir problemi
- tam sayı programlama gevşetmesi
Temel kuramlar
- Arama ağacının budanması
- Her iki paradigma da aday çözümleri derinlemesine keşfedilen bir ağaç olarak organize etmektedir; doğruluk kapsamlılıktan gelirken, verimlilik geçerli veya iyileştirici bir çözüm içeremeyeceği kanıtlanmış alt ağaçların budanmasından kaynaklanmaktadır.
- Dal-sınır yöntemindeki sınırlama fonksiyonları
- Dal-sınır yöntemi, şimdiye kadar bulunan en iyi çözümü ve her alt ağaçta elde edilebilecek en iyi değere ilişkin bir sınırı (örneğin bir LP gevşetmesi) korumaktadır; bir alt ağaç, sınırı mevcut en iyi çözümü iyileştiremediğinde elenmektedir.
Klinik önem
Dal-sınır yöntemi, operasyonel araştırmalardaki kesin kombinatoryal optimizasyonun omurgasını oluşturmaktadır; buna çizelgeleme, yönlendirme ve planlama için kullanılan tam sayı ve karma tam sayı programlama çözücüleri de dahildir. Geri izleme ise kısıt çözücülerin, SAT tarzı aramaların, bulmaca çözücülerin ve ayrıştırıcıların temelini oluşturur; bu alanlarda budama ile sistematik arama, kesin yanıtlara ulaşmanın pratik yoludur.
Tarihçe
Geri izleme, 1950'li ve 1960'lı yıllarda Golomb ve Baumert tarafından özellikle tanımlanarak genel bir teknik olarak sistemleştirilmiştir. Dal-sınır yöntemi ise 1960 yılında Ailsa Land ve Alison Doig tarafından tam sayı doğrusal programlama için tanıtılmış ve o zamandan beri kombinatoryal optimizasyonun merkezi bir parçası haline gelerek modern karma tam sayı programlama çözücülerine güç vermektedir.
Öne çıkan isimler
- Ailsa Land
- Alison Doig
- Solomon Golomb
- Robert Bixby
İlgili konular
Temel eserler
- landdoig1960
- cormen2009
Sıkça sorulan sorular
- Geri izleme ile dal-sınır yöntemi arasındaki fark nedir?
- Geri izleme genellikle uygulanabilirlik ve kısıt tatmini problemleri için kullanılmakta ve kısıtlamaları ihlal eden dalları budamaktadır. Dal-sınır yöntemi ise optimizasyonu hedeflemekte ve ek olarak sayısal sınırlar kullanarak budama yapmakta, mümkün olan en iyi hedef değeri zaten bulunmuş olan en iyi çözümü geçemeyen herhangi bir alt ağacı elemektedir.
- Bu yöntemler en kötü durumda üstel ise, neden kullanılmaktadır?
- NP-zor problemler için polinom zamanlı kesin bir algoritma bilinmemektedir, ancak etkili budama gerçek örneklerde arama ağacının büyük çoğunluğunu sıklıkla ortadan kaldırmaktadır; bu nedenle dal-sınır ve geri izleme çözücüleri, kanıtlanabilir optimal çözümleri en kötü durum sınırlarının önerdiğinden çok daha hızlı bulabilmektedir.