[PYTHON] Solution optimale en combinant des «chambres à facteurs»
Résoudre la salle des facteurs
La ** Factor Room ** est un puzzle qui ressemble à un nombre. Ce casse-tête peut également être résolu en utilisant Optimisation de combinaison. référence
Exemple de problème
Avec le consentement de Nikori, j'ai emprunté un exemple. La gauche est la question et la droite est la réponse. Le problème est divisé en pièces entourées de lignes épaisses, avec des chiffres indicatifs en haut à gauche. L'indice est la multiplication des nombres dans la pièce. Pour une taille 5x5, les nombres que vous pouvez utiliser sont de 1 à 5. Comme pour Sugoku, les mêmes nombres ne peuvent pas être utilisés dans une ligne verticale ou une colonne horizontale.
Formulation
L'important dans le modèle d'optimisation de combinaison est de l'exprimer autant que possible sous forme d'expression linéaire. La simple modélisation de la multiplication des variables aboutit à une optimisation non linéaire et est difficile à résoudre. Cette fois, nous utiliserons la logique logarithmique pour créer une expression linéaire. En d'autres termes, vous pouvez y penser comme suit.
De cette manière, il peut être exprimé sous la forme d'une expression linéaire. Cependant, s'il est laissé tel quel, une erreur de calcul se produira car un nombre déraisonnable sera utilisé. Par conséquent, spécifiez l'expression de contrainte afin qu'elle se situe dans une petite plage et non dans un nombre égal.
La formulation est la suivante.
| $ \ mbox {variables} $ | $ x_ {ijk} \ in \ {0, 1 \} ~ \ forall i, j, k $ | La masse i, j est-elle le nombre k + 1? (1) |
| $ y_ {ij} \ in \ {1 \ cdots n \} ~ \ forall i, j $ | Nombres i, j (2) | |
| $ \ mbox {sujet à} $ | $ \ sum_k {x_ {ijk}} = 1 ~ \ forall i, j $ | Un nombre (3) |
| $ \ sum_k {x_ {ikj}} = 1 ~ \ forall i, j $ | Pas de même nombre vertical (4) | |
| $ \ sum_k {x_ {kij}} = 1 ~ \ forall i, j $ | Il n'y a pas le même numéro à côté (5) | |
| $ y_ {ij} est représenté par x_ {ijk} $ (6) | ||
| Le produit des carrés est égal à l'indice (7) | ||
Résoudre avec Python
[pulpe](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Utilisez% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB) et les pandas.
Le problème est que c'est dans une chaîne.
python
ch = """
ABBCD
AEEFD
GGHFD
IJHKK
ILHMM
""".strip().split('\n')
rooms = [6, 15, 1, 12, 20, 8, 10, 6, 4, 4, 15, 1, 10]
Sois prêt.
python
import pandas as pd
from collections import defaultdict
from pulp import *
from math import log
def addvar(lowBound=0, count=[0], *args, **kwargs):
count[0] += 1
return LpVariable('v%d'%count[0], lowBound=lowBound, *args, **kwargs)
nn, nb = len(ch), len(rooms) #Nombre de numéros, nombre de chambres
rn, rb = range(nn), range(nb)
lognn = [log(k + 1) for k in rn] # 1..nn log
logrm = [log(h) for h in rooms] #Journal des pourboires
Faisons un tableau de variables.
python
a = pd.DataFrame([(i, j, [addvar(cat=LpBinary) for k in rn], addvar())
for i in rn for j in rn],
columns=['Verticale', 'côté', 'Vars', 'Var']) # (1), (2)
print(a[:3])
- Les variables de la verticale $ i $ horizontale $ j $ correspondent à [$ x_ {ijk} \ forall k $], et Var correspond à $ y_ {ij} $.
| Vertical | Horizontal | Vars | Var | |
|---|---|---|---|---|
| 0 | 0 | 0 | [v1, v2, v3, v4, v5] | v6 |
| 1 | 0 | 1 | [v7, v8, v9, v10, v11] | v12 |
| 2 | 0 | 2 | [v13, v14, v15, v16, v17] | v18 |
Formulez et résolvez.
python
m = LpProblem() #Modèle mathématique
dic = defaultdict(list) #Variables pour chaque pièce(x)Liste de
for _, r in a.iterrows():
m += lpSum(r.Vars) == 1 # (3)
m += lpDot(rn, r.Vars) + 1 == r.Var # (6)
dic[ch[r.Verticale][r.côté]].append(r.Vars)
for i in rn:
for k in rn:
m += lpSum(v[k] for v in a.query('Verticale==%d'%i).Vars) == 1 # (4)
m += lpSum(v[k] for v in a.query('côté==%d'%i).Vars) == 1 # (5)
for h in rb:
c = lpSum(lpDot(lognn, v) for v in dic[chr(h + 65)]) #Journal du produit des nombres
m += c >= logrm[h] - 0.001 # (7)
m += c <= logrm[h] + 0.001 # (7)
m.solve() #Solution
Affichez le résultat.
python
a['Val'] = a.Var.apply(value)
print(a.Val.reshape(5, -1))
>>>
[[ 2. 3. 5. 1. 4.]
[ 3. 5. 4. 2. 1.]
[ 5. 2. 1. 4. 3.]
[ 1. 4. 2. 3. 5.]
[ 4. 1. 3. 5. 2.]]
c'est tout