Explication mathématique de la recherche de dichotomie et de trisection et méthode de mise en œuvre sans bogues

Contenu de cet article

Dans cet article, je décrirai ** l'explication de la recherche de dichotomie et de trisection et sa mise en œuvre **.

Dans le cadre de cet article, j'essaie d'expliquer ** mathématiquement rigoureusement **, donc si vous voulez lire une explication intuitive, [Article de référence](https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453#% Veuillez voir E6% 9C% 80% E5% BE% 8C% E3% 81% AB).

Préface

Dans ce qui suit, la zone de définition ** x ** de la fonction considérée dans la recherche dichotomique (ou recherche par trisection) est fixée à ** l'intervalle fermé ** sur l'ensemble des entiers ou des nombres réels, mais en réalité c'est un ensemble entièrement ordonné (ensemble de nombres rationnels). S'il s'agit d'une section fermée sur (y compris etc.), cela peut être une zone de définition.

De plus, sur un ordinateur personnel, même un ensemble continu tel qu'un nombre réel est traité de manière discrète, il convient donc de noter que les ensembles suivants sont tous des ** ensembles discrets **.

De plus, j'ai écrit l'article avec le plus grand soin, mais il peut y avoir des erreurs dans la description. Dans ce cas, je le corrigerai si vous commentez ou demandez une modification.

Recherche de bisection

Qu'est-ce qu'une dichotomie?

** x ** (le numéro d'origine est $ n $) [fonction monotone croissante (ou décroissante)](https://ja.wikipedia.org/wiki/%E5%8D%98%E8%AA%BF% E5% 86% 99% E5% 83% 8F) Lorsque $ f $ est défini, il existe $ x ^ \ * \ in $ ** x ** où $ f (x ^ \ *) = t $ C'est un algorithme qui cherche quoi faire avec $ O (\ log n) $. [^ 1]

** Dans ce qui suit, $ f $ est implicitement utilisé comme une fonction croissante monotone, mais le même argument peut être avancé même si $ f $ est une fonction décroissante de manière monotone en concevant des mesures telles que l'inversion de l'inégalité. Je vais. ** **

Dans la dichotomie, la valeur minimale est recherchée à grande vitesse en recherchant la zone de recherche où la fonction $ f $ est définie par $ \ frac {1} {2} $, mais sous l'hypothèse suivante (✳︎) Puisque $ \ frac {1} {2} $ est en cours, (✳︎) est affiché.

(✳︎) Pour $ x ^ \ * \ in [l, r] $ où $ f (x ^ \ *) = t $ dans l'intervalle fermé $ [l, r] $, divisez-le en deux parties égales de $ [l, r] $ Lorsque le point est $ k $ $ f (k) \ geqq t \ rightarrow x ^ \ * \ in [l, k] $ et $ f (k) <t \ rightarrow x ^ \ * \ in (k, r] $

<détails>

Preuve </ summary>

(1) Quand $ f (k) \ geqq t $ $ f (k) \ geqq t \ leftrightarrow k \ geqq x ^ \ * $ ($ \ car f $ est une fonction monotone croissante) Par conséquent, $ x ^ \ * $ est inclus dans $ [l, k] $.

(2) Lorsque $ f (k) <t $ $ f (k) <t \ leftrightarrow k <x ^ \ * $ ($ \ car f $ est une fonction monotone croissante) Par conséquent, $ x ^ \ * $ est inclus dans $ (k, r] $.

Par conséquent, (✳︎) est indiqué à partir de (1) et (2).

[Q.E.D.]


<détails>

Diagramme de référence </ summary>

Voici un diagramme montrant le comportement de la dichotomie. J'espère que cela vous aide à comprendre.


De plus, si $ false $ est $ 0 $ et $ true $ est $ 1 $, la valeur de retour est une valeur booléenne et $ x ^ \ * \ in $ ** x ** est la limite entre $ false $ et $ true $. Vous pouvez penser à une fonction comme celle-ci, et vous pouvez trouver la limite $ x ^ \ * $ avec un algorithme similaire.

Mise en œuvre de la dichotomie

Vous trouverez ci-dessous une implémentation concrète de la dichotomie (je pense que les commentaires dans le code aideront à l'implémentation).

Aussi, puisque le but est de confirmer l'implémentation, je n'expliquerai pas le problème que j'ai traité dans cet article, mais il est recommandé de résoudre le problème une fois pour approfondir la compréhension de la dichotomie.

① Lorsque la valeur de retour de la fonction n'est pas une valeur booléenne

Il est souvent utilisé pour trouver des éléments dans un tableau trié qui sera $ k $. En considérant la zone de définition ** x ** comme un ensemble d'index et la valeur de retour de la fonction comme un élément du tableau correspondant à chaque index, il est vrai que la fonction monotone $ f $ peut être définie dans la zone de définition ** x **. Je comprends ça. De plus, si vous voulez trouver $ k $ dans un tableau trié, vous pouvez utiliser le module bisect pour ne pas avoir à implémenter vous-même une dichotomie. Pour plus d'informations, consultez Cet article.

Ici, nous rechercherons l'index de l'élément dont le tableau $ a = [0,1,1,2,4,5,6,8,8,9,10] $ par dichotomie.

basicbisect.py


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

#Code de recherche de bisection

#(1)l,r est l aux deux extrémités<=r
#Assurez-vous que l'indice l est inférieur à 2 et r est supérieur ou égal à 2.
l,r=0,10
#(2)l=r ou l=r-Pause à 1
while l+1<r:
    #(3)Milieu de la section fermée(Tronquer la partie fractionnaire de)
    #Compte tenu du débordement, il s'écrira comme suit
    k=l+(r-l)//2
    #(4)Division de la section fermée
    #a[k]>=Dans le cas de 2, définissez le point final le plus grand sur k et a[k]<Dans le cas de 2, définissez le point final le plus petit sur k
    if a[k]>=2:
        r=k
    else:
        l=k
#(5)production
#r est un[x]>=Minimum de 2 index(a[x]=Notez qu'il n'y a pas toujours un index x égal à 2.)
print(r)

(2) Lorsque la valeur de retour de la fonction est une valeur booléenne

Si vous souhaitez implémenter vous-même la dichotomie, ce modèle est très probable. Ci-dessous, le code est écrit en fonction de ABC063D-Widespread, et x qui rend la valeur de retour de la fonction $ f $ $ true $. Je recherche le plus petit d'entre eux. Aussi, si vous voulez savoir comment résoudre ce problème, Solution principale ou Mon article de commentaire Voir les éléments / 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

#Code de recherche de bisection

#(1)l,r est l aux deux extrémités<=r
#À ce stade, confirmez que l est faux et r est vrai.
l,r=0,10**9
#(2)l=r ou l=r-Pause à 1
while l+1<r:
    #(3)Milieu de la section fermée(Tronquer la partie fractionnaire de)
    #Compte tenu du débordement, il s'écrira comme suit
    k=l+(r-l)//2
    #(4)Division de la section fermée
    #x=Si k est vrai, définissez le point final le plus grand sur k et x=Si k est faux, définissez le point final le plus petit sur k
    if f(k):
        r=k
    else:
        l=k
#(5)production
#r est f(x)=Le plus petit des vrais x
print(r)

Recherche de trois minutes

Qu'est-ce qu'une recherche de trois minutes?

** x ** (le numéro d'origine est $ n $) ** Pseudo [fonction convexe (ou concave)](https://ja.wikipedia.org/wiki/%E5%87%B8%E9%96% A2% E6% 95% B0) ** Lorsque $ f $ est défini, $ x ^ \ * \ in $ ** x ** où $ f (x) $ est le minimum (ou maximum) est $ O (\ log n) Un algorithme qui recherche avec $. De plus, ** x ** a toujours un point minimum (ou point maximum) car il s'agit d'un ensemble fini.

** Dans ce qui suit, $ f $ est implicitement considéré comme une fonction pseudo-convexe, mais le même argument peut être fait même si $ f $ est une fonction pseudo-concave en concevant des mesures telles que l'inversion de l'inégalité. Masu **

Ici, la fonction pseudo-convexe est définie comme suit. [^ 2]

$ \ Lambda x_1 + (1- \ lambda) x_2 \ in $ ** x ** pour $ ^ ∀ x_1, x_2 \ in $ ** x **, $ ^ ∀ \ lambda \ in [0,1] $ Alors, $ f (\ lambda x_1 + (1- \ lambda) x_2) \ leqq \ lambda f (x_1) + (1- \ lambda) f (x_2) $ est valable.

Dans la recherche en trois parties, la valeur minimale est recherchée à grande vitesse en recherchant la zone de recherche où la fonction $ f $ est définie par $ \ frac {2} {3} $, mais sous l'hypothèse suivante (✳︎) Ceci est affiché car $ \ frac {2} {3} $ est ajouté à.

(✳︎) Pour le point minimum $ x ^ \ * \ in [l, r] $ dans l'intervalle fermé $ [l, r] $, le point de trisection de cet intervalle est $ c_1, c_2 (l \ leqq c_1 \ leqq c_2 \ leqq Lorsque r) $ $ f (c_1) \ leqq f (c_2) \ rightarrow $ Le point minimum $ x ^ \ * $ est inclus dans $ [l, c_2] $. $ f (c_1) \ geqq f (c_2) \ rightarrow $ Le point minimum $ x ^ \ * $ est inclus dans $ [c_1, r] $.

<détails>

Preuve </ summary>

(1) Quand $ x ^ \ * \ in [l, c_1] $ Puisque $ x ^ \ * \ leqq c_1 \ leqq c_2 $, il existe $ \ lambda \ dans [0,1] $ qui est $ c_1 = \ lambda x ^ \ * + (1- \ lambda) c_2 $. En ce moment,

\begin{align}
f(c_1) &= f(\lambda x^*+(1-\lambda)c_2) \\
& \leqq \lambda f(x^*)+(1-\lambda)f(c_2) \ (\car f est une fonction pseudo-convexe)\\
& \leqq \lambda f(c_2)+(1-\lambda)f(c_2) \ (\because f(x^*) \leqq f(c_2))\\
& = f(c_2)
\end{align}

(2) Quand $ x ^ \ * \ dans [c_1, c_2] $ Au moins un des $ f (c_1) \ leqq f (c_2) $ et $ f (c_1) \ geqq f (c_2) $ est valide.

(3) Quand $ x ^ \ * \ dans [c_2, r] $ Si vous faites la même chose que (1), vous pouvez obtenir $ f (c_1) \ geqq f (c_2) $.

Par conséquent, (✳︎) est représenté de (1) à (3).

[Q.E.D.]


<détails>

Diagramme de référence </ summary>

La figure ci-dessous montre la division de la section de la recherche de trois minutes. J'espère que cela vous aide à comprendre.


Mise en œuvre de la recherche par trisection

Vous trouverez ci-dessous une implémentation concrète de la recherche par trisection (je pense que les commentaires dans le code aideront à l'implémentation).

(1) Lorsque la zone de définition de la fonction est un intervalle fermé sur un nombre réel

Dans ce qui suit, considérons ARC054-B la loi de Moore. Dans ce problème, un nombre réel $ x \ in [0,10 ^ {18] qui minimise $ f (x) = x + \ frac {p} {2 ^ {\ frac {x} {1.5}}} $ }] Cela peut être réduit au problème de penser à $.

Ici, cette fonction $ f (x) $ peut être différenciée deux fois, donc lorsqu'elle est calculée, $ f ^ {''} (x) = (\ log 2) ^ 2 (- \ frac {2} {3}) ^ 2p \ times 2 ^ {- \ frac {2x} {3}}> 0 $, donc vous pouvez voir que la ** fonction $ f (x) $ est une fonction convexe **. [^ 3]

Par conséquent, vous pouvez rechercher $ x $, qui est le point minimum dans la recherche de trois quarts, et vous pouvez écrire le code suivant. De plus, ici, la plage de définition de la fonction n'est pas un entier mais un nombre réel, et la plage d'erreur est autorisée jusqu'à $ 10 ^ {-8} $, donc la plage de recherche est $ \ frac {2} {3} $ en une seule recherche. Compte tenu de cela, $ \ log_ {\ frac {3} {2}} \ frac {10 ^ {18}} {10 ^ {-8}} = 26 \ times \ log_ {\ frac {3} L'instruction while sera tournée environ {2}} {10} $ fois, ce qui rend le programme suffisamment rapide.

mooreslaw.py


p=float(input())

#(1)Définissez la fonction f que vous souhaitez minimiser
def f(x):
    global p
    return x+p*pow(2,-(x/1.5))

#(2)Je veux trouver la valeur minimale de la fonction f l aux deux extrémités de l'intervalle fermé,Mettre avec r(l<=r)
l,r=0,10**18
#(3)L'erreur est 10^-Tournez l'instruction while jusqu'à ce qu'elle tombe en dessous de 8.
while l+pow(10,-8)<r:
    #(4)Placez les points de trisection comme indiqué ci-dessous pour éviter tout débordement
    c1=l+(r-l)/3
    c2=r-(r-l)/3
    #(5)Faire une mise à jour
    if f(c1)<f(c2):
        r=c2
    else:
        l=c1
#(6)La sortie finale est l,Soit r c'est bien
print(f(l))

(2) Lorsque la zone de définition de la fonction est un intervalle fermé sur un entier

Dans ce qui suit, considérez ABC102D-Equal Cut. Puisque cette méthode est un peu différente de cette solution, je présenterai Mon article de commentaire comme article de référence.

C'est un problème assez difficile, donc j'aimerais que vous ne vérifiiez que la méthode d'implémentation par rapport au cas de ①.

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)Définissez la fonction f que vous souhaitez minimiser
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)Je veux trouver la valeur minimale de la fonction f l aux deux extrémités de l'intervalle fermé,Mettre avec r(l<=r)
    #Voici la valeur d'index
    l,r=0,i
    #(3)Puisqu'il s'agit d'un entier, r=l,l+1,l+Devrait être l'un des 2
    #Au contraire, r>=l+Dans le cas de 3, la différence entre r et l peut être réduite.
    while l+2<r:
        #(4)Point de trisection(Tronquer la partie fractionnaire)
        c1=l+(r-l)//3
        c2=r-(r-l)//3
        #(5)Faire une mise à jour
        if f(c1,i)<f(c2,i):
            r=c2
        else:
            l=c1
    #(6)La demande finale est l~L'élément de r qui minimise la valeur de la fonction f
    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])

    #Décidez de la bonne

    #(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))

finalement

J'ai été déçu de ne pas pouvoir résoudre le problème en utilisant la recherche de trois minutes, alors je l'ai considéré rigoureusement mathématiquement.

Veuillez également vous référer à la pièce de montage telle que je l'ai conçue moi-même.

Et je voudrais exprimer ma gratitude à la synchronisation universitaire pour m'avoir aidé à apporter les corrections dans cette explication mathématiquement rigoureuse.

Article de référence

Généralisation de l'algorithme de dichotomie-Recommandation de la méthode de dichotomie- Modèle d'implémentation de la dichotomie qui ne bogue jamais et 5 raisons pour lesquelles il ne bogue pas

[^ 1]: L'explication de la dichotomie suppose que $ x ^ \ * $ existe, mais notez que ** $ x ^ \ * $ peut ne pas exister **. [^ 2]: Nous avons introduit une fonction pseudo-convexe au lieu d'une fonction convexe car la première est définie sur un ensemble continu, nous considérons donc une fonction sur un ** ensemble discret **. [^ 3]: Pour la fonction $ f (x) $ qui peut être différenciée deux fois sur un ensemble continu, c'est une fonction convexe si la double différenciation est non négative, et si c'est une fonction convexe sur un ensemble continu, c'est un sous-ensemble de celle-ci. Il est implicitement utilisé pour être une fonction pseudo-convexe dans un ensemble discret.

Recommended Posts