Techniques d'optimisation combinées vues dans les puzzles

Postscript: lien de référence

introduction

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.

Environnement

--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

Préparation

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

Puzzle cible

Préparé dans SaitoTsutomu / OptForPuzzle.

Technique

Créer des variables avec np.array

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 $.

Obtenez le résultat avec np.vectorize

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.

Tous les mêmes

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)

Nombre autour

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.

Contrainte IF

Utilité: exprime le cas qui tient en fonction des conditions Puzzle cible: "Kanaore" etc. Quand il y a des variables $ x, y , si vous voulez faire " y \ le a " si " x == 1 $", utilisez un nombre suffisamment grand $ M $ comme indiqué ci-dessous. Je peux écrire. Exemple:

python


m += y <= a + M(1-x)

De plus, si vous souhaitez définir "$ y = a " si " x == 1 $", vous pouvez écrire comme suit. Exemple:

python


m += y <= a + M(1-x)
m += y >= a - M(1-x)

Contraintes de concaténation

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.

Traitement par zone (pièce ou pays)

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.

Sélectionnez parmi les candidats

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

Techniques d'optimisation combinées vues dans les puzzles
Résolution de "cubes en cubes" avec optimisation des combinaisons
Python en optimisation
Utiliser l'optimisation des combinaisons
Optimisation du regroupement par combinaison
Optimisation des performances dans Django 3.xx
Enquête Star avec optimisation des combinaisons
Jeux de regroupement avec optimisation des combinaisons
Techniques de tri en Python
Optimisation combinée avec recuit quantique
Résoudre les problèmes d'optimisation avec Python