[PYTHON] Finden Sie Golferwartungen mithilfe dynamischer Optimierung

Dinge die zu tun sind

• Einfache Bestätigung der dynamischen Optimierung
• Berechnung des erwarteten Golfwertes

Einfache Bestätigung der dynamischen Optimierung

Was ist dynamische Optimierung?

――Dynamische Optimierung ist ein neuerer Begriff für dynamische Programmierung.

• Lösen Sie ein Teilproblem und verwenden Sie das Ergebnis, um das gesamte Problem zu lösen. Zu diesem Zeitpunkt wird für dasselbe Teilproblem, das wiederholt auftritt, der Ergebniscache verwendet, um effizient zu berechnen (Memo).

Einfache Bestätigung mit Rucksackproblem

In Python erleichtert lru_cache das Zwischenspeichern von Ergebnissen. (Wenn das Argument gehasht werden kann) Lassen Sie uns den Effekt mit dem Rucksackproblem sehen.

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

Hier wird das Rucksackproblem in Teilprobleme unterteilt, je nachdem, ob das erste Element ausgewählt ist oder nicht, und das Problem wird rekursiv gelöst.

--count_knapsack1 berechnet die Anzahl der nicht zwischengespeicherten Anrufe. --count_knapsack2 berechnet die Anzahl der zwischengespeicherten Anrufe.

Der einzige Unterschied ist das Vorhandensein oder Fehlen von lru_cache. Mal sehen, das Ergebnis.

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='Kein Cache')
plt.plot(rng, res2, label='Mit Cache')
plt.xlabel('Stückzahl')
plt.ylabel('Anzahl der Anrufe')
plt.yscale('log')
plt.legend(loc='lower right');

Da die vertikale Achse die logarithmische Achse ist, können Sie sehen, dass sich der Cache erheblich beschleunigt.

Berechnung des erwarteten Golfwertes

Betrachten Sie als nächstes ein einfaches Golfproblem.

――Sie und Ihr Gegner kämpfen um eine Punktzahl von 18 Löchern. Wenn Sie gewinnen, erhalten Sie +1 Punkt, wenn Sie verlieren, erhalten Sie -1 Punkt und Sie ziehen 0 Punkte. ――Es sind 18 Löcher, aber alle Bedingungen sind gleich. ――Der Gegner hat eine 20% ige Chance, ein Bogey zu werden, eine 60% ige Chance, ein Par zu werden, und eine 20% ige Chance, ein Birdie zu werden. ――Sie müssen für jedes Loch entweder Sicherheitsmaßnahmen oder harte Maßnahmen wählen.

• Der Schutz beträgt 10% Chance, Bogey zu sein, 80% Chance, Par zu sein, und 10% Chance, Birdie zu sein. ――Die Hardline-Strategie besteht aus einer 30% igen Chance, Bogey zu sein, einer 40% igen Chance, Par zu sein, und einer 30% igen Chance, Birdie zu sein.

Lassen Sie uns die Möglichkeiten (%) für jede Kennzahl tabellieren.

Betrachtet man den Punktedifferenz, gibt es 5 Möglichkeiten: [-2, -1, 0, +1, +2]. Teilprobleme entstehen durch die Aufteilung dieser 10 Wege (5 Sicherheitsmaßnahmen + 5 harte Maßnahmen).

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:Anzahl der verbleibenden Löcher
    df:Aktuelle Punktzahldifferenz(Negativ gewinnt)
Rückgabewert:Ob Sicherheitsmaßnahmen ergriffen werden sollen,Erwartete Punktzahl
    """
    if rem == 1: #Letztes Loch
        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('Anzahl der verbleibenden Löcher')
plt.ylabel('Erwartete Punktzahl')
plt.plot(range(18), [golf(i, 0)[1] for i in rng]);
plt.xticks(range(18), rng);

Je mehr Löcher Sie noch haben, desto höher ist Ihre erwartete Punktzahl. Es wird angenommen, dass dies darauf zurückzuführen ist, dass Sicherheitsmaßnahmen ergriffen werden, wenn dies vorteilhaft ist, und dass harte Maßnahmen ergriffen werden, wenn dies nachteilig ist.

das ist alles