Optimizasyon Algoritmaları Şampiyonası. - sayfa 117

 
ff'ye yapılan ilk çağrı, düzgün bir dağılıma sahip normal bir MT RNG tarafından oluşturulan bir diziden oluşmalıdır? RNG'nizi normal dağılımla kullanamıyor musunuz? ısrar etmeyeyim. Değerlendirme kriterlerine gelince. Kod yürütme için makine zamanını dikkate almayı öneriyorsunuz. Ama üzgünüm, bu başka bir operadan. Etkili bir ekstrema araması için kodu keskinleştirmek ve aynı zamanda donanımın o andaki durumuna da bağlı olan program bileşenlerinin makine yürütme süresini hesaba katmak başka bir şeydir. Çağrı sayısını ff olarak saymak yeterli olacaktır. Ama burada ısrar etmiyorum. Prosedürel konularda tekrar çıkmaza girmek istemiyorum ve benim algoritmam için bunun bir önemi yok. Şimdi bir sorum var. Hayır kuralı. ff'ye yapılan aramalar sabit ve ilgili herkes için aynı mı?
 

Yuri Evseenkov :
1. Первое обращение к фф должно состоять иэ массива сформированного штатным ГСЧ МТ с равномерным распределением? Свой ГСЧ с нормальным распределением использовать нельзя?

2. Değerlendirme kriterleri hakkında. Kod yürütme için makine zamanını dikkate almayı öneriyorsunuz.

1. İlk başlatmaya gelince, ısrar etmiyorum, sadece tavsiye ediyorum - bilinmeyen FF için (yani, şampiyonada bilinmeyen bir FF olacak), FF bilinmediği için herhangi bir başlangıç parametresi eşit derecede iyidir. Bu nedenle, herhangi bir RNG'yi kullanmak en pratik olanıdır (ne olursa olsun, ancak tercihen mümkün olduğunca çok sayıda seçenekle). Ayrıca, istatistiksel olarak güvenilir sonuçlar için, algoritmanın en az 20 çalışması yapılacaktır ve algoritmayı aynı sayılarla başlatmak pratik değildir.

2. Halihazırda belirlenmiş, değerlendirme kriterleri 2, FF fırlatmalarının doğruluğu ve sayısı . Ama linki takip ederek bir hesaplama örneği verdim, çok uzun zaman önceydi, lansman sayısı yerine zaman var. Bu nedenle, gönderide açıklığa kavuşturdum: FF'ye yapılan çağrıların doğruluğu ve sayısı iki değerlendirme kriteridir, doğruluk ise 3 kat daha fazla tercih edilir.

Tablodaki yerlerin bu hesaplamasına göre, probleminizin sonucuna göre benim algoritmam ilk sırayı alacaktır. Şunu düşünüyoruz: doğruluk daha yüksek, yani kriter doğruluk 3 ve FF başlatma sayısı daha fazla, yani 0, toplam 3+0=3 ve algoritmanız 0+1=1 puan alacak, yani, daha az puan Ancak bu, görevinizde kazandığım anlamına gelmez, çünkü birkaç koşul karşılanmaz. Ve eğer maksimum FF önceden biliniyorsa, o zaman tablo biraz farklı hesaplanacak, ilk "sanal" yere maksimum değer verilecek ve yerlerimiz buna göre hesaplanacak (puanlanan puan sayısı farklı olacaktır) .

 
Yuri Evseenkov :
Hayır kuralı. ff'ye yapılan aramalar sabit ve ilgili herkes için aynı mı?

Hayır, böyle bir kural hiç olmadı. Yalnızca izin verilen maksimum değer vardır. Ne kadar az isabet o kadar iyi, bu doğruluktan sonra ikinci en önemli kriterdir.

Şahsen, bununla uğraşmayacağım, tüm çağrı sınırını kullanacağım, başka bir deyişle, doğruluğa güveniyorum.

 
Alexander Laur :

Kısacası, saçmalık, Şampiyonluk değil.

Kazananı belirlemek için kriterler hareket halindeyken icat edilir.

15 sayfadan sonra kazananı değerlendirmek için yine de bir parametre girmeniz gerekecek.

Hepsi bir çırpıda, düşünülmemiş.

Ve gerçeklerin dileklerden daha karmaşık olduğu ortaya çıkıyor. :)

Bugünkü "Günün Düşüncesi" bu mu? Ya da "Yılın Düşüncesi"?

Kriterler on bir sayfa önce onaylandı ve hesaplama ilkesi ve formüller daha da önce. Çok sayıda fludorast var, bu, malzemenin izleyici tarafından anlaşılırlığını zorlaştırıyor - şimdi bu konuda sizin hakkınız var, kendinizi tebrik edebilirsiniz.

Bana soruldu - cevap verdim. Yarın sorarlarsa tekrar cevaplarım. Ama yarın Vasya Perezzabor perelezayko gelecek ve yine düşünceli bir şekilde "Şampiyonluk gomno, hareket halindeyken kuralları onlar oluşturuyor!" ..........

 
Alexander Laur :
O zaman şu soruyu cevaplayın: Doğruluk neden FF'ye erişim sayısından 3 kat daha değerlidir?!

Öyle karar verdim, çünkü organizatör. Başka sebepler de var.

Hiç kendi optimizasyon algoritmanızı yazdınız mı? Örneğin, 2E16 değerleri arasında 1. doğruyu bulmanın ve aynı anda sadece 50 deneme kullanmanın nasıl bir şey olduğunu hayal edebiliyor musunuz? Milyarlarca samanlıkta iğne bulmaktan daha zor. Ve bu sadece parametre bir ise, ancak 500 ise? 1000? 1000000?

 
Alexander Laur :
İlgilenen, yani "diğer" nedenler, örneğin 10 sayısı değil, 3 sayısı lehine argümanlar.
ampirik oran. 3 dakika beklemeye ve bir dakikadan 3 kat daha doğru sonuç almaya hazırım ve aynı sonuç daha kötü. Diğer oranlar pratik değildir.
 
Alexander Laur :
Ve bunun kazananı belirlemek için değerli bir argüman olduğunu düşünüyor musunuz?

Düşünmediğimi mi sanıyorsun? - boşuna öyle düşünüyorsun.

Bu soruma cevap ver:

Andrey Dik :

Hiç kendi optimizasyon algoritmanızı yazdınız mı? Örneğin, 2E16 değerleri arasında 1 doğru bulmanın ve aynı anda sadece 50 deneme kullanmanın nasıl bir şey olduğunu hayal edebiliyor musunuz? Milyarlarca samanlıkta iğne bulmaktan daha zor. Ve bu sadece parametre bir ise, ancak 500 ise? 1000? 1000000?

 
Alexander Laur :
Hiçbir şey düşünmüyorum, soruyorum ve cevap bekliyorum. Kaynaktan sorup cevap alabilecekken neden tahmin yürüteyim.

Böyle cevap verdi. ampirik oran. Hiçbir yerde bilimsel olarak sağlam bir cevap bulamazsınız.

Çözümün doğruluğunun, verilen bir çarpma olasılığı için çağrı sayısına bağlılığını Matematik ile birlikte bulmaya çalıştım, başarılı olamadık. Belki bu bir şekilde 3 sigma kuralıyla bağlantılıdır, ancak bir gerçek değildir.

 
Alexander Laur :

...doğrudan bir soru: Tam olarak olmasa bile bir ekstremum bulamayan, ancak belirli bir hatayla bir algoritma Şampiyonaya katılmalı mı?

Burada oturuyorum ve düşünüyorum ... Doğrudan cevap vermek ya da vermemek. Cevap vermeye karar verdim!

Neden "referansları" 3 kat aşan "doğruluk" kriterinin önemini sordunuz? Eğer bir "doğruluk" kriteri varsa, o zaman katılımcıların %100 doğruluğa sahip olmayacağı varsayılmalıdır... Bunun için doğruluğa göre sıralanacak bir "doğruluk" kriteri vardır. Buradan şu sonuca varıyoruz - olabilir!, ama zorunlu değil (yapmamalı), çünkü algoritması her zaman %100 doğru cevap veriyorsa neden kimse rekabet etsin ve bu aynı zamanda FF'ye kabul edilebilir sayıda çağrı için, algoritmadan gelen cevap bir kez alındığından beri. Yani kesinlikle hayır! - ayrıca, böyle bir algoritma gizlenmeli ve kimseye gösterilmemelidir.

Ve evet... Çok önemli bir nokta var. Algoritma, mutlak maksimumun nerede olduğunu "bilmiyorsa", ancak bunu bilmiyorsa, aksi halde neden onu ararsınız?, o zaman algoritmanın içinde maksimumun hangi doğrulukla bulunduğunu karşılaştırmanın bir yolu yoktur. Algoritmanın doğruluk derecesini yalnızca üzerinde deneyler yaparak yargılayabilen, ancak algoritma parametresini "böyle bir doğrulukla ara!" Yapamayız, umarım, anlaşılabilir sebeplerden dolayı.

 
Alexander Laur :

Basitçe cevap vereceğim:

1. Algoritma belirli bir doğrulukta bir ekstremum bulamıyorsa, bu algoritmanın Şampiyonada yeri yoktur;

2. 1. noktayı dikkate alarak, kazananı belirlemeye yalnızca belirli bir doğrulukla bir ekstremum BULMA yapan algoritmalar katılır;

3. Doğruluğa göre sıralama yok. Doğruluk, aralık tarafından verilir;

4. FF'ye yapılan talep sayısına göre kazananın belirlenmesi.

Bunun üzerine ayrılıyorum, sabah saat 2'de.

Açık.

Ama bu mümkün değil.

Birincisi: kesinliği belirtmek için nesnel bir neden yoktur. Bazıları için %1'lik bir sapma hoş olmayacak, ancak bazıları için %20 mutluluk için olacaktır. büyük ölçüde problemin türüne ve algoritmanın türüne bağlıdır. Şampiyonada "geçme doğruluğu" belirlemek, çeşitli ilginç algoritmik çözümleri ayıklamak anlamına gelecektir.

İkincisi: doğruluk, FF'ye yapılan çağrılara bağlıdır ve ayrıca doğrusal değildir. Farklı algoritma türleri için bağımlılık farklı olacaktır ve sadece “bu algoritma iyi ama bu kötü” diyemezsiniz, bunun için algoritmaları olabildiğince objektif olarak değerlendirmek için iki kriter kullanılır. Üçüncü bir kriter de vardı - algoritmanın çalışma süresi (FF değil), ancak çok öznel, OCL kullanan algoritmalar bazı makinelerde uçacak ve diğerlerinde yavaşlayacak, sonuç olarak, katılımcıları test etmek isteyen izleyiciler. çözümler, algoritmalar hakkında yeterli bir fikir edinemeyecektir. Bu nedenle geriye yalnızca iki kriter kalır: doğruluk ve FF'ye yapılan atıflar.