[PYTHON] Trouvez les attentes du golf grâce à l'optimisation dynamique

Choses à faire

• Confirmation facile de l'optimisation dynamique --Calcul de la valeur attendue du golf

Confirmation facile de l'optimisation dynamique

Qu'est-ce que l'optimisation dynamique?

―― L'optimisation dynamique est un terme récent pour la programmation dynamique.

• Résolvez un problème partiel et utilisez le résultat pour résoudre l'ensemble du problème. À ce moment-là, pour le même problème partiel qui apparaît à plusieurs reprises, le cache de résultats est utilisé pour calculer efficacement (mémo).

Confirmation facile avec problème de sac à dos

En Python, lru_cache facilite la mise en cache des résultats. (Si l'argument peut être haché) Voyons l'effet du problème du sac à dos.

python

%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
from functools import lru_cache
plt.rcParams['font.family'] = 'IPAexGothic'
plt.rcParams['font.size'] = 16

count = 0
np.random.seed(1)
_size = np.random.randint(100, 200, 100)
_weight = np.random.randint(100, 200, 100)

def make_sample(n):
    size = tuple(_size[:n])
    weight = tuple(_weight[:n])
    capacity = sum(size) // 3 * 2
    return size, weight, capacity

def knapsack1(size, weight, capacity):
    if len(size) == 0 or capacity < min(size):
        return 0
    global count
    count += 1
    r = capacity - size[0]
    if r < 0:
        return knapsack1(size[1:], weight[1:], capacity)
    else:
        return max(weight[0] + knapsack1(size[1:], weight[1:], r),
                    knapsack1(size[1:], weight[1:], capacity))

@lru_cache(None)
def knapsack2(size, weight, capacity):
    if len(size) == 0 or capacity < min(size):
        return 0
    global count
    count += 1
    r = capacity - size[0]
    if r < 0:
        return knapsack2(size[1:], weight[1:], capacity)
    else:
        return max(weight[0] + knapsack2(size[1:], weight[1:], r),
                    knapsack2(size[1:], weight[1:], capacity))

def count_knapsack1(n):
    global count
    count = 0
    knapsack1(*make_sample(n))
    return count

def count_knapsack2(n):
    global count
    count = 0
    knapsack2(*make_sample(n))
    return count

Ici, le problème du sac à dos est divisé en problèmes partiels selon que le premier article est sélectionné ou non, et le problème est résolu de manière récursive.

--count_knapsack1 calcule le nombre d'appels non mis en cache. --count_knapsack2 calcule le nombre d'appels mis en cache.

La seule différence est la présence ou l'absence de lru_cache. Voyons le résultat.

python

rng = [10, 12, 14, 16, 18, 20]
res1 = [count_knapsack1(i) for i in rng]
res2 = [count_knapsack2(i) for i in rng]

plt.plot(rng, res1, label='Pas de cache')
plt.plot(rng, res2, label='Avec cache')
plt.xlabel('Nombre d'éléments')
plt.ylabel('Nombre d'appels')
plt.yscale('log')
plt.legend(loc='lower right');

Puisque l'axe vertical est l'axe logarithmique, vous pouvez voir que le cache accélère considérablement.

Calcul de la valeur de golf attendue

Ensuite, considérez un problème de golf simple.

―― Vous et votre adversaire vous disputez un score de 18 trous. Si vous gagnez, vous obtenez +1 point, si vous perdez, vous obtenez -1 point et vous tirez 0 point. ――C'est 18 trous, mais toutes les conditions sont les mêmes. ―― L'adversaire a 20% de chances de devenir un épouvantail, 60% de chances de devenir un par et 20% de chances de devenir un oiseau. ――Vous devez choisir des mesures de sécurité ou des mesures rigides pour chaque trou.

• La sauvegarde est de 10% de chance d'être bogey, 80% de chance d'être par, et 10% de chance d'être birdie. ―― La stratégie de la ligne dure est de 30% de chances d'être un épouvantail, de 40% de chances d'être égal et de 30% de chances d'être birdie.

Tableau des possibilités (%) pour chaque mesure.

En regardant la différence de score, il y a 5 façons: [-2, -1, 0, +1, +2]. Des problèmes partiels sont créés en divisant ces 10 voies (5 mesures de sécurité + 5 mesures dures).

python

a0 = np.arange(-2, 3)
a1 = [0.02, 0.22, 0.52, 0.22, 0.02]
a2 = [0.06, 0.26, 0.36, 0.26, 0.06]
@lru_cache(None)
def golf(rem, df):
    """
    rem:Nombre de trous restants
    df:Différence de score actuelle(Victoires négatives)
Valeur de retour:S'il faut prendre des mesures de sécurité,Score attendu
    """
    if rem == 1: #Dernier trou
        s1 = np.inner(a1, (a0+df)<0) - np.inner(a1, (a0+df)>0)
        s2 = np.inner(a2, (a0+df)<0) - np.inner(a2, (a0+df)>0)
    else:
        a = [golf(rem-1, df+i)[1] for i in a0]
        s1 = np.inner(a, a1)
        s2 = np.inner(a, a2)
    return s1 >= s2, max(s1, s2)

rng = range(18,0,-1)
plt.xlabel('Nombre de trous restants')
plt.ylabel('Score attendu')
plt.plot(range(18), [golf(i, 0)[1] for i in rng]);
plt.xticks(range(18), rng);

Plus vous avez de trous, plus votre score attendu est élevé. On pense que cela est dû à la prise de mesures de sécurité quand c'est avantageux et de mesures dures quand c'est désavantageux.

c'est tout