Yaklaşım algoritması - Approximation algorithm

Gelen bilgisayar bilimi ve operasyonlar araştırma , yaklaşım algoritmaları olan verimli algoritmalar bulmak yaklaşık çözüm optimizasyon problemlerinin (özellikle NP-zor olan problemler) kanıtlanabilir garantiler optimum birine döndü çözümün mesafeye. Yaklaşım algoritmaları , yaygın olarak inanılan P ≠ NP varsayımının bir sonucu olarak teorik bilgisayar bilimi alanında doğal olarak ortaya çıkar . Bu varsayım altında, geniş bir optimizasyon problemi sınıfı, polinom zamanında tam olarak çözülemez . Yaklaşım algoritmaları alanı, bu nedenle, polinom zamanında bu tür problemlere optimal çözümlere yaklaşmanın ne kadar yakından mümkün olduğunu anlamaya çalışır. Vakaların ezici bir çoğunluğunda, bu tür algoritmaların garantisi, bir yaklaşım oranı veya yaklaşıklık faktörü olarak ifade edilen bir çarpımsal çözümdür, yani, optimal çözümün her zaman döndürülen çözümün (önceden belirlenmiş) bir çarpım faktörü içinde olması garanti edilir. Bununla birlikte, döndürülen çözümün kalitesi üzerinde ek bir garanti sağlayan birçok yaklaşım algoritması da vardır. Sağlayan bir yaklaşım algoritması dikkate değer bir örnek, hem klasik yaklaşım algoritmasıdır Lenstra , Shmoys ve Tardos için ilgisiz paralel makinelerde zamanlama .

Yaklaşım algoritmalarının tasarımı ve analizi, kritik bir şekilde, en kötü durumda döndürülen çözümlerin kalitesini onaylayan matematiksel bir kanıtı içerir. Bu, onları , bazı girdilerde makul derecede iyi çözümler bulan, ancak başlangıçta ne zaman başarılı veya başarısız olabilecekleri konusunda net bir gösterge sağlamayan tavlama veya genetik algoritmalar gibi buluşsal yöntemlerden ayırır .

Bazı ünlü optimizasyon problemlerine yaklaşabileceğimiz sınırları daha iyi anlamak için teorik bilgisayar bilimine yaygın bir ilgi vardır . Örneğin, bilgisayar biliminde uzun süredir devam eden açık sorulardan biri , Christofides'in 1.5 yaklaşım algoritmasını metrik gezgin satıcı problemine göre daha iyi performans gösteren bir algoritma olup olmadığını belirlemektir . Zor optimizasyon problemlerini yaklaşıklık perspektifinden anlama arzusu, şaşırtıcı matematiksel bağlantıların ve zor optimizasyon problemleri için algoritmalar tasarlamak için geniş çapta uygulanabilir tekniklerin keşfi ile motive edilir. İlkinin iyi bilinen bir örneği, yüksek boyutlu geometri kullanarak bir grafik teorik problemini çözen maksimum kesim için Goemans-Williamson algoritmasıdır .

Tanıtım

Yaklaşım algoritmasının basit bir örneği , giriş grafiğindeki her kenar en az bir seçilmiş tepe noktası içerecek şekilde hedefin en küçük köşe kümesini seçmek olduğu minimum tepe örtüsü problemi için bir örnektir . Bir tepe örtüsü bulmanın bir yolu, aşağıdaki işlemi tekrarlamaktır: kaplanmamış bir kenar bulun, her iki uç noktasını da kapağa ekleyin ve grafikten herhangi bir tepe noktasına gelen tüm kenarları kaldırın. Giriş grafiğinin herhangi bir köşe kaplaması, işlemde dikkate alınan her bir kenarı kaplamak için ayrı bir köşe kullanması gerektiğinden (bir eşleşme oluşturduğundan ), üretilen köşe kaplaması, bu nedenle, optimal olanın en fazla iki katı büyüklüğündedir. Başka bir deyişle, bu, yaklaşık faktörü 2 olan bir sabit faktör yaklaşımı algoritmasıdır . Son zamanlardaki benzersiz oyunlar varsayımına göre , bu faktör mümkün olan en iyi faktördür.

NP-zor problemler, yakınlıklarına göre büyük farklılıklar gösterir; sırt çantası problemi gibi bazıları, herhangi bir sabit için bir çarpımsal faktör içinde yaklaşıklanabilir ve bu nedenle optimuma keyfi olarak yakın çözümler üretebilir (böyle bir yaklaşım algoritmaları ailesine polinom zaman yaklaşım şeması veya PTAS denir). Diğerlerini , maksimum klik probleminde olduğu gibi, P = NP olmadıkça herhangi bir sabit, hatta polinom faktörü içinde tahmin etmek imkansızdır . Bu nedenle, yaklaşım algoritmalarını çalışmanın önemli bir faydası, çeşitli NP-zor problemlerin zorluğunun NP-tamlık teorisinin sağladığının ötesinde ince taneli bir sınıflandırmasıdır . Başka bir deyişle, NP-tam problemler, kesin çözümler açısından birbirine (polinom zaman azalmaları altında) eşdeğer olabilse de, karşılık gelen optimizasyon problemleri yaklaşık çözümler açısından çok farklı davranır. ${\displaystyle 1+\epsilon }$${\displaystyle \epsilon >0}$

Algoritma tasarım teknikleri

Şimdiye kadar, yaklaşım algoritmaları tasarlamak için birkaç yerleşik teknik vardır. Bunlar aşağıdakileri içerir.

1. Açgözlü algoritma
2. Bölgesel arama
3. Numaralandırma ve dinamik programlama
4. Kesirli bir çözüm elde etmek için dışbükey programlama gevşemesini çözme . Daha sonra bu kesirli çözümü uygun bir yuvarlama ile uygun bir çözüme dönüştürün. Popüler rahatlamalar aşağıdakileri içerir.
   • Doğrusal programlama gevşemeleri
   • Yarı kesin programlama gevşemeleri
5. İlkel-ikili yöntemler
6. Çift uydurma
7. Problemi bir metrik içine gömmek ve sonra problemi metrik üzerinde çözmek. Bu aynı zamanda metrik gömme olarak da bilinir.
8. Rastgele örnekleme ve yukarıdaki yöntemlerle bağlantılı olarak genel olarak rastgelelik kullanımı.

A posteriori garantiler

Yaklaşım algoritmaları her zaman a priori en kötü durum garantisi sağlarken (toplamsal veya çarpımsal olabilir), bazı durumlarda genellikle çok daha iyi olan a posteriori bir garanti de sağlarlar. Bu genellikle , verilen girdideki optimizasyon probleminin dışbükey gevşemesini çözerek çalışan algoritmalar için geçerlidir . Örneğin, gevşeme değerinin en fazla iki katı olan bir köşe örtüsü bulmak için doğrusal bir programlama gevşemesini çözen minimum tepe örtüsü için farklı bir yaklaşım algoritması vardır . Gevşemenin değeri hiçbir zaman optimal tepe örtüsünün boyutundan daha büyük olmadığı için, bu başka bir 2-yaklaşım algoritması verir. Bu, önceki yaklaşım algoritmasının a priori garantisine benzer olsa da, ikincisinin garantisi çok daha iyi olabilir (aslında LP gevşemesinin değeri optimal tepe örtüsünün boyutundan uzak olduğunda).

Yaklaşımın sertliği

Bir araştırma alanı olarak yaklaşıklık algoritmaları, belirli yaklaşım oranlarına sahip verimli algoritmaların bulunmadığının (P ≠ NP varsayımı gibi yaygın olarak inanılan hipotezlere bağlı olarak) indirgemeler yoluyla kanıtlandığı yaklaşıklıksızlık teorisi ile yakından ilişkilidir ve bu teori tarafından bilgilendirilir . Metrik gezgin satıcı problemi durumunda, en iyi bilinen yaklaşıklıksızlık sonucu, P = NP, Karpinski, Lampis, Schmied olmadıkça, yaklaşıklık oranı 123/122 ≈ 1.008196'dan küçük olan algoritmaları dışlar. Christofides'in 1.5 yaklaşım algoritmasının varlığı bilgisi ile birleştiğinde, bu bize metrik gezgin satıcı için (varsa) yaklaşıklık eşiğinin 123/122 ile 1.5 arasında bir yerde olduğunu söyler.

Yaklaşımsızlık sonuçları 1970'lerden beri kanıtlanırken, bu tür sonuçlar ad hoc yollarla elde edildi ve o sırada sistematik bir anlayış mevcut değildi. Feige, Goldwasser, Lovász, Safra ve Szegedy'nin Bağımsız Küme ve ünlü PCP teoreminin yaklaşık olmamasına ilişkin 1990 sonuçlarından bu yana, yaklaşıklıksızlık sonuçlarını kanıtlamak için modern araçlar ortaya çıkarılmıştır. Örneğin PCP teoremi, Johnson'ın Maks SAT , küme örtüsü , bağımsız küme ve renklendirme için 1974 yaklaşım algoritmalarının tümünün, P ≠ NP varsayarak en uygun yaklaşım oranını elde ettiğini gösterir.

pratiklik

Tüm yaklaşım algoritmaları doğrudan pratik uygulamalar için uygun değildir. Bazıları, yalnızca pratik olarak büyük girdilerde zor uygulama sorunlarına veya iyileştirilmiş çalışma süresi performansına (tam algoritmalar üzerinden) yol açan önemsiz olmayan doğrusal programlama / yarı kesin gevşemeler (kendileri elipsoid algoritmayı çağırabilir ), karmaşık veri yapıları veya karmaşık algoritmik teknikleri çözmeyi içerir. . Uygulama ve çalışma süresi sorunları bir yana, yaklaşım algoritmaları tarafından sağlanan garantiler, pratikte dikkate alınmalarını haklı kılacak kadar güçlü olmayabilir. Pratik uygulamalarda "kutunun dışında" kullanılamamalarına rağmen, bu tür algoritmaların tasarımının arkasındaki fikirler ve içgörüler genellikle pratik algoritmalarda başka yollarla birleştirilebilir. Bu şekilde, çok pahalı algoritmaların incelenmesi bile tamamen teorik bir arayış değildir, çünkü değerli bilgiler sağlayabilirler.

Diğer durumlarda, ilk sonuçlar tamamen teorik ilgi olsa bile, zamanla, gelişmiş bir anlayışla, algoritmalar daha pratik hale gelecek şekilde geliştirilebilir. Bu tür bir örnek için ilk PTAS olan Öklid TSP tarafından Sanjeev Arora (göre, bağımsız bir şekilde ve Joseph Mitchell bir engelleyici çalışma süresi vardı) for a yaklaşım. Yine de, bir yıl içinde bu fikirler herhangi bir sabit için doğrusala yakın bir zaman algoritmasına dahil edildi . ${\ Displaystyle n^{O(1/\epsilon )}}$${\displaystyle 1+\epsilon }$${\ Displaystyle O(n\log n)}$${\displaystyle \epsilon >0}$

Performans garantileri

Bazı yaklaşım algoritmaları için, optimum sonucun yaklaşıklığı hakkında belirli özellikleri kanıtlamak mümkündür. Örneğin, bir ρ -approximation algoritma bir o değeri / maliyet kanıtlanmıştır olan bir algoritma olarak tanımlanır f ( x yaklaşık çözelti), A ( x bir örneğine) x daha olmayacak (ya da duruma bağlı olarak) bir optimum çözümün ρ faktörü çarpı OPT değerinden daha azdır .

${\displaystyle {\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{durumlar}}}$

ρ faktörüne göreli performans garantisi denir . Her x örneği için kanıtlanmışsa, bir yaklaşım algoritmasının mutlak bir performans garantisi veya sınırlı hatası c vardır .

${\displaystyle (\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c).}$

Benzer şekilde, bir x örneğine y çözümünün performans garantisi , R ( x,y ), şu şekilde tanımlanır:

${\displaystyle R(x,y)=\max \sol({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\sağ),}$

burada f ( y ), x örneği için y çözümünün değeri/maliyetidir . Açıkça, performans garantisi 1'den büyük veya 1'e eşit ve ancak ve ancak y optimal bir çözümse 1'e eşittir . Bir algoritma halinde bir garanti en bir performans garantisi ile çözüm dönmek için r ( n ), daha sonra bir bir olduğu söylenir r ( n -approximation algoritması) ve bir yer alır yaklaşım oranı bir R ( n ). Benzer şekilde, bir r ( n )-yaklaşım algoritmasıyla ilgili bir problemin r ( n ) - yaklaşık olduğu veya yaklaşıklık oranının r ( n ) olduğu söylenir .

Minimizasyon problemleri için, iki farklı garanti aynı sonucu verir ve maksimizasyon problemleri için ρ göreli performans garantisinin performans garantisine eşdeğerdir . Literatürde her iki tanım da ortaktır ancak maksimizasyon problemlerinde ρ ≤ 1 iken r ≥ 1 olduğundan hangi tanımın kullanıldığı açıktır. ${\görüntüleme stili r=\rho ^{-1}}$

Mutlak kesin teminat bir yaklaşım algoritması A , X , bir sorun örneğine karşılık gelir ve burada performansı garanti A ile x (sorun örneği için, yani ρ x ) aşağıdaki gibidir: ${\görüntüleme stili \mathrm {P} _{A}}$${\görüntüleme stili R_{A}(x)}$

${\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}$

Diğer bir deyişle , bu, problemin tüm olası örneklerinde görülen, yaklaşım oranı ( r) üzerindeki en büyük sınırdır . Benzer şekilde, asimptotik performans oranı : ${\görüntüleme stili \mathrm {P} _{A}}$ ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }=\inf\{r\geq 1\mid \vardır n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\ için x,|x|\geq n\}.}$

Başka bir deyişle , problem örneklerinin boyutunda bir alt sınır n ile mutlak performans oranı ile aynıdır . Bu iki oran türü, bu ikisi arasındaki farkın önemli olduğu algoritmalar olduğu için kullanılır.

Performans garantileri

	r -yaklaşık	ρ -yaklaşık	rel. hata	rel. hata	norm. rel. hata	karın kasları hata
maksimum: ${\görüntüleme stili f(x)\geq }$	${\displaystyle r^{-1}\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\görüntüleme stili (1-c)\mathrm {OPT} }$	${\görüntüleme stili (1-c)\mathrm {OPT} }$	${\displaystyle (1-c)\mathrm {OPT} +c\mathrm {KÖTÜ} }$	${\displaystyle \mathrm {OPT} -c}$
dk: ${\displaystyle f(x)\leq }$	${\displaystyle r\mathrm {OPT} }$	${\displaystyle \rho \mathrm {OPT} }$	${\displaystyle (1+c)\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} }$	${\displaystyle (1-c)^{-1}\mathrm {OPT} +c\mathrm {EN KÖTÜ} }$	${\displaystyle \mathrm {OPT} +c}$

epsilon terimleri

Literatürde, c - ϵ (min: c + ϵ) olan bir maksimizasyon (minimizasyon) problemi için bir yaklaşım oranı , algoritmanın rastgele ϵ > 0 için bir c ∓ ϵ yaklaşım oranına sahip olduğu, ancak oranın (veya olamaz) ϵ = 0 için gösterilemez. Buna bir örnek, Johan Håstad'a bağlı olarak tatmin edici MAX-3SAT örnekleri için 7/8 + ϵ'lik optimal yakınlıksızlık — yaklaşıklığın yokluğu — oranıdır . Daha önce bahsedildiği gibi, c = 1 olduğunda, problemin bir polinom-zaman yaklaşım şemasına sahip olduğu söylenir .

Bir yaklaşım algoritması, n boyutundaki örneklerin minimum optimumu n'nin yaptığı gibi sonsuza giderken bir çarpımsal hata ve sabit bir hata getirdiğinde bir ϵ terimi görünebilir . Bu durumda, bazı sabitler c ve k için yaklaşıklık oranı c ∓ k / OPT = c ∓ o(1) 'dir . Rastgele ϵ > 0 verildiğinde, her n ≥ N için k / OPT < ϵ terimi olacak şekilde yeterince büyük bir N seçilebilir . Her sabit ϵ için, n < N boyutundaki örnekler kaba kuvvetle çözülebilir, böylece her ϵ > 0 için c ∓ ϵ'lik bir yaklaşıklık oranı (garantili yaklaşım algoritmalarının varlığı) gösterilir .

Ayrıca bakınız

• Hakimiyet analizi , garantileri hesaplanan çözümün sıralaması açısından değerlendirir.
• PTAS - yaklaşım oranını parametre olarak alan bir tür yaklaşım algoritması
• APX , bazı sabit faktörlü yaklaşım algoritmalarına sahip problemler sınıfıdır.
• Yaklaşımı koruyan azalma
• Kesin algoritma

alıntılar

Referanslar

• Vazirani, Vijay V. (2003). Yaklaşım Algoritmaları . Berlin: Springer. ISBN'si 978-3-540-65367-7.
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest ve Clifford Stein . Algoritmalara Giriş , İkinci Baskı. MIT Press ve McGraw-Hill, 2001. ISBN  0-262-03293-7 . Bölüm 35: Yaklaşım Algoritmaları, s. 1022–1056.
• Dorit S. Hochbaum , ed. NP-Zor problemler için Yaklaşım Algoritmaları , PWS Publishing Company, 1997. ISBN  0-534-94968-1 . Bölüm 9: Çeşitli Yaklaşım Kavramları: İyi, Daha İyi, En İyi ve Daha Fazlası
• Williamson, David P .; Shmoys, David B. (26 Nisan 2011), Yaklaşım Algoritmalarının Tasarımı , Cambridge University Press , ISBN 978-052195270

Dış bağlantılar

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ve Gerhard Woeginger , NP optimizasyon problemlerinin bir özeti .