Nachtrag: Referenzlink
Mit der Kombinationsoptimierung (bfbf4c185ed7004b5721) (sogenannte Mixed Integer-Optimierung) können Sie einfach verschiedene Regeln schreiben. Hier werden wir einige Techniken am Beispiel von Rätseln kurz vorstellen. Einige dieser Techniken sind auch Teil von Python. Python eignet sich gut zur Modellierung der mathematischen Optimierung.
pip install pulp ortoolpy unionfind more_itertools
Als Modellierer wird PuLP verwendet. (Über PuLP) Im folgenden Codebeispiel wird Folgendes weggelassen.
python
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
from itertools import groupby
from pulp import *
from unionfind import unionfind
from ortoolpy import addvar, addvars, addbinvar, addbinvars
m = LpProblem()
| Methode | Beschreibung |
|---|---|
| gruppieren nach | Gruppieren Sie Dinge mit demselben Schlüssel |
| unionfind | [Datenstruktur des Elementarsatzes](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83% Klasse für BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0) |
| addvar | Eine Variable erstellen |
| addvars | Erstellt eine Liste von Variablen |
| addbinvar | 0-1 Erstellen Sie eine Variable |
| addbinvars | 0-1 Erstellt eine Liste von Variablen |
| LpProblem | PuLP Mathematical Optimization Model |
Vorbereitet in SaitoTsutomu / OptForPuzzle.
Dienstprogramm: Beschleunigen Sie die Berechnung, verschiedene Zugriffe Zielrätsel: "Plötzlich" usw. Beispiel:
python
v = np.array(addbinvars(9, 9, 9)) # (1)
m += lpSum(v[i,:,k]) == 1 # (2)
m += lpSum(v[i:i+3,j:j+3,k]) == 1 # (3)
w = addvars(9, 9) # (4)
m += lpDot(range(9), v[i,j])+1 == r[i][j] # (4)
-In (1) wird eine 0-1-Variable eines mehrdimensionalen 9x9x9-Arrays erstellt. Jede Dimension repräsentiert eine Zeile, eine Spalte und eine Zahl. -In (2) bedeutet dies, dass es nur eine Zahl $ k + 1 $ in der Zeile $ i $ gibt. -In (3) ist oben links der Bereich von 3x3, in dem $ (i, j) $, was bedeutet, dass es nur eine Zahl $ k + 1 $ gibt.
Dienstprogramm: Beschleunigen Sie die Berechnung, verschiedene Zugriffe Zielrätsel: "Plötzlich" usw. (Visualisierung ist "Kurodoko" usw.) Beispiel:
python
r = np.vectorize(value)(v).astype(int) # (1)
plt.imshow(1-r, cmap='gray', interpolation='none') # (2)
Es ist zweckmäßig, das Ergebnis $ r $ wie in (1) oben gezeigt zu erhalten, um eine Variable mit np.array zu erstellen und die Optimierung zu lösen. Auf diese Weise erhalten Sie schnell und einfach Ergebnisse und können die Verarbeitung mit den verschiedenen Funktionen von numpy fortsetzen. Wenn Sie das Ergebnis von 2D-Schwarzweiß als Abbildung überprüfen möchten, können Sie es mithilfe von matplotlib wie in (2) gezeigt einfach visualisieren.
Wenn die Variablen von der Pandas DataFrame-Serie verwaltet werden, können Sie dies auch mit apply tun.
Dienstprogramm: Effiziente Modellierung Zielpuzzle: "Malbereich" etc. Beispiel:
python
for vi, vj in zip(v, v[1:]):
m += vi == vj
Wenn alle Elemente des eindimensionalen Variablenarrays $ v $ denselben Wert haben müssen, können Sie wie oben schreiben. (Es gibt auch eine Möglichkeit, die Variable selbst zu ersetzen.)
Dienstprogramm: Effiziente Modellierung Zielrätsel: "Creek", "Shakashaka", "Mehrere Walzen", "Nori-Kleber", "Malbereich", "Bomber-Puzzle"
Wenn Sie die Summe der oberen, unteren, linken und rechten Variablen der Massenvariablen $ v [i, j] $ verwenden möchten, können Sie $ w $ wie unten gezeigt verwenden. Beispiel:
python
u = np.zeros((nh+2, nw+2), dtype=object)
v = u[1:-1,1:-1] = np.array(addbinvars(nh, nw))
w = u[:-2,1:-1]+u[2:,1:-1]+u[1:-1,:-2]+u[1:-1,2:]
Dies ist ein Beispiel für die gute Verwendung von Slices, indem ein Array $ u $ vorbereitet wird, das eine Runde weiter um v liegt.
Dienstprogramm: Drückt den Fall aus, der abhängig von den Bedingungen gilt
Zielrätsel: "Kanaore" usw.
Wenn es Variablen $ x, y $ gibt und Sie "$ y \ le a
python
m += y <= a + M(1-x)
Wenn Sie "$ y = a
python
m += y <= a + M(1-x)
m += y >= a - M(1-x)
Dienstprogramm: Einfache Modellierung Zielpuzzle: "Kurodoko" etc.
Es gibt eine Einschränkung, dass "alle weißen Quadrate miteinander verbunden sind" wie "schwarzer Ort". Der Versuch, eine solche Einschränkung mit einer mathematischen Formel auszudrücken, kann ziemlich schwierig sein. Daher gibt es eine Möglichkeit, es einmal zu ignorieren. Wenn es nicht verbunden ist, verbieten Sie die Lösung und lösen Sie sie erneut.
Beispiel: Überprüfen der Konnektivität
python
from unionfind import unionfind
r = np.array(
[[0,0,0],
[1,1,1],
[0,0,0]])
print(unionfind.isconnected(1-r))
r[1][1] = 0
print(unionfind.isconnected(1-r))
>>>
False
True
Angenommen, das resultierende $ r $ steht für 0: Weiß und 1: Schwarz. Sie können überprüfen, ob Weiß mit unionfind.isconnected (1-r) verbunden ist. In diesem Sinne können Sie das Modell ändern, bis es wie unten gezeigt verbunden ist.
python
while True:
m.solve()
r = np.vectorize(value)(v).astype(int)
if unionfind.isconnected(1-r):
break
m += lpSum(v[r==1]) <= r.sum() - 1
Der obige Code ist einfach, kann jedoch bei einigen Rätseln lange dauern. In diesem Fall ist es möglich, anstatt "alle schwarzen Zellen im Ergebnis zu verbieten", effizient zu lösen, indem "die schwarzen Zellen, die das Weiß umgeben", für jeden durch die schwarzen Zellen geteilten weißen Bereich "verboten" werden. Ich kann es schaffen
Vorteile: Einfache Eingabe und Programmierung Zielrätsel: "Factor Room", "Country Road", "Satogaeri", "Star Battle", "Tile Paint", "Chocona", "Nori Nori", "Hey" Beispiel:
python
data = """\
AABBB
AABCC
ADDDC
DDECC
EEEEC""".split()
v = np.array(addbinvars(nn, nn))
for _, d in groupby(sorted(zip(''.join(data), v.flat)), lambda x:x[0]):
m += lpSum(c[1] for c in d) == 1
Die Tabelle der zweidimensionalen Zellen ist wie in den obigen Daten gezeigt in Räume unterteilt. Zu diesem Zeitpunkt kann die Bedingung, dass "in jedem Raum ein schwarzes Quadrat vorhanden ist", einfach wie oben beschrieben werden, indem group by verwendet wird.
Dienstprogramm: Einfache Modellierung Zielrätsel: "Kanaore" "Satogaeri" "In Quadrate schneiden" "Nurikabe" "Noguram" "Filmat" "Blockpuzzle" "Firefly Beam]
Wenn Sie zwei 0-1-Variablen $ x, y $ haben und höchstens eine davon (= 1) enthalten soll, können Sie Folgendes tun:
Beispiel:
python
m += x + y <= 1
Wenn es schwierig ist, die Regeln eines Puzzles mit einer Formel auszudrücken, kann es einfach sein, die Kombinationen, die den Regeln entsprechen, aufzulisten und sie aus ihnen auswählen zu lassen. Eine solche Formulierung entspricht dem Set Division Problem des Typical Problem.
Werfen wir einen Blick auf die Funktion zur Erstellung von Kandidaten für "Kanaore". Beispiel:
python
def makecand(lst, y, x, d, l, p, u):
yy, xx = y+[0, -1, 0, 1][d], x+[-1, 0, 1, 0][d] # (1)
if 0 <= yy < nh and 0 <= xx < nw and (yy,xx) not in u:
if p == l - 1:
lst.append(u + [(yy, xx)])
return
for k in range(4):
makecand(lst, yy, xx, k, l, p + 1, u + [(yy,xx)])
Das Argument d ist die Richtung. Fügen Sie 1 Quadrat in (1) hinzu, und wenn p die Länge erreicht, fügen Sie es zu lst hinzu und beenden Sie. Wenn nicht, wiederholen Sie die Suche in vier Richtungen. Es wäre schwierig, "Kanaore" anders als auf diese Weise zu modellieren. Modellierungssprachen wie AMPL ermöglichen kein flexibles Schreiben. Die Verwendung von Python für die Modellierung auf diese Weise kann sehr nützlich sein.
das ist alles
Recommended Posts