Inhalt dieses Artikels

In diesem Artikel werde ich ** Erklärung der Dichotomie- und Trisektionssuche und ihrer Implementierung ** beschreiben.

Als Merkmal dieses Artikels versuche ich, ** mathematisch streng ** zu erklären. Wenn Sie also eine intuitive Erklärung lesen möchten, Referenzartikel Siehe E6% 9C% 80% E5% BE% 8C% E3% 81% AB).

Vorwort

Im Folgenden wird der Definitionsbereich ** x ** der Funktion, die bei der dichotomen Suche (oder Trisektionssuche) berücksichtigt wird, auf ** das geschlossene Intervall ** für die Menge von Ganzzahlen oder reellen Zahlen gesetzt, in Wirklichkeit handelt es sich jedoch um eine vollständig geordnete Menge (Menge rationaler Zahlen). Wenn es sich um einen geschlossenen Abschnitt handelt (einschließlich usw.), kann es sich um einen Definitionsbereich handeln.

Auf einem Personal Computer wird sogar ein fortlaufender Satz wie eine reelle Zahl diskret behandelt, so dass zu beachten ist, dass die folgenden Sätze alle ** diskrete Sätze ** sind.

Außerdem habe ich den Artikel mit größter Sorgfalt geschrieben, aber es kann einige Fehler in der Beschreibung geben. In diesem Fall werde ich ihn korrigieren, indem ich ihn kommentiere oder um Bearbeitung bitte.

Halbierungssuche

Was ist eine Zweiteilung?

** x ** (ursprüngliche Zahl ist $ n $) [monoton ansteigende (oder abnehmende) Funktion](https://ja.wikipedia.org/wiki/%E5%8D%98%E8%AA%BF% E5% 86% 99% E5% 83% 8F) Wenn $ f $ definiert ist, existiert $ x ^ \ * \ in $ ** x **, wobei $ f (x ^ \ *) = t $ Es ist ein Algorithmus, der sucht, was mit $ O (\ log n) $ zu tun ist. [^ 1]

** Im Folgenden wird $ f $ implizit als monoton ansteigende Funktion verwendet, aber das gleiche Argument kann auch dann vorgebracht werden, wenn $ f $ eine monoton abnehmende Funktion ist, indem Maßnahmen wie die Umkehrung der Ungleichung entwickelt werden. Ich werde. ** ** **

In der Dichotomie wird der Minimalwert mit hoher Geschwindigkeit gesucht, indem der Suchbereich durchsucht wird, in dem die Funktion $ f $ durch $ \ frac {1} {2} $ definiert ist, jedoch unter der folgenden Annahme (✳︎) Da $ \ frac {1} {2} $ läuft, wird (✳︎) angezeigt.

(✳︎) Teilen Sie für $ x ^ \ * \ in [l, r] $, wobei $ f (x ^ \ *) = t $ im geschlossenen Intervall $ [l, r] $ ist, es in zwei gleiche Teile von $ [l, r] $ Wenn der Punkt $ k $ ist $ f (k) \ geqq t \ rightarrow x ^ \ * \ in [l, k] $ und $ f (k) <t \ rightarrow x ^ \ * \ in (k, r] $

Beweis

(1) Wenn $ f (k) \ geqq t $ $ f (k) \ geqq t \ leftrightarrow k \ geqq x ^ \ * $ ($ \ weil f $ eine monoton ansteigende Funktion ist) Daher ist $ x ^ \ * $ in $ [l, k] $ enthalten.

(2) Wenn $ f (k) <t $ $ f (k) <t \ leftrightarrow k <x ^ \ * $ ($ \ weil f $ eine monoton ansteigende Funktion ist) Daher ist $ x ^ \ * $ in $ (k, r] $ enthalten.

Daher ist (✳︎) aus (1) und (2) gezeigt.

[Q.E.D.]

Referenzdiagramm

Das folgende Diagramm zeigt das Verhalten der Dichotomie. Ich hoffe es hilft dir zu verstehen.

Wenn $ false $ $ 0 $ und $ true $ 1 $ ist, ist der Rückgabewert ein Bool-Wert und $ x ^ \ * \ in $ ** x ** ist die Grenze zwischen $ false $ und $ true $. Sie können sich eine Funktion wie diese vorstellen und die Grenze $ x ^ \ * $ mit einem ähnlichen Algorithmus finden.

Implementierung der Dichotomie

Im Folgenden finden Sie eine konkrete Implementierung der Dichotomie (ich denke, das Auskommentieren im Code hilft bei der Implementierung).

Da der Zweck darin besteht, die Implementierung zu bestätigen, werde ich das in diesem Artikel behandelte Problem nicht erläutern. Es wird jedoch empfohlen, das Problem einmal zu lösen, um das Verständnis der Dichotomie zu vertiefen.

① Wenn der Rückgabewert der Funktion kein Bool-Wert ist

Es wird häufig verwendet, um Elemente in einem sortierten Array zu finden, das $ k $ ist. Betrachtet man den Definitionsbereich ** x ** als eine Menge von Indizes und den Rückgabewert der Funktion als ein Element des Arrays, das jedem Index entspricht, so kann die monotone Funktion $ f $ im Definitionsbereich ** x ** definiert werden. Ich verstehe das. Wenn Sie $ k $ in einem sortierten Array finden möchten, können Sie das Halbierungsmodul verwenden, damit Sie selbst keine Dichotomie implementieren müssen. Weitere Informationen finden Sie unter Dieser Artikel.

Hier suchen wir nach dem Index des Elements, dessen Array $ a = [0,1,1,2,4,5,6,8,8,9,10] $ durch Dichotomie.

`basicbisect.py`


a=[0,1,1,2,4,5,6,8,8,9,10]

#Bisektionssuchcode

#(1)l,r ist l an beiden Enden<=r
#Stellen Sie sicher, dass der Index l kleiner als 2 und r größer oder gleich 2 ist.
l,r=0,10
#(2)l=r oder l=r-Pause bei 1
while l+1<r:
    #(3)Mittelpunkt des geschlossenen Abschnitts(Schneiden Sie den Bruchteil von ab)
    #In Anbetracht des Überlaufs wird wie folgt geschrieben
    k=l+(r-l)//2
    #(4)Aufteilung des geschlossenen Abschnitts
    #a[k]>=Im Fall von 2 setzen Sie den größeren Endpunkt auf k und a[k]<Im Fall von 2 setzen Sie den kleineren Endpunkt auf k
    if a[k]>=2:
        r=k
    else:
        l=k
#(5)Ausgabe
#r ist a[x]>=Mindestens 2 Indizes(a[x]=Beachten Sie, dass es nicht immer einen Index x gibt, der 2 ist.)
print(r)

(2) Wenn der Rückgabewert der Funktion ein Bool-Wert ist

Wenn Sie die Dichotomie selbst implementieren möchten, ist dieses Muster am wahrscheinlichsten. Im Folgenden wird der Code basierend auf ABC063D-Widespread und x geschrieben, wodurch der Rückgabewert der Funktion $ f $ $ true $ wird. Ich suche den kleinsten von ihnen. Wenn Sie wissen möchten, wie dieses Problem gelöst werden kann, wählen Sie Hauptlösung oder Mein Kommentarartikel. Siehe Artikel / 9efaf76418ef4677f979).

`widespread.py`


import math
n,a,b=map(int,input().split())
h=[int(input()) for i in range(n)]

def f(x):
    global n
    c=0
    for i in range(n):
        if h[i]-x*b>0:
            c+=math.ceil((h[i]-x*b)/(a-b))
    return c<=x

#Bisektionssuchcode

#(1)l,r ist l an beiden Enden<=r
#Bestätigen Sie zu diesem Zeitpunkt, dass l falsch und r wahr ist.
l,r=0,10**9
#(2)l=r oder l=r-Pause bei 1
while l+1<r:
    #(3)Mittelpunkt des geschlossenen Abschnitts(Schneiden Sie den Bruchteil von ab)
    #In Anbetracht des Überlaufs wird wie folgt geschrieben
    k=l+(r-l)//2
    #(4)Aufteilung des geschlossenen Abschnitts
    #x=Wenn k wahr ist, setzen Sie den größeren Endpunkt auf k und x=Wenn k falsch ist, setzen Sie den kleineren Endpunkt auf k
    if f(k):
        r=k
    else:
        l=k
#(5)Ausgabe
#r ist f(x)=Das kleinste von wahrem x
print(r)

Drei-Minuten-Suche

Was ist eine dreiminütige Suche?

** x ** (ursprüngliche Nummer ist $ n $) ** Pseudo [konvexe (oder konkave) Funktion](https://ja.wikipedia.org/wiki/%E5%87%B8%E9%96% A2% E6% 95% B0) ** Wenn $ f $ definiert ist, ist $ x ^ \ * \ in $ ** x **, wobei $ f (x) $ das Minimum (oder Maximum) ist, $ O. (\ log n) Ein Algorithmus, der mit $ sucht. Außerdem hat ** x ** immer einen minimalen Punkt (oder maximalen Punkt), da es sich um eine endliche Menge handelt.

** Im Folgenden wird $ f $ implizit als pseudokonvexe Funktion betrachtet, aber das gleiche Argument kann auch dann vorgebracht werden, wenn $ f $ eine pseudokonkave Funktion ist, indem Maßnahmen wie die Umkehrung der Ungleichung entwickelt werden. Masu **

Hier ist die pseudokonvexe Funktion wie folgt definiert. [^ 2]

$ \ Lambda x_1 + (1- \ Lambda) x_2 \ in $ ** x ** für $ ^ ∀ x_1, x_2 \ in $ ** x **, $ ^ ∀ \ Lambda \ in [0,1] $ Dann gilt $ f (\ lambda x_1 + (1- \ lambda) x_2) \ leqq \ lambda f (x_1) + (1- \ lambda) f (x_2) $.

Bei der dreiteiligen Suche wird der Mindestwert mit hoher Geschwindigkeit gesucht, indem der Suchbereich durchsucht wird, in dem die Funktion $ f $ durch $ \ frac {2} {3} $ definiert ist, jedoch unter der folgenden Annahme (✳︎) Dies wird angezeigt, weil $ \ frac {2} {3} $ hinzugefügt wird.

(✳︎) Für den Minimalpunkt $ x ^ \ * \ in [l, r] $ im geschlossenen Intervall $ [l, r] $ ist der Trisektionspunkt dieses Intervalls $ c_1, c_2 (l \ leqq c_1 \ leqq c_2 \ leqq Wenn r) $ $ f (c_1) \ leqq f (c_2) \ rightarrow $ Der Mindestpunkt $ x ^ \ * $ ist in $ [l, c_2] $ enthalten. $ f (c_1) \ geqq f (c_2) \ rightarrow $ Der Mindestpunkt $ x ^ \ * $ ist in $ [c_1, r] $ enthalten.

Beweis

(1) Wenn $ x ^ \ * \ in [l, c_1] $ Da $ x ^ \ * \ leqq c_1 \ leqq c_2 $ existiert, existiert $ \ lambda \ in [0,1] $, was $ c_1 = \ lambda x ^ \ * + (1- \ lambda) c_2 $ ist. In diesem Moment,

\begin{align}
f(c_1) &= f(\lambda x^*+(1-\lambda)c_2) \\
& \leqq \lambda f(x^*)+(1-\lambda)f(c_2) \ (\weil f eine pseudokonvexe Funktion ist)\\
& \leqq \lambda f(c_2)+(1-\lambda)f(c_2) \ (\because f(x^*) \leqq f(c_2))\\
& = f(c_2)
\end{align}

(2) Wenn $ x ^ \ * \ in [c_1, c_2] $ Mindestens eines von $ f (c_1) \ leqq f (c_2) $ und $ f (c_1) \ geqq f (c_2) $ gilt.

(3) Wenn $ x ^ \ * \ in [c_2, r] $ Wenn Sie dasselbe wie (1) tun, können Sie $ f (c_1) \ geqq f (c_2) $ erhalten.

Daher ist (✳︎) von (1) bis (3) gezeigt.

[Q.E.D.]

Referenzdiagramm

Die folgende Abbildung zeigt die Aufteilung des Abschnitts der dreiminütigen Suche. Ich hoffe es hilft dir zu verstehen.

Implementierung der Trisektionssuche

Im Folgenden finden Sie eine konkrete Implementierung der Trisektionssuche (ich denke, das Auskommentieren im Code hilft bei der Implementierung).

(1) Wenn der Definitionsbereich der Funktion ein geschlossenes Intervall für eine reelle Zahl ist

Betrachten Sie im Folgenden ARC054-B Moores Gesetz. In diesem Problem eine reelle Zahl $ x \ in [0,10 ^ {18], die $ f (x) = x + \ frac {p} {2 ^ {\ frac {x} {1,5}}} $ minimiert }] Es kann auf das Problem reduziert werden, über $ nachzudenken.

Hier kann diese Funktion $ f (x) $ zweimal unterschieden werden. Wenn also berechnet, ist $ f ^ {''} (x) = (\ log 2) ^ 2 (- \ frac {2} {3}) ^ 2p \ times 2 ^ {- \ frac {2x} {3}}> 0 $, sodass Sie sehen können, dass die ** Funktion $ f (x) $ eine konvexe Funktion ** ist. [^ 3]

Daher können Sie durch Dreiteilungssuche nach dem Mindestpunkt $ x $ suchen und den folgenden Code schreiben. Auch hier ist der Definitionsbereich der Funktion keine Ganzzahl, sondern eine reelle Zahl, und der Fehlerbereich ist bis zu $ 10 ^ {-8} $ zulässig, sodass der Suchbereich bei einer Suche $ \ frac {2} {3} $ ist. In Anbetracht dessen ist $ \ log_ {\ frac {3} {2}} \ frac {10 ^ {18}} {10 ^ {-8}} = 26 \ times \ log_ {\ frac {3} Die while-Anweisung wird ungefähr {2}} {10} $ Mal gedreht, wodurch das Programm ausreichend schnell ist.

`mooreslaw.py`


p=float(input())

#(1)Definieren Sie die Funktion f, die Sie minimieren möchten
def f(x):
    global p
    return x+p*pow(2,-(x/1.5))

#(2)Ich möchte den Minimalwert der Funktion f l an beiden Enden des geschlossenen Intervalls finden,Setzen Sie mit r(l<=r)
l,r=0,10**18
#(3)Der Fehler ist 10^-Drehen Sie die while-Anweisung, bis sie unter 8 fällt.
while l+pow(10,-8)<r:
    #(4)Platzieren Sie die Trisektionspunkte wie unten gezeigt, um ein Überlaufen zu verhindern
    c1=l+(r-l)/3
    c2=r-(r-l)/3
    #(5)Machen Sie ein Update
    if f(c1)<f(c2):
        r=c2
    else:
        l=c1
#(6)Die endgültige Ausgabe ist l,Entweder ist r in Ordnung
print(f(l))

(2) Wenn der Definitionsbereich der Funktion ein geschlossenes Intervall für eine Ganzzahl ist

Betrachten Sie im Folgenden ABC102D-Equal Cut. Da sich diese Methode ein wenig von dieser Lösung unterscheidet, werde ich Mein Kommentarartikel als Referenzartikel einführen.

Dies ist ein ziemlich schwieriges Problem, daher möchte ich, dass Sie nur die Implementierungsmethode im Vergleich zum Fall von ① überprüfen.

`equalcut.py`


n=int(input())
a=list(map(int,input().split()))
s=[a[0]]
for i in range(1,n):
    s.append(s[-1]+a[i])

#(1)Definieren Sie die Funktion f, die Sie minimieren möchten
def f(c,i):
    global n,a,s
    return abs(s[c]-(s[i]-s[c]))

#(1)
def g(c,i):
    global n,a,s
    return abs((s[c]-s[i])-(s[n-1]-s[c]))

ans=[]
for i in range(1,n-2):
    ans_=[]

    #(2)Ich möchte den Minimalwert der Funktion f l an beiden Enden des geschlossenen Intervalls finden,Setzen Sie mit r(l<=r)
    #Hier ist der Indexwert
    l,r=0,i
    #(3)Da es eine ganze Zahl ist, r=l,l+1,l+Sollte einer von 2 sein
    #Im Gegenteil, r>=l+Im Fall von 3 kann der Unterschied zwischen r und l kleiner gemacht werden.
    while l+2<r:
        #(4)Trisektionspunkt(Schneiden Sie den Bruchteil ab)
        c1=l+(r-l)//3
        c2=r-(r-l)//3
        #(5)Machen Sie ein Update
        if f(c1,i)<f(c2,i):
            r=c2
        else:
            l=c1
    #(6)Die letzte Anfrage ist l~Das Element von r, das den Wert der Funktion f minimiert
    x=sorted([(f(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x])
    ans_.append(s[i]-s[x])

    #Entscheide dich rechts

    #(2)
    l,r=i+1,n-1
    #(3)
    while l+2<r:
        #(4)
        c1=l+(r-l)//3
        c2=r-(r-l)//3
        #(5)
        if g(c1,i)>g(c2,i):
            l=c1
        else:
            r=c2
    #(6)
    x=sorted([(g(j,i),j) for j in range(l,r+1)])[0][1]
    ans_.append(s[x]-s[i])
    ans_.append(s[n-1]-s[x])

    ans.append(max(ans_)-min(ans_))
print(min(ans))

Schließlich

Ich war enttäuscht, dass ich das Problem mit der dreiminütigen Suche nicht lösen konnte, und habe es daher streng mathematisch betrachtet.

Bitte beziehen Sie sich auch auf das Montageteil, wie ich es selbst entworfen habe.

Und ich möchte der Universitätssynchronisation meinen Dank dafür aussprechen, dass sie mir geholfen hat, die Korrekturen in dieser mathematisch strengen Erklärung vorzunehmen.

Referenzartikel

Verallgemeinerung des Dichotomiealgorithmus - Empfehlung der Dichotomiemethode Implementierungsmuster der Dichotomie, die niemals fehlerhaft ist, und 5 Gründe, warum sie nicht fehlerhaft ist

[^ 1]: Die Erklärung der Dichotomie setzt voraus, dass $ x ^ \ * $ existiert, aber beachte, dass ** $ x ^ \ * $ möglicherweise nicht existiert **. [^ 2]: Wir haben eine pseudokonvexe Funktion anstelle einer konvexen Funktion eingeführt, da die erstere in einer kontinuierlichen Menge definiert ist. Daher betrachten wir eine Funktion in einer ** diskreten Menge **. [^ 3]: Für die Funktion $ f (x) $, die in einer kontinuierlichen Menge zweimal differenziert werden kann, ist sie eine konvexe Funktion, wenn die doppelte Differenzierung nicht negativ ist, und wenn es sich in einer kontinuierlichen Menge um eine konvexe Funktion handelt, ist sie eine Teilmenge davon. Es wird implizit als pseudokonvexe Funktion in einer diskreten Menge verwendet.

[PYTHON] Mathematische Erklärung der Dichotomie- und Trisektionssuch- und Implementierungsmethode ohne Fehler