Modern uygulamalı araştırma, gradyan inişi adı verilen çok önemli bir algoritmaya dayanır. Bu, genellikle belirli bir matematiksel işlevin en büyük veya en küçük değerlerini bulmak için kullanılan bir prosedürdür – işlevi optimize etme olarak bilinen bir işlem. Bir ürünü üretmenin en karlı yolundan işçilere vardiya atamanın en iyi yoluna kadar her şeyi hesaplamak için kullanılabilir.
Ancak bu yaygın kullanışlılığa rağmen, araştırmacılar algoritmanın en çok hangi durumlarla mücadele ettiğini hiçbir zaman tam olarak anlayamadılar. Şimdi, yeni çalışma bunu açıklıyor, gradyan inişini özünde, temelde zor bir hesaplama problemini ele alıyor. Yeni sonuç, araştırmacıların belirli uygulamalarda teknikten bekleyebilecekleri performans türüne sınırlamalar getiriyor.
Liverpool Üniversitesi’nden John Fearnley ve Rahul Savani ve Oxford’dan Alexandros Hollender ile birlikte çalışmanın ortak yazarı Oxford Üniversitesi’nden Paul Goldberg, “Bilinmeye değer bir tür en kötü durum sertliği var” dedi. Sonuç, Haziran ayında yıllık Bilgisayar Teorisi Sempozyumu’nda En İyi Makale Ödülü’nü aldı.
Gradyan İnişi Nedir?
Bir işlevi, arazinin yüksekliğinin, o noktadaki işlevin değerine (“kâr”) eşit olduğu bir manzara olarak hayal edebilirsiniz. Gradyan iniş, belirli bir konumdaki en dik çıkışın yönünü arayarak ve bu konumdan yokuş aşağı iniş yaparak fonksiyonun yerel minimumunu arar. Peyzajın eğimine gradyan, dolayısıyla gradyan inişi denir.
Gradyan inişi, modern uygulamalı araştırmanın temel bir aracıdır, ancak iyi çalışmadığı birçok yaygın sorun vardır. Ancak bu araştırmadan önce, gradyan iniş mücadelesini tam olarak neyin ve ne zaman yaptığına dair kapsamlı bir anlayış yoktu – bilgisayar biliminin hesaplama karmaşıklığı teorisi olarak bilinen başka bir alanı yanıtlamaya yardımcı oldu.
Massachusetts Teknoloji Enstitüsü’nden Costis Daskalakis, “Degrade inişle ilgili çalışmaların çoğu karmaşıklık teorisinden bahsetmiyordu” dedi.
Hesaplama karmaşıklığı, farklı hesaplama sorunlarının çözümlerini çözmek veya doğrulamak için gereken kaynakların, genellikle hesaplama süresinin incelenmesidir. Araştırmacılar, aynı sınıftaki tüm problemler bazı temel hesaplama özelliklerini paylaşarak, problemleri farklı sınıflara ayırırlar.
Yeni makaleyle ilgili bir örnek vermek gerekirse, evlerden daha fazla insanın olduğu ve herkesin bir evde yaşadığı bir kasaba hayal edin. Size şehirdeki herkesin isim ve adreslerini içeren bir telefon rehberi veriliyor ve aynı evde yaşayan iki kişiyi bulmanız isteniyor. Bir cevap bulabileceğinizi biliyorsunuz, çünkü evlerden daha fazla insan var, ancak biraz aramanız gerekebilir (özellikle bir soyadı paylaşmıyorlarsa).
Bu soru, “total function nondeterministic polinom”un kısaltması olan TFNP adlı bir karmaşıklık sınıfına aittir. Çözümü garanti edilen ve çözümlerinin doğruluğu hızlı bir şekilde kontrol edilebilen tüm hesaplama problemlerinin toplamıdır. Araştırmacılar, TFNP içindeki iki problem alt kümesinin kesişimine odaklandı. 
İlk alt kümeye PLS (polinom yerel arama) adı verilir. Bu, belirli bir bölgedeki bir fonksiyonun minimum veya maksimum değerini bulmayı içeren bir problemler topluluğudur. Bu problemlerin nispeten basit akıl yürütme yoluyla bulunabilecek cevapları olması garanti edilir.
PLS kategorisine giren bir problem, seyahati yalnızca herhangi bir ardışık şehir çiftinin sırasını değiştirerek değiştirebileceğiniz göz önüne alındığında, mümkün olan en kısa seyahat mesafesine sahip sabit sayıda şehri ziyaret etmenize izin veren bir rota planlama görevidir. turda. Önerilen herhangi bir rotanın uzunluğunu hesaplamak kolaydır ve güzergah üzerinde değişiklik yapabileceğiniz yollara ilişkin bir sınırlama ile, hangi değişikliklerin yolculuğu kısalttığını görmek kolaydır. Sonunda kabul edilebilir bir hareketle iyileştiremeyeceğiniz bir rota bulmanız garantidir – yerel bir minimum.
Gradyan İnişi hakkında merak ettikleriniz varsa yorumlarda bizimle paylaşabilirsiniz! 🙂
