Yaklaşım Algoritmaları
Yaklaşım algoritmaları, NP-zor optimizasyon problemlerini polinom zamanda çözerek, optimumun belirli bir katı içinde kanıtlanabilir bir çözüm garanti eder ve çözüm kalitesi ile işlenebilirlik arasında titiz ödünleşimler sunar.
Tanım
Bir optimizasyon problemi için yaklaşım algoritması, amaç değerinin, optimum değerin kanıtlanmış bir çarpımsal faktörü (yaklaşım oranı) içinde olduğu garanti edilen uygun bir çözüm döndüren polinom zamanlı bir algoritmadır.
Kapsam
Bu konu, zor optimizasyon problemlerine yakın-optimal çözümler döndüren polinom zamanlı algoritmaları, kalitelerini ölçen yaklaşım oranını ve başlıca tasarım tekniklerini (kanıtlanabilir sınırlara sahip açgözlü (greedy) ve yerel arama (local-search) sezgisel yöntemleri, doğrusal programlama gevşetmesi ve yuvarlama ile primal-dual yöntemi) kapsamaktadır. Ayrıca, yaklaşım şemalarını (PTAS ve FPTAS) ve bazı problemlerin ne kadar iyi yaklaşılabileceğini sınırlayan yaklaşılamazlık (inapproximability) sonuçlarının varlığını da ele almaktadır.
Temel sorular
- Yaklaşık bir çözümün kalitesi, yaklaşım oranı ile nasıl ölçülür?
- LP gevşetmesi ve yuvarlama, kesirli bir optimumu sınırlı bir tam sayı çözümüne nasıl dönüştürür?
- Açgözlü (greedy) ve yerel arama (local-search) yöntemleri kanıtlanabilir yaklaşım garantilerini nasıl sağlar?
- Polinom zamanlı yaklaşım şemaları nelerdir ve hangi problemler bunları kabul eder?
- Bazı problemler neden keyfi olarak iyi yaklaştırılabilirken, diğerleri hiç yaklaştırılamaz?
Anahtar kavramlar
- yaklaşım oranı
- NP-zor optimizasyon
- açgözlü (greedy) yaklaşım
- yerel arama
- LP gevşetmesi ve yuvarlama
- primal-dual yöntemi
- PTAS ve FPTAS
- yaklaşılamazlık
Temel kuramlar
- Yaklaşım oranı
- Yaklaşım oranı, bir algoritmanın çözümünün en kötü durumda optimumdan ne kadar uzakta olabileceğini sınırlar; bir c-yaklaşımı, optimumun c katı içinde bir çözüm garanti ederek, verimli bir algoritma için titiz bir kalite sertifikası sağlar.
- LP gevşetmesi ve yuvarlama
- Birçok yaklaşım algoritması, bir tam sayı programını doğrusal bir programa gevşetir, verimli bir şekilde çözer ve kesirli çözümü, kaybı sınırlayarak tam sayı bir çözüme yuvarlar; böylece primal-dual veya yuvarlama çerçeveleri aracılığıyla kanıtlanabilir oranlar elde edilir.
Klinik önem
Yaklaşım algoritmaları, çözülemeyen optimizasyonu pratikte kullanılabilir hale getirmektedir: küme örtüsü, tepe örtüsü, tesis yerleşimi, çizelgeleme ve gezgin satıcı problemi için sınırlı oranlı yöntemler, lojistik, ağ tasarımı ve yöneylem araştırmasındaki gerçek sistemlere rehberlik ederek, doğrulanmamış sezgisel yöntemler yerine kalite garantili çözümler sunmaktadır.
Tarihçe
Bu alan 1970'lerde, Johnson'ın küme örtüsü ve kutu paketleme gibi problemler için yaklaşım oranları analizleri ve Christofides'in metrik gezgin satıcı problemi için 1976 algoritması ile başlamıştır. Doğrusal programlama ve primal-dual teknikleri 1980'ler ve 1990'larda olgunlaşmış, olasılıksal olarak doğrulanabilir kanıtlar ise daha sonra güçlü yaklaşılamazlık sonuçları ortaya koymuştur; tüm bu gelişmeler Vazirani ile Williamson ve Shmoys'un ders kitaplarında pekiştirilmiştir.
Öne çıkan isimler
- Vijay Vazirani
- David Williamson
- David Shmoys
- David Johnson
- László Lovász
İlgili konular
Temel eserler
- vazirani2001
- williamson2011
- cormen2009
Sıkça sorulan sorular
- 2-yaklaşım algoritması neyi garanti eder?
- Bir minimizasyon problemi için, 2-yaklaşımı her zaman maliyeti optimum maliyetin en fazla iki katı olan bir çözüm döndürür (ve bir maksimizasyon problemi için, optimumun en az yarısı kadar bir faktör içinde). Bu garanti, ne kadar düşmanca olursa olsun her girdi için geçerlidir.
- Her NP-zor problem iyi yaklaştırılabilir mi?
- Hayır. Bazı problemler, optimuma keyfi olarak yaklaşan yaklaşım şemalarını kabul ederken, diğerleri mümkün olan en iyi sabit orana sahiptir ve bazıları, P'nin NP'ye eşit olmadığı sürece makul herhangi bir faktör içinde yaklaştırılamaz. Yaklaşılamazlık sonuçları bu sınırları resmi olarak belirler.