Postscript: lien de référence
L'optimisation combinée (bfbf4c185ed7004b5721) (ce qu'on appelle l'optimisation d'entiers mixtes) vous permet d'écrire simplement diverses règles. Ici, nous présenterons brièvement quelques techniques utilisant des puzzles comme exemple. Certaines de ces techniques font également partie de Python. Python convient parfaitement à la modélisation de l'optimisation mathématique.
--Si vous voulez l'essayer rapidement: en utilisant un service appelé Binder, vous ne pouvez l'essayer qu'avec un navigateur. Pour plus d'informations, consultez Présentation de Binder, un service Jupyter gratuit (821ebd608c412e57382d). --Si vous voulez l'essayer correctement: Après avoir installé Anaconda, veuillez exécuter ce qui suit.
pip install pulp ortoolpy unionfind more_itertools
En tant que modélisateur, PuLP est utilisé. (À propos de PuLP) Dans l'exemple de code ci-dessous, ce qui suit est omis.
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()
| Méthode | Description |
|---|---|
| grouper par | Regrouper les éléments avec la même clé |
| unionfind | [Structure des données d'ensemble élémentaire](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83% Classe pour BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0) |
| addvar | Créer une variable |
| addvars | Créer une liste de variables |
| addbinvar | 0-1 Créer une variable |
| addbinvars | 0-1 Créer une liste de variables |
| LpProblem | Modèle d'optimisation mathématique PuLP |
Préparé dans SaitoTsutomu / OptForPuzzle.
Utilitaire: calcul accéléré, accès divers Puzzles cibles: "Soudain", etc. Exemple:
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)
-Dans (1), une variable 0-1 d'un tableau multidimensionnel 9x9x9 est créée. Chaque dimension représente une ligne, une colonne et un nombre. -Dans (2), cela signifie qu'il n'y a qu'un seul nombre $ k + 1 $ sur la ligne $ i $. -Dans (3), le coin supérieur gauche est l'aire de 3x3 où $ (i, j) $, ce qui signifie qu'il n'y a qu'un seul nombre $ k + 1 $.
Utilitaire: calcul accéléré, accès divers Puzzle cible: "Sudden" etc. (la visualisation est "Kurodoko" etc.) Exemple:
python
r = np.vectorize(value)(v).astype(int) # (1)
plt.imshow(1-r, cmap='gray', interpolation='none') # (2)
Il est pratique d'obtenir le résultat $ r $ comme indiqué dans (1) ci-dessus pour le résultat de la création d'une variable avec np.array et de la résolution de l'optimisation. De cette façon, vous pouvez obtenir des résultats rapidement et facilement, et vous pouvez continuer le traitement avec les différentes fonctionnalités de numpy. Si vous voulez vérifier le résultat de 2D noir et blanc sous forme de figure, vous pouvez facilement le visualiser en utilisant matplotlib comme indiqué dans (2).
Si les variables sont gérées par la série pandas DataFrame, vous pouvez faire de même avec apply.
Utilité: modélisation efficace Puzzle cible: "Zone de peinture", etc. Exemple:
python
for vi, vj in zip(v, v[1:]):
m += vi == vj
Si tous les éléments du tableau unidimensionnel de variables $ v $ doivent avoir la même valeur, vous pouvez écrire comme ci-dessus. (Il existe également un moyen de remplacer la variable elle-même)
Utilité: modélisation efficace Puzzles cibles: "Creek", "Shakashaka", "Plusieurs rouleaux", "Nori glue", "Paint area", "Bomber puzzle"
Si vous souhaitez utiliser la somme des variables supérieure, inférieure, gauche et droite de la variable de masse $ v [i, j] $, vous pouvez utiliser $ w $ comme indiqué ci-dessous. Exemple:
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:]
Voici un exemple d'utilisation correcte des tranches en préparant un tableau $ u $ qui est un tour de plus autour de v.
Utilité: exprime le cas qui tient en fonction des conditions
Puzzle cible: "Kanaore" etc.
Quand il y a des variables $ x, y
python
m += y <= a + M(1-x)
De plus, si vous souhaitez définir "$ y = a
python
m += y <= a + M(1-x)
m += y >= a - M(1-x)
Utilité: Modélisation facile Puzzle cible: "Kurodoko" etc.
Il y a une restriction selon laquelle «tous les carrés blancs sont connectés» comme «lieu noir». Essayer d'exprimer une telle contrainte avec une formule mathématique peut être assez difficile. Par conséquent, il existe un moyen de l'ignorer une fois et, s'il n'est pas connecté, d'interdire la solution et de la résoudre à nouveau.
Exemple: vérification de la connectivité
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
Supposons que le $ r $ résultant représente 0: blanc et 1: noir. Vous pouvez vérifier si le blanc est connecté avec unionfind.isconnected (1-r). Dans cet esprit, vous pouvez changer le modèle jusqu'à ce qu'il soit connecté comme indiqué ci-dessous.
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
Le code ci-dessus est simple, mais il peut être long à répéter pour certaines énigmes. Dans ce cas, au lieu "d'interdire tous les carrés noirs dans le résultat", il est possible de résoudre efficacement en "interdisant les carrés noirs entourant le blanc" pour chaque zone blanche divisée par les carrés noirs. Je peux le faire.
Avantages: saisie et programmation simples Puzzles cibles: "Factor Room", "Country Road", "Satogaeri", "Star Battle", "Tile Paint", "Chocona", "Nori Nori", "Heyawari", "Paint Area" Exemple:
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
Le tableau des cellules bidimensionnelles est divisé en pièces comme indiqué dans les données ci-dessus. À ce stade, la condition selon laquelle «il y a un carré noir dans chaque pièce» peut être simplement écrite comme ci-dessus en utilisant group by.
Utilité: Modélisation facile Puzzles cibles: "Kanaore" "Satogaeri" "Découpé en carrés" "Nurikabe" "Noguram" "Filmat" "Block puzzle" "Firefly beam]
Si vous avez deux variables 0-1 $ x, y $ et que vous voulez que l'une d'entre elles au plus tienne (= 1), vous pouvez faire ce qui suit:
Exemple:
python
m += x + y <= 1
S'il est difficile d'exprimer les règles d'un puzzle dans une formule mathématique, il peut être facile de modéliser en énumérant les combinaisons qui satisfont aux règles et en les laissant choisir parmi elles. Une telle formulation correspond au problème de division d'ensemble du problème typique.
Jetons un œil à la fonction de création de candidats "Kanaore". Exemple:
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)])
L'argument d est la direction. Ajoutez 1 carré dans (1), et lorsque p atteint la longueur, ajoutez-le à lst et terminez. Sinon, répétez la recherche dans quatre directions. Il serait difficile de modéliser "Kanaore" autrement que de cette façon. Les langages de modélisation tels que AMPL ne permettent pas une écriture flexible. Utiliser Python pour la modélisation de cette manière peut être très utile.
c'est tout
Recommended Posts