Araştırma çalışması belki de eğitimimizin en ilginç kısmıdır. Buradaki fikir, henüz üniversitedeyken kendinizi seçtiğiniz yönde denemektir. Örneğin, Yazılım Mühendisliği ve Makine Öğrenimi alanlarındaki öğrenciler sıklıkla şirketlerde (özellikle JetBrains veya Yandex'de) araştırma yapmaya giderler.
Bu yazımda Bilgisayar Bilimleri alanındaki projemden bahsedeceğim. Çalışmamın bir parçası olarak, en ünlü NP-zor problemlerden birinin çözümüne yönelik yaklaşımları inceledim ve uygulamaya koydum: köşe kaplama sorunu.
Günümüzde NP-zor problemlere ilginç bir yaklaşım, çok hızlı bir şekilde parametrelendirilmiş algoritmalar geliştirilmektedir. Sizi bilgilendirmeye çalışacağım, size bazı basit parametreli algoritmalar anlatacağım ve bana çok yardımcı olan güçlü bir yöntemi anlatacağım. Sonuçlarımı PACE Challenge yarışmasında sundum: Açık testlerin sonuçlarına göre çözümüm üçüncü sırada yer alıyor ve nihai sonuçlar 1 Temmuz'da belli olacak.
Hakkımda
Adım Vasily Alferov, şu anda St. Petersburg Ulusal Araştırma Üniversitesi İktisat Yüksek Okulu'nda üçüncü yılımı bitiriyorum. Moskova'nın 179 numaralı okulunda okuduğum ve bilgisayar bilimleri olimpiyatlarına başarıyla katıldığım okul günlerimden beri algoritmalara ilgi duyuyorum.
Parametreli algoritmalarda sınırlı sayıda uzman çıtaya giriyor...
Kitaptan alınan örnek
Küçük bir kasabada bar güvenlik görevlisi olduğunuzu hayal edin. Her Cuma, şehrin yarısı rahatlamak için barınıza geliyor, bu da size çok fazla sorun çıkarıyor: Kavgaları önlemek için kabadayı müşterileri bardan atmanız gerekiyor. Sonunda bıkarsınız ve önleyici tedbirler almaya karar verirsiniz.
Şehriniz küçük olduğundan, birlikte bir bara giderlerse hangi müşteri çiftlerinin kavga etme ihtimalinin yüksek olduğunu tam olarak bilirsiniz. bir listeniz var mı n bu gece bara gelecek insanlar. Kimse kavga etmeden bazı kasaba halkını barın dışında tutmaya karar veriyorsunuz. Aynı zamanda patronlarınız da karlarını kaybetmek istemezler ve eğer daha fazlasına izin vermezseniz mutsuz olacaklardır. k insanlar.
Ne yazık ki karşınızdaki problem klasik bir NP-zor problemdir. Onu şu şekilde tanıyor olabilirsin: veya köşe kaplama problemi olarak. Bu tür problemler için genel olarak kabul edilebilir bir sürede çalışan bir algoritma yoktur. Daha kesin olmak gerekirse, kanıtlanmamış ve oldukça güçlü hipotez ETH (Üstel Zaman Hipotezi), bu sorunun zamanla çözülemeyeceğini söylüyor. yani, tam bir aramadan gözle görülür derecede daha iyi bir şey düşünemezsiniz. Örneğin birisinin barınıza geleceğini varsayalım. n = 1000 İnsan. Daha sonra tam arama şu şekilde olacaktır: yaklaşık olarak mevcut olan seçenekler - çılgın miktar. Neyse ki yönetiminiz size bir limit vermiş k = 10yani yinelemeniz gereken kombinasyonların sayısı çok daha azdır: on öğenin alt kümelerinin sayısı . Bu daha iyi ama yine de güçlü bir kümede bile bir günde sayılmayacak.
Barın ziyaretçileri arasındaki gergin ilişkilerin bu konfigürasyonunda kavga olasılığını ortadan kaldırmak için Bob, Daniel ve Fedor'u dışarıda tutmanız gerekiyor. Geride sadece iki kişinin kalacağı bir çözüm yok.
Bu pes edip herkesin içeri girmesine izin vermenin zamanı geldiği anlamına mı geliyor? Diğer seçenekleri düşünelim. Mesela sadece çok sayıda insanla kavga etmesi muhtemel olanları içeri alamazsınız. Birisi en azından savaşabilirse k+1 başka biri varsa kesinlikle onu içeri alamazsınız - aksi takdirde herkesi dışarıda tutmak zorunda kalırsınız k+1 Kavga edebileceği kasaba halkı, bu kesinlikle liderliği üzecek.
Bu prensibe göre atabildiğiniz herkesi dışarı atmanıza izin verin. O zaman herkes en fazla savaşabilir k insanlar. Onları dışarı atmak k dostum, bundan başka hiçbir şeyi engelleyemezsin çatışmalar. Bu şu anlama gelir; eğer birden fazla varsa Bir kişi en az bir çatışmaya karışmışsa hepsini kesinlikle önleyemezsiniz. Tabii ki, tamamen çatışmasız insanları kesinlikle kabul edeceğiniz için, iki yüz kişiden on tanesinin tüm alt kümelerinden geçmeniz gerekiyor. Yaklaşık olarak var ve bu sayıdaki işlemler zaten kümede sıralanabilir.
Hiçbir çatışması olmayan bireyleri güvenli bir şekilde alabiliyorsanız, o zaman yalnızca bir çatışmaya katılanlar ne olacak? Aslında kapıyı rakiplerine kapatarak da içeri alınabiliyorlar. Gerçekten de, eğer Alice yalnızca Bob'la çatışıyorsa, o zaman Alice'i ikisinin dışında bırakırsak, kaybetmeyeceğiz: Bob'un başka çatışmaları da olabilir ama Alice'in kesinlikle böyle çatışmaları yoktur. Üstelik ikimizi de içeri almamanın hiçbir anlamı yok. Bu tür işlemlerden sonra artık kalmaz kaderi çözülmemiş misafirler: elimizde sadece her biri iki katılımcılı ve her biri en az iki katılımcıya dahil olan çatışmalar. Yani geriye kalan tek şey sıralamak Bir dizüstü bilgisayarda yarım gün rahatlıkla sayılabilecek seçenekler.
Aslında basit bir akıl yürütmeyle çok daha cazip koşullara ulaşabilirsiniz. Kesinlikle tüm anlaşmazlıkları çözmemiz gerektiğini, yani çatışan her çiftten içeri almayacağımız en az bir kişiyi seçmemiz gerektiğini unutmayın. Aşağıdaki algoritmayı ele alalım: Bir katılımcıyı çıkardığımız ve geri kalanından özyinelemeli olarak başladığımız, ardından diğerini kaldırdığımız ve yinelemeli olarak başladığımız herhangi bir çatışmayı ele alalım. Her adımda birisini dışarı attığımız için böyle bir algoritmanın özyineleme ağacı ikili bir derinlik ağacıdır. k, yani toplamda algoritma şu şekilde çalışır: Nerede n köşe sayısıdır ve m - kaburga sayısı. Örneğimizde bu yaklaşık on milyondur ve bu sadece bir dizüstü bilgisayarda değil, bir cep telefonunda bile bir salisede hesaplanabilir.
Yukarıdaki örnek bir örnektir parametreli algoritma. Parametreli algoritmalar, zaman içinde çalışan algoritmalardır f(k) poli(n)Nerede p - polinom, f keyfi hesaplanabilir bir fonksiyondur ve k - Büyük olasılıkla problemin boyutundan çok daha küçük olacak bazı parametreler.
Bu algoritmadan önceki tüm akıl yürütmeler bir örnek veriyor çekirdekleştirme parametreli algoritmalar oluşturmaya yönelik genel tekniklerden biridir. Çekirdekleştirme, problem boyutunun bir parametrenin fonksiyonu ile sınırlanan bir değere indirgenmesidir. Ortaya çıkan soruna genellikle çekirdek adı verilir. Böylece, köşelerin dereceleri hakkında basit bir mantık yürüterek, Köşe Örtüsü problemi için cevabın boyutuna göre parametrelendirilmiş ikinci dereceden bir çekirdek elde ettik. Bu görev için seçebileceğiniz başka ayarlar da vardır (LP'nin Üstündeki Vertex Cover gibi), ancak bu, tartışacağımız ayardır.
Hız Mücadelesi
Rekabet (Parameterized Algorithms and Computational Experiments Challenge), parametreli algoritmalar ile hesaplama problemlerini çözmek için pratikte kullanılan yaklaşımlar arasında bağlantı kurmak amacıyla 2015 yılında doğdu. İlk üç yarışma bir grafiğin ağaç genişliğini bulmaya ayrılmıştı (), bir Steiner ağacını arıyor () ve döngüleri kesen bir dizi köşe arama (). Bu yıl, şansınızı deneyebileceğiniz sorunlardan biri yukarıda açıklanan köşe kaplama sorunuydu.
Yarışma her yıl popülerlik kazanıyor. Ön verilere inanırsanız bu yıl 24 takım köşe kaplama problemini tek başına çözmek için yarışmaya katıldı. Yarışmanın birkaç saat, hatta bir hafta değil, birkaç ay sürdüğünü belirtmekte fayda var. Takımlar literatürü inceleme, kendi orijinal fikirlerini bulma ve bunu uygulamaya çalışma fırsatına sahiptir. Bu yarışma özünde bir araştırma projesidir. En etkili çözümlere yönelik fikirler ve kazananların ödüllendirilmesi konferansla birlikte gerçekleştirilecek (Uluslararası Parametreli ve Kesin Hesaplama Sempozyumu) Avrupa'nın en büyük yıllık algoritmik toplantısının bir parçası olarak . Yarışmayla ilgili daha detaylı bilgiye şu adresten ulaşabilirsiniz: ve önceki yılların sonuçları yalan söylüyor .
Çözüm diyagramı
Köşe kaplama problemini çözmek için parametreli algoritmalar kullanmayı denedim. Genellikle iki bölümden oluşurlar: basitleştirme kuralları (ideal olarak çekirdekleştirmeye yol açan) ve bölme kuralları. Basitleştirme kuralları, girdinin polinom zamanında ön işlenmesidir. Bu tür kuralların uygulanmasının amacı, sorunu eşdeğer daha küçük bir soruna indirgemektir. Basitleştirme kuralları algoritmanın en pahalı kısmıdır ve bu kısmın uygulanması toplam çalışma süresine yol açar basit polinom zamanı yerine. Bizim durumumuzda bölme kuralları, her köşe için onu veya komşusunu cevap olarak almanız gerektiği gerçeğine dayanmaktadır.
Genel şema şudur: Basitleştirme kurallarını uygularız, sonra bir köşe seçeriz ve iki özyinelemeli çağrı yaparız: ilkinde onu yanıt olarak alırız, diğerinde ise tüm komşularını alırız. Bu tepe noktası boyunca bölünme (dallanma) dediğimiz şey budur.
Bir sonraki paragrafta bu şemaya tam olarak bir ekleme yapılacaktır.
Kuralları bölmek (brunch) için fikirler
Bölmenin gerçekleşeceği tepe noktasının nasıl seçileceğini tartışalım.
Ana fikir algoritmik anlamda çok açgözlü: hadi maksimum derecedeki bir köşeyi alalım ve ona göre bölelim. Neden daha iyi görünüyor? Çünkü özyinelemeli çağrının ikinci dalında bu şekilde birçok köşeyi kaldıracağız. Kalan küçük bir grafiğe güvenebilirsiniz ve üzerinde hızla çalışabiliriz.
Bu yaklaşım, daha önce tartışılan basit çekirdekleştirme teknikleriyle birlikte kendini iyi bir şekilde gösterir ve birkaç bin köşe boyutunda bazı testleri çözer. Ancak örneğin kübik grafiklerde (yani her köşesinin derecesi üç olan grafiklerde) pek işe yaramaz.
Oldukça basit bir fikre dayanan başka bir fikir daha var: Grafiğin bağlantısı kesilirse, bağlı bileşenlerindeki sorun, yanıtların sonunda birleştirilmesiyle bağımsız olarak çözülebilir. Bu arada, bu, şemada çözümü önemli ölçüde hızlandıracak vaat edilen küçük bir değişikliktir: daha önce, bu durumda, bileşenlerin tepkilerini hesaplamak için zamanların çarpımı üzerinde çalışıyorduk, ancak şimdi bunun için çalışıyoruz. toplam. Dallanmayı hızlandırmak için bağlı bir grafiği bağlantısız bir grafik haline getirmeniz gerekir.
Nasıl yapılır? Grafikte bir eklemlenme noktası varsa onunla mücadele etmeniz gerekir. Eklem noktası, kaldırıldığında grafiğin bağlantısını kaybedecek şekilde bir tepe noktasıdır. Bir grafikteki tüm bağlantı noktaları, doğrusal zamanda klasik bir algoritma kullanılarak bulunabilir. Bu yaklaşım dallanmayı önemli ölçüde hızlandırır.
Seçilen köşelerden herhangi biri kaldırıldığında grafik bağlı bileşenlere bölünür.
Bunu yapacağız ama daha fazlasını istiyoruz. Örneğin, grafikte küçük köşe kesimlerini arayın ve buradan köşe noktaları boyunca bölün. Minimum küresel köşe kesimini bulmanın bildiğim en etkili yolu, kübik zamanda inşa edilen Gomori-Hu ağacını kullanmaktır. PACE Challenge'da tipik grafik boyutu birkaç bin köşedir. Bu durumda özyineleme ağacının her köşesinde milyarlarca işlemin gerçekleştirilmesi gerekir. Sorunu ayrılan sürede çözmenin imkansız olduğu ortaya çıktı.
Çözümü optimize etmeye çalışalım. Bir çift köşe arasındaki minimum köşe kesimi, maksimum akışı oluşturan herhangi bir algoritma tarafından bulunabilir. Böyle bir ağa izin verebilirsiniz , pratikte çok hızlı çalışır. Çalışma süresine ilişkin bir tahminin teorik olarak kanıtlanmasının mümkün olduğuna dair şüphelerim var ki bu zaten oldukça kabul edilebilir.
Rastgele köşe çiftleri arasındaki kesimleri aramayı ve en dengeli olanı almayı birkaç kez denedim. Ne yazık ki bu, açık PACE Challenge testinde kötü sonuçlar verdi. Bunu, maksimum derecedeki köşeleri bölen ve bunları iniş derinliği sınırlamasıyla çalıştıran bir algoritmayla karşılaştırdım. Bu şekilde bir kesim bulmaya çalışan bir algoritma, geride daha büyük grafikler bıraktı. Bunun nedeni, kesimlerin çok dengesiz olduğu ortaya çıktı: 5-10 köşeyi çıkardıktan sonra yalnızca 15-20'yi bölmek mümkün oldu.
Teorik olarak en hızlı algoritmalarla ilgili makalelerin, bölme için köşelerin seçiminde çok daha gelişmiş teknikler kullandığını belirtmekte fayda var. Bu tür tekniklerin uygulanması çok karmaşıktır ve genellikle zaman ve bellek açısından zayıf performansa sahiptir. Uygulama için oldukça kabul edilebilir olanları tespit edemedim.
Basitleştirme Kuralları Nasıl Uygulanır?
Çekirdekleştirme için zaten fikirlerimiz var. Hatırlatmama izin ver:
- Yalıtılmış bir köşe varsa onu silin.
- Derece 1'in bir köşesi varsa, onu kaldırın ve yanıt olarak komşusunu alın.
- En azından derecenin bir tepe noktası varsa k+1, geri al.
İlk ikisinde her şey açık, üçüncüsünde ise bir hile var. Bir barla ilgili komik bir problemde bize bir üst sınır verilmiş olsaydı k, o zaman PACE Mücadelesinde minimum boyutta bir köşe kapağı bulmanız yeterlidir. Bu, Arama Sorunlarının Karar Sorunlarına tipik bir dönüşümüdür; genellikle iki tür sorun arasında hiçbir fark yoktur. Uygulamada köşe kaplama problemine çözüm yazıyorsak farklılık olabilir. Örneğin üçüncü maddede olduğu gibi.
Uygulama açısından bakıldığında ilerlemenin iki yolu vardır. İlk yaklaşıma İteratif Derinleştirme adı veriliyor. Şöyledir: Cevap üzerinde aşağıdan makul bir kısıtlama ile başlayabiliriz ve daha sonra özyinelemede bu kısıtlamadan daha aşağı inmeden, bu kısıtlamayı yukarıdan yanıt üzerinde bir kısıtlama olarak kullanarak algoritmamızı çalıştırabiliriz. Eğer bir cevap bulursak, optimal olacağı garantidir, aksi halde bu limiti bir arttırıp yeniden başlayabiliriz.
Diğer bir yaklaşım ise mevcut en uygun yanıtı depolamak ve daha küçük bir yanıt aramak, bulduğunda bu parametreyi değiştirmektir. k Arama sırasında gereksiz dalların daha fazla kesilmesi için.
Her gece birkaç deney yaptıktan sonra, bu iki yöntemin bir kombinasyonuna karar verdim: ilk olarak, algoritmamı arama derinliğinde bir tür sınırla çalıştırıyorum (bunu, ana çözüme kıyasla ihmal edilebilir bir zaman alacak şekilde seçiyorum) ve en iyisini kullanıyorum. Cevabın üst sınırı olarak bulunan çözüm - yani aynı şeye k.
2. derecenin köşeleri
0 ve 1 derece köşe noktalarını ele aldık. Bunun 2. derecedeki köşelerle yapılabileceği ortaya çıktı, ancak bu, grafikte daha karmaşık işlemler gerektirecektir.
Bunu açıklamak için köşe noktalarını bir şekilde belirlememiz gerekiyor. 2. derecedeki bir köşeye köşe diyelim vve komşuları - köşeler x и y. Daha sonra iki vakamız olacak.
- Ne zaman x и y - komşular. O zaman cevap verebilirsin x и yVe v silmek. Aslında bu üçgenden karşılığında en az iki köşe alınması gerekiyor, alırsak da kesinlikle kaybetmeyeceğiz. x и y: muhtemelen başka komşuları da vardır ve v değiller.
- Ne zaman x и y - komşular değil. Daha sonra üç köşenin de tek bir noktaya yapıştırılabileceği belirtiliyor. Buradaki fikir şu ki, bu durumda ikisinden birini aldığımız en uygun cevap vardır. vveya her iki köşe x и y. Üstelik ilk durumda tüm komşuları yanıt olarak almamız gerekecek x и y, ancak ikincisinde gerekli değildir. Bu, yapıştırılmış tepe noktasını yanıt olarak almadığımız ve aldığımız durumlara tam olarak karşılık gelir. Geriye sadece her iki durumda da böyle bir operasyondan gelen tepkinin bir oranında azaldığını belirtmek kalıyor.
Bu yaklaşımın adil doğrusal zamanda doğru bir şekilde uygulanmasının oldukça zor olduğunu belirtmekte fayda var. Köşeleri yapıştırmak karmaşık bir işlemdir; komşu listelerini kopyalamanız gerekir. Bu dikkatsizce yapılırsa, asimptotik olarak optimumun altındaki çalışma süresiyle karşılaşabilirsiniz (örneğin, her yapıştırmadan sonra çok sayıda kenar kopyalarsanız). 2. derece köşe noktalarından tüm yolları bulmaya ve bu köşe noktalarından veya biri hariç tüm bu köşe noktalarından gelen döngüler gibi bir dizi özel durumu analiz etmeye karar verdim.
Ek olarak, özyinelemeden döndüğümüzde grafiği orijinal biçimine döndürebilmemiz için bu işlemin tersinir olması gerekir. Bunu sağlamak için birleştirilmiş köşelerin kenar listelerini temizlemedim ve yalnızca hangi kenarların nereye gitmesi gerektiğini biliyordum. Grafiklerin bu uygulaması da doğruluk gerektirir, ancak adil doğrusal zaman sağlar. Ve onbinlerce kenardan oluşan grafikler için işlemci önbelleğine sığar ve bu da hızda büyük avantajlar sağlar.
Doğrusal çekirdek
Son olarak çekirdeğin en ilginç kısmı.
Başlangıç olarak, iki parçalı grafiklerde minimum tepe noktası kapsamının şu şekilde bulunabileceğini hatırlayın: . Bunu yapmak için algoritmayı kullanmanız gerekir. buradaki maksimum eşleşmeyi bulmak için ve sonra teoremi kullanın .
Doğrusal çekirdeğin fikri şudur: İlk önce grafiği ikiye ayırırız, yani her köşe yerine v iki tepe ekleyelim и ve her kenar yerine u - v iki kaburga ekleyelim и . Ortaya çıkan grafik iki parçalı olacaktır. Minimum köşe örtüsünü bulalım. Orijinal grafiğin bazı köşeleri oraya iki kez ulaşır, bazıları yalnızca bir kez, bazıları ise asla. Nemhauser-Trotter teoremi, bu durumda bir kez bile isabet etmeyen köşelerin kaldırılabileceğini ve iki kez isabet edenlerin geri alınabileceğini belirtir. Üstelik geri kalan köşelerin (bir kez çarpanların) en az yarısını cevap olarak almanız gerektiğini söylüyor.
Daha fazlasını bırakmamayı öğrendik 2k zirveler Aslında, eğer kalan cevap tüm köşelerin en az yarısı ise, o zaman toplamda şu sayıdan daha fazla köşe yoktur: 2k.
Burada ileriye doğru küçük bir adım atabildim. Bu şekilde oluşturulan çekirdeğin, iki parçalı grafikte ne tür bir minimum köşe örtüsü aldığımıza bağlı olduğu açıktır. Kalan köşe sayısı minimum olacak şekilde bir tane almak istiyorum. Daha önce bunu yalnızca zamanında yapabiliyorlardı . Zamanında bu algoritmanın bir uygulamasını buldum Böylece bu çekirdek, her dallanma aşamasında yüzbinlerce köşeden oluşan grafiklerde aranabilir.
sonuç
Uygulama, çözümümün birkaç yüz köşe ve birkaç bin kenar testinde iyi çalıştığını gösteriyor. Bu tür testlerde yarım saat içinde çözüm bulunmasını beklemek oldukça mümkündür. Kabul edilebilir bir sürede bir cevap bulma olasılığı, prensip olarak, grafiğin yeterince fazla sayıda yüksek dereceli köşeye sahip olması durumunda, örneğin derece 10 ve daha yüksekse artar.
Yarışmaya katılmak için çözümlerin şu adrese gönderilmesi gerekiyordu: . Orada sunulan bilgilere bakılırsa Açık testlerdeki çözümüm yirmi arasında üçüncü sırada yer alıyor ve ikincilikle arasında büyük bir fark var. Dürüst olmak gerekirse, çözümlerin yarışmada nasıl değerlendirileceği tam olarak belli değil: örneğin, benim çözümüm dördüncü sıradaki çözümden daha az testi geçiyor, ancak geçenlerde daha hızlı çalışıyor.
Kapalı testlerin sonuçları XNUMX Temmuz'da belli olacak.
Kaynak: habr.com