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

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

Explication et mise en œuvre de SocialFoceModel

Explication et mise en œuvre de PRML Chapitre 4

Explication et implémentation de l'algorithme ESIM

Explication et mise en œuvre du perceptron simple

Mise en œuvre et expérience de la méthode de clustering convexe

Explication et implémentation de l'algorithme Decomposable Attention

Explication de la distance d'édition et de l'implémentation en Python

Principes de base et mise en œuvre de Perceptron

Explication et mise en œuvre de SocialFoceModel

Normalisation de la théorie et de la mise en œuvre des flux

J'ai comparé Java et Python!

Structure WordNet et recherche de synonymes

bases de python: conditions et itérations

Description et implémentation de Maxout (Python)

[Python] Recherche de priorité de profondeur et recherche de priorité de largeur

Exploration avec Python et Twitter API 2-Implémentation de la fonction de recherche d'utilisateurs

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

[Deep Learning from scratch] Implémentation de la méthode Momentum et de la méthode AdaGrad

Vérification et mise en œuvre de la méthode de reconstruction vidéo en utilisant GRU et Autoencoder

Explication du CSV et exemple d'implémentation dans chaque langage de programmation

Exploration avec Python et Twitter API 2-Implémentation de la fonction de recherche d'utilisateurs

[Python] Implémentation de la méthode Nelder – Mead et sauvegarde des images GIF par matplotlib

[Recommandation] Résumé des avantages et des inconvénients de la méthode de filtrage / mise en œuvre basée sur le contenu et coopérative

Introduction et mise en œuvre de JoCoR-Loss (CVPR2020)

Introduction et mise en œuvre de la fonction d'activation

Implémentation Einsum de la méthode d'itération de valeur

Qiskit: Implémentation de QAOA sans Qiskit Aqua

Explication et implémentation du protocole XMPP utilisé dans Slack, HipChat et IRC