PythonSandbox/hilbertDistance/minseeker.py

# Jovian Hersemeule

def dicho(f, a, b, epsilon=0.01, n=10, deep=0, deep_max=10, debug=False, prefix=""):
    """
    Cherche le minimum entre a et b.
    :param f: Fonction numérique.
    :param a: Borne inférieure.
    :param b: Borne supérieure.
    :param epsilon: Marge tolérée.
    :param n: Découpage.
    :param deep: Profondeur d'appel.
    :param deep_max: Profondeur d'appel maximale.
    :param debug: Si vrai alors fait des print.
    :param prefix: Chaine affichées en tête de ligne.
    :return: x0 où f(x0) est le minimum.
    """
    # Profondeur
    deep_next = deep + 1
    if deep_next <= deep_max:
        if debug:
            print(prefix, "Lancement du calcul à profondeur ", deep_next, " entre ", a, " et ", b, ".")
    else:
        if debug:
            print(prefix, "Avortment du calcul : profondeur maximale dépassée.")
        return a

    # Recherche
    pas = (b - a) / n
    mini = f(a)
    loc = a
    x = a
    img = 0

    for k in range(n - 1):
        x += pas

        img = f(x)
        if img < mini:
            if debug:
                print(prefix, "Nouveau minimum trouvé. Ancien : x0 = ", loc, " et y0 = ", mini, "Nouveau : x0 = ", x,
                      " et y0 = ", img)
            mini = img
            loc = x
        elif debug:
            print(prefix, "Ce n'est pas un nouveau minimum.")

    # Erreur acceptable
    if abs(f(loc + pas / 2) - f(loc)) + abs(f(loc - pas / 2) - f(loc)) < epsilon:
        if debug:
            print(prefix, "Minimum trouvé en ", loc, " de valeur ", mini, "\n")
        return loc
    else:
        return dicho(f, loc - pas, loc + pas, epsilon=epsilon, n=n, deep=deep_next, debug=debug, prefix=prefix)


def minSeeker(f, x1, x2, y1, y2, epsilon=0.01, debug=False):
    """
    Cherche à minimiser f( x, y ).
    :param f: Une fonction numérique à deux paramètres réels.
    :param x1, x2, y1, y2: Les plages de valeurs de recherche.
    :param epsilon: Marge tolérée.
    :param debug: Si vrai alors fait des print.
    :return: ( v, a, b ) où v = f(a , b) le minimum cherché.
    """
    if debug:
        print("Exécution de minSeeker.")
        print("x dans ", x1, " : ", x2)
        print("y dans ", y1, " : ", y2, "\n")

    minLine = lambda x: dicho(lambda t: f(x, t), y1, y2, epsilon=epsilon, debug=debug, prefix="|   > ")

    ans = dicho(minLine, x1, x2, epsilon=epsilon, debug=debug, prefix="> ")

    if debug:
        print("Fin de l'exécution de minSeeker. Minimum trouvé : ", ans, ".\n")

    return ans