Üçlü arama - Ternary search

Bir üçlü arama algoritması bir tekniktir bilgisayar Bilimi bulmak için minimum veya maksimum bir tek modlu işlevi. Üçlü arama, minimum veya maksimumun alanın ilk üçte birinde olamayacağını veya alanın son üçte birinde olamayacağını belirler ve ardından kalan üçte ikisinde tekrar eder. Üçlü arama, bir böl ve ele geçir algoritması (görmek arama algoritması ).

İşlev

Maksimum aradığımızı varsayalım f(x) ve maksimumun aralarında bir yerde olduğunu bildiğimizi Bir ve B. Algoritmanın uygulanabilir olması için bir değer olması gerekir x öyle ki

  • hepsi için a,b ile ≤ a < b ≤ x, sahibiz f(a) < f(b), ve
  • hepsi için a,b ile x ≤ a < b ≤ B, bizde f(a) > f(b).

Algoritma

İzin Vermek f(x) olmak tek modlu belirli aralıklarla işlev [l; r]. Herhangi iki noktayı alın m1 ve m2 bu segmentte: l < m1 < m2 < r. O zaman üç olasılık vardır:

  • Eğer f(m1) < f(m2), o zaman gerekli maksimum sol tarafta bulunamaz - [l; m1]. Bu, maksimumun yalnızca aralığa bakmanın daha mantıklı olduğu anlamına gelir. [m1;r]
  • Eğer f(m1) > f(m2), durum bir öncekine benzer, simetriye kadar. Şimdi, gerekli maksimum sağ tarafta olamaz - [m2; r]o halde segmente git [l; m2]
  • Eğer f(m1) = f (m2)arama yapılmalı [m1; m2], ancak bu durum önceki ikisinden herhangi birine atfedilebilir (kodu basitleştirmek için). Er ya da geç, parçanın uzunluğu önceden belirlenmiş bir sabitten biraz daha az olacaktır ve işlem durdurulabilir.

seçim noktaları m1 ve m2:

  • m1 = l + (r-l)/3
  • m2 = r - (r-l)/3
Çalışma süresi sırası

Özyinelemeli algoritma

def ternary_search(f, ayrıldı, sağ, mutlak_hassasiyet) -> yüzen:    "" "Sol ve sağ mevcut sınırlardır;    maksimum aralarında.    """    Eğer abs(sağ - ayrıldı) < mutlak_hassasiyet:        dönüş (ayrıldı + sağ) / 2    left_third = (2*ayrıldı + sağ) / 3    right_third = (ayrıldı + 2*sağ) / 3    Eğer f(left_third) < f(right_third):        dönüş ternary_search(f, left_third, sağ, mutlak_hassasiyet)    Başka:        dönüş ternary_search(f, ayrıldı, right_third, mutlak_hassasiyet)

Yinelemeli algoritma

def ternary_search(f, ayrıldı, sağ, mutlak_hassasiyet) -> yüzen:    "" "[Sol, sağ] içinde maksimum tek modlu f () fonksiyonu bulun    Minimum değeri bulmak için if / else ifadesini tersine çevirin veya karşılaştırmayı tersine çevirin.    """    süre abs(sağ - ayrıldı) >= mutlak_hassasiyet:        left_third = ayrıldı + (sağ - ayrıldı) / 3        right_third = sağ - (sağ - ayrıldı) / 3        Eğer f(left_third) < f(right_third):            ayrıldı = left_third        Başka:            sağ = right_third     # Sol ve sağ mevcut sınırlardır; maksimum aralarında     dönüş (ayrıldı + sağ) / 2

Ayrıca bakınız

Referanslar