Ternární vyhledávání - Ternary search
A ternární vyhledávací algoritmus je technika v počítačová věda pro nalezení minimální nebo maximální a unimodální funkce. Ternární vyhledávání určuje, že minimum nebo maximum nemůže být v první třetině domény nebo že nemůže být v poslední třetině domény, poté se opakuje u zbývajících dvou třetin. Ternární vyhledávání je příkladem a algoritmus rozděl a panuj (vidět vyhledávací algoritmus ).
Funkce
Předpokládejme, že hledáme maximum F(X) a že víme, že maximum leží někde mezi A a B. Aby byl algoritmus použitelný, musí mít určitou hodnotu X takhle
- pro všechny A,b s A ≤ A < b ≤ X, my máme F(A) < F(b), a
- pro všechny A,b s X ≤ A < b ≤ B, máme F(A) > F(b).
Algoritmus
Nechat F(X) být unimodální funkce v určitém intervalu [l; r]. Vezměte libovolné dva body m1 a m2 v tomto segmentu: l < m1 < m2 < r. Pak existují tři možnosti:
- -li F(m1) < F(m2), pak požadované maximum nelze najít na levé straně - [l; m1]. To znamená, že maximum má dále smysl hledat pouze v intervalu [m1;r]
- -li F(m1) > F(m2), že situace je podobná té předchozí, až symetrie. Nyní požadované maximum nemůže být na pravé straně - [m2; r], tak jděte do segmentu [l; m2]
- -li F(m1) = f (m2), pak by mělo být vyhledávání provedeno v [m1; m2], ale tento případ lze připsat kterékoli z předchozích dvou (pro zjednodušení kódu). Dříve nebo později bude délka segmentu o něco menší než předem určená konstanta a proces lze zastavit.
výběrové body m1 a m2:
- m1 = l + (r-l)/3
- m2 = r - (r-l)/3
- Spusťte časovou objednávku
Rekurzivní algoritmus
def ternary_search(F, vlevo, odjet, že jo, absolutní_přesnost) -> plovák: "" "Levé a pravé jsou aktuální hranice; maximum je mezi nimi. """ -li břišní svaly(že jo - vlevo, odjet) < absolutní_přesnost: vrátit se (vlevo, odjet + že jo) / 2 left_third = (2*vlevo, odjet + že jo) / 3 správně_třetí = (vlevo, odjet + 2*že jo) / 3 -li F(left_third) < F(správně_třetí): vrátit se ternary_search(F, left_third, že jo, absolutní_přesnost) jiný: vrátit se ternary_search(F, vlevo, odjet, správně_třetí, absolutní_přesnost)
Iterativní algoritmus
def ternary_search(F, vlevo, odjet, že jo, absolutní_přesnost) -> plovák: "" "Najít maximum unimodální funkce f () uvnitř [vlevo, vpravo] Chcete-li zjistit minimum, obraťte příkaz if / else nebo porovnejte srovnání. """ zatímco břišní svaly(že jo - vlevo, odjet) >= absolutní_přesnost: left_third = vlevo, odjet + (že jo - vlevo, odjet) / 3 správně_třetí = že jo - (že jo - vlevo, odjet) / 3 -li F(left_third) < F(správně_třetí): vlevo, odjet = left_third jiný: že jo = správně_třetí # Levá a pravá jsou aktuální hranice; maximum je mezi nimi vrátit se (vlevo, odjet + že jo) / 2
Viz také
- Newtonova metoda v optimalizaci (lze použít k vyhledání, kde je derivace nulová)
- Hledání zlatých řezů (podobně jako ternární vyhledávání, užitečné, pokud vyhodnocení f zabere většinu času na iteraci)
- Algoritmus binárního vyhledávání (lze použít k vyhledání, kde se derivace mění ve znaménku)
- Hledání interpolace
- Exponenciální vyhledávání
- Lineární vyhledávání
- Implementace N Dimensional Ternary Search
Reference
tento článek ne uvést žádný Zdroje.Květen 2007) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |