Kaba kuvvet arama - Brute-force search

Gelen bilgisayar bilimleri , kaba kuvvet arama veya ayrıntılı aramada olarak da bilinen oluşturmak ve test , bir çok genel problem çözme tekniğini ve algoritmik paradigma sistematik çözümü için tüm olası adayları numaralandırma ve kontrol edilmesini içermektedir her aday tatmin Sorunun ifadesi olmadığını .

Bulan bir kaba kuvvet algoritması bölenler a doğal sayı , n , n, 1 ila tüm tamsayıları numaralandırmak ve bunların her biri ikiye bölen kontrol olur n kalanı olmadan. Sekiz vezir bulmacası için kaba kuvvet yaklaşımı , 64 karelik satranç tahtasında 8 parçanın tüm olası düzenlemelerini inceleyecek ve her düzenleme için, her bir (kraliçe) taşının diğerine saldırıp saldıramayacağını kontrol edecektir.

Bir kaba kuvvet aramanın uygulanması basittir ve varsa her zaman bir çözüm bulacaktır, ancak uygulama maliyetleri aday çözümlerin sayısı ile orantılıdır - birçok pratik problemde sorunun boyutu arttıkça çok hızlı büyüme eğilimindedir ( § Kombinatoryal patlama ). Bu nedenle, kaba kuvvet araması genellikle problem boyutu sınırlı olduğunda veya aday çözümler kümesini yönetilebilir bir boyuta indirmek için kullanılabilecek probleme özgü buluşsal yöntemler olduğunda kullanılır. Yöntem, uygulamanın basitliği hızdan daha önemli olduğunda da kullanılır.

Örneğin, algoritmadaki herhangi bir hatanın çok ciddi sonuçlara yol açacağı kritik uygulamalarda veya matematiksel bir teoremi kanıtlamak için bir bilgisayar kullanırken durum böyledir . Kaba kuvvet araması, diğer algoritmaları veya meta-sezgiselleri karşılaştırırken bir temel yöntem olarak da kullanışlıdır . Gerçekte, kaba kuvvetle arama, en basit meta-sezgisel arama olarak görülebilir . Kaba kuvvet araması , büyük çözüm kümelerinin açıkça numaralandırılmadan atılabildiği geri izleme ile karıştırılmamalıdır (yukarıdaki sekiz kraliçe problemine ders kitabındaki bilgisayar çözümünde olduğu gibi). Bir tablodaki bir öğeyi bulmak için kaba kuvvet yöntemine - yani, sırayla ikincisinin tüm girişlerini kontrol edin - doğrusal arama olarak adlandırılır .

Kaba kuvvet aramasının uygulanması

Temel algoritma

Mevcut olandan sonra P'ye aday olmak için c .

geçerli ( P , c ): c adayının P için bir çözüm olup olmadığını kontrol edin .
çıkış ( P , C ) çözeltisi kullanmak c ait P uygulamasına uygun olarak.

Bir sonraki prosedür, mevcut prosedürden sonra, P örneği için başka aday olmadığını da belirtmelidir c . Bunu yapmanın uygun bir yolu, herhangi bir gerçek adaydan farklı bir "boş aday", bazı geleneksel veri değerleri Λ döndürmektir. Benzer şekilde, ilk prosedür P örneği için hiç aday yoksa geri dönmelidir . Kaba kuvvet yöntemi daha sonra algoritma tarafından ifade edilir

c ← first(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    c ← next(P, c)
end while

Bir tamsayıdır ve bölenler arayan Örneğin, n , örneğin veri P sayısıdır , n . Çağrı ilk ( n ) bir tam sayı 1 döndürmelidir n ≥ 1 veya Λ aksi; Çağrı aşağıdaki ( n , c ) döndürmelidir c + 1 ise C < n Aksi belirtilmediği taktirde ve Λ; ve geçerli ( n , c ), ancak ve ancak c , n'nin böleni ise true döndürmelidir . (Aslında, Λ'yi n + 1 olarak seçersek , n ≥ 1 ve c < n testleri gereksizdir.) Yukarıdaki kaba kuvvet arama algoritması , verilen P örneğine bir çözüm olan her aday için çıktıyı çağıracaktır . Algoritma, ilk çözümü veya belirli sayıda çözümü bulduktan sonra duracak şekilde kolayca değiştirilebilir; veya belirli sayıda adayı test ettikten sonra veya belirli bir CPU zamanı harcadıktan sonra .

Kombinatoryal patlama

Kaba kuvvet yönteminin temel dezavantajı, gerçek dünyadaki birçok sorun için, doğal aday sayısının engelleyici bir şekilde fazla olmasıdır. Yukarıda açıklandığı gibi bir dizi bölenler bakmak Örneğin, test edilen aday sayısı verilen sayı olacaktır n . Dolayısıyla, n'nin on altı ondalık basamağı varsa, örneğin, arama, tipik bir PC'de birkaç gün sürecek olan en az 10 ¹⁵ bilgisayar talimatının yürütülmesini gerektirecektir . Eğer n , ortalama olarak yaklaşık 19 ondalık basamağa sahip rastgele 64 bitlik bir doğal sayı ise, arama yaklaşık 10 yıl sürecektir. Verilerin büyüklüğü arttıkça aday sayısındaki bu hızlı artış her türlü sorunda ortaya çıkmaktadır. Örneğin, 10 harfin belirli bir yeniden düzenlenmesini istiyorsak, o zaman 10 harfimiz var! = Tipik bir bilgisayarın bir saniyeden daha kısa sürede oluşturup test edebileceği, dikkate alınması gereken 3.628.800 aday. Ancak, veri boyutunda yalnızca% 10'luk bir artış olan bir harf daha eklemek, aday sayısını% 1000 artışla 11 ile çarpacaktır. 20 harf için aday sayısı 20 !, yani yaklaşık 2,4 × 10 ¹⁸ veya 2,4 kentilyon ; ve arama yaklaşık 10 yıl sürecektir. Bu hoş karşılanmayan fenomen, genel olarak kombinasyon patlaması veya boyutluluk laneti olarak adlandırılır .

Kombinasyonel karmaşıklığın çözülebilirlik sınırına yol açtığı bir duruma bir örnek satrancı çözmektir . Satranç çözülmüş bir oyun değil . 2005 yılında, altı veya daha az taştan oluşan tüm satranç oyunu sonları çözüldü ve mükemmel oynandığında her pozisyonun sonucunu gösterdi. Bir satranç taşı daha eklenerek masa tabanını tamamlamak on yıl daha sürdü, böylece 7 parçalı bir masa tabanı tamamlandı. Bir satranç oyunsonuna bir parça daha eklemek (böylece 8 parçalı bir masa tabanı yapmak), eklenen kombinatoryal karmaşıklık nedeniyle zorlu kabul edilir.

Kaba kuvvet aramalarını hızlandırmak

Bir kaba kuvvet algoritmasını hızlandırmanın bir yolu , problem sınıfına özgü buluşsal yöntemler kullanarak arama alanını, yani aday çözümler kümesini azaltmaktır . Örneğin, sekiz vezir probleminde sorun , sekiz veziri standart bir satranç tahtasına yerleştirmektir, böylece hiçbir vezir diğerine saldırmaz. Her kraliçe 64 kareden herhangi birine yerleştirilebildiğinden, prensipte dikkate alınması gereken 64 ⁸ = 281,474,976,710,656 olasılık vardır. Ancak, kraliçelerin hepsi aynı olduğundan ve aynı kareye iki kraliçe yerleştirilemeyeceğinden, adaylar 64 karenin tamamından 8 karelik bir set seçmenin olası yollarıdır ; bu, 64'ün 8 = 64! / (56! * 8!) = 4,426,165,368 aday çözümünü seçmesi anlamına gelir - önceki tahminin yaklaşık 1 / 60.000'i. Ayrıca, aynı satırda veya aynı sütunda iki kraliçe ile yapılan hiçbir düzenleme bir çözüm olamaz. Bu nedenle, aday kümesini bu düzenlemelerle daha da sınırlayabiliriz.

Bu örneğin gösterdiği gibi, biraz analiz, genellikle aday çözümlerin sayısında önemli düşüşlere yol açar ve çözülemeyen bir sorunu önemsiz bir soruna dönüştürebilir.

Bazı durumlarda, analiz adayları tüm geçerli çözümler kümesine indirgeyebilir; yani, testlerle zaman kaybetmeden ve geçersiz adaylar oluşturmadan, istenen tüm çözümleri doğrudan numaralandıran (veya uygun şekilde tek bir çözüm bulan) bir algoritma sağlayabilir. Örneğin, "1 ile 1.000.000 arasında 417'ye eşit olarak bölünebilen tüm tam sayıları bulma" problemi için saf bir kaba kuvvet çözümü, aralıktaki tüm tam sayıları, bölünebilirlik açısından test ederek üretecektir. Bununla birlikte, bu sorun, 417 ile başlayıp sayı 1.000.000'u geçene kadar tekrar tekrar 417 ekleyerek çok daha verimli bir şekilde çözülebilir - bu sadece 2398 (= 1.000.000 ÷ 417) adım alır ve test olmadan.

Arama alanını yeniden sıralama

Tüm çözümler yerine tek bir çözüm gerektiren uygulamalarda , bir kaba kuvvet aramasının beklenen çalışma süresi genellikle adayların test edilme sırasına bağlı olacaktır. Genel bir kural olarak, önce en umut verici adayları test etmelisiniz. Örneğin, rastgele bir n sayısının uygun bir bölenini ararken , aday bölenleri artan sırayla 2'den n'ye - 1'e saymak daha iyidir - çünkü n'nin c ile bölünebilme olasılığı şu şekildedir: 1 / c . Ayrıca, bir adayın geçerli olma olasılığı, genellikle önceki başarısız denemelerden etkilenir. Örneğin, belirli bir 1000 bitlik P dizesinde 1 bit bulma sorununu düşünün . Bu durumda, aday çözümler 1'den 1000'e kadar olan indislerdir ve P [ c ] = 1 ise aday c geçerlidir . Şimdi, P'nin ilk bitinin eşit olasılıkla 0 veya 1 olduğunu , ancak bundan sonraki her bitin% 90 olasılıkla bir öncekine eşit olduğunu varsayalım . Aday artan şekilde numaralandırılmış ise, 1 ila 1000, sayı t başarı ortalama 6 ile ilgili olacak önce aday incelenmiştir. Öte yandan, adaylar 1,11,21,31 ... 991,2,12,22,32 vb. Sırayla sıralanırsa, beklenen t değeri sadece 2'den biraz fazla olacaktır. Genel olarak, arama alanı , önceki denemelerin olmadığı göz önüne alındığında , bir sonraki adayın büyük olasılıkla geçerli olacağı şekilde numaralandırılmalıdır . Dolayısıyla, geçerli çözümlerin bir anlamda "kümelenmesi" muhtemel ise, o zaman her yeni aday, aynı anlamda öncekilerden mümkün olduğunca uzakta olmalıdır. Elbette, çözümlerin şans eseri beklenenden daha tekdüze bir şekilde yayılma olasılığı varsa, tersi geçerlidir.

Kaba kuvvet aramasına alternatifler

Çözüm hakkında sahip olabileceğiniz çeşitli kısmi bilgilerden yararlanmak için tasarlanmış birçok başka arama yöntemi veya meta-sezgisel araştırma vardır. Sezgisel tarama, aramanın bölümlerinin erken kesilmesi için de kullanılabilir. Bunun bir örneği, aramanın erken bir aşamasında birçok alt ağacı ortadan kaldıran oyun ağaçlarını aramak için minimum ilkedir. Dil ayrıştırma gibi belirli alanlarda, grafik ayrıştırma gibi teknikler, üstel bir karmaşıklık problemini bir polinom karmaşıklık problemine indirgemek için problemdeki kısıtlamalardan faydalanabilir. Kısıt Memnuniyet Sorunları gibi birçok durumda, Kısıt programlama dillerinde verimli bir şekilde uygulanan Kısıt yayılımı yoluyla arama alanı önemli ölçüde azaltılabilir . Sorunlar için arama alanı, tüm sorunun basitleştirilmiş bir sürümle değiştirilmesiyle de azaltılabilir. Örneğin, bilgisayar satrancında , oyunun geri kalanı için mümkün olan tüm hamlelerin tam minimax ağacını hesaplamak yerine , ağaç belirli sayıda hamlede budanarak ve kalanıyla daha sınırlı bir minimum maksimum olasılık ağacı hesaplanır. Statik bir değerlendirme fonksiyonu ile yaklaştırılan ağaç .

Kriptografide

In kriptografi , bir kaba kuvvet saldırısı sistematik olası tüm kontrol edilmesini içerir anahtarları doğru anahtar bulunana kadar. Bu strateji teorik olarak , bir şifreleme sistemindeki herhangi bir zayıflıktan yararlanamayan saldırgan tarafından herhangi bir şifrelenmiş veriye karşı ( tek seferlik bir blok hariç ) kullanılabilir, aksi takdirde işini kolaylaştırabilir.

Anahtar uzunluğu şifreleme kullanılan kısa olanlar olana göre katlanarak daha zor uzun anahtarlar, bir kaba kuvvet saldırısını gerçekleştiren pratik uygulanabilirliği belirler. Kaba kuvvet saldırıları, kodlanacak verileri gizleyerek daha az etkili hale getirilebilir; bu, bir saldırganın kodu ne zaman kırdığını fark etmesini zorlaştıran bir şeydir. Bir şifreleme sisteminin gücünün ölçülerinden biri, bir saldırganın kendisine karşı başarılı bir kaba kuvvet saldırısı düzenlemesinin teorik olarak ne kadar süreceğidir.

Languages

In other projects